Nonnegative object came to the result unbounded

Dear all,

I was trying to minimize a nonnegative object. But the result shows unbounded. Could u help me find out what’s wrong here ?

The code is to perform the algorithm shown in the following formula:

``````load('data1.mat');
[N,d] = size (Xtrain);
beta = ones(d,1);
solution = zeros(10,d);
for k = 1:10
cvx_begin
variable x(d);
minimize ((Ytrain - Xtrain*x)'*(Ytrain - Xtrain*x)/N + 0.5* sum(abs(x)./(sqrt(abs(beta))+ eps)));
cvx_end
solution(k, 1:d) = x';
beta = x;
clear x;

end
``````

Can you show the output from running it? Which iteration (value of k) did your get the unbounded message? Did you look at the beta which was used in that iteration? Did it have any very large magnitude components?

We haven’t seen data1.mat, so we don’;t know whether your input data might be very bad numerically (spanning many orders of magnitude). Perhaps the solver is having numerical difficulties with challenging input data, to include value of beta somwhere for k=2:10… Have you tried more than one solver?

Thank you for such a quick reply.

I set beta all ones at the beginning.

The “unbounded” first appear when k = 3, and the outcome of the first 3 steps are shown as below:

Calling SDPT3 4.0: 622 variables, 221 equality constraints For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 221
dim. of socp var = 622, num. of socp blk = 111

SDPT3: Infeasible path-following algorithms

number of iterations = 14 primal objective value = -1.29442904e-01 dual objective value = -1.29442918e-01 gap := trace(XZ) = 1.47e-08 relative gap = 1.17e-08 actual relative gap = 1.16e-08 rel. primal infeas (scaled problem) = 4.34e-13 rel. dual " " " = 1.77e-12 rel. primal infeas (unscaled problem) = 0.00e+00 rel. dual " " " = 0.00e+00 norm(X), norm(y), norm(Z) = 5.4e+00, 2.6e+01, 3.6e+01 norm(A), norm(b), norm© = 1.5e+06, 6.2e+00, 1.9e+01 Total CPU time (secs) = 1.91 CPU time per iteration = 0.14 termination code = 0 DIMACS: 1.8e-12 0.0e+00 1.7e-11 0.0e+00 1.2e-08 1.2e-08

Status: Solved
Optimal value (cvx_optval): +0.126943

Calling SDPT3 4.0: 622 variables, 221 equality constraints For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 221
dim. of socp var = 622, num. of socp blk = 111

SDPT3: Infeasible path-following algorithms

number of iterations = 17 primal objective value = 1.64203328e+00 dual objective value = 7.53547409e+07 gap := trace(XZ) = 2.17e+03 relative gap = 2.87e-05 actual relative gap = -1.00e+00 rel. primal infeas (scaled problem) = 3.89e-11 rel. dual " " " = 1.47e-05 rel. primal infeas (unscaled problem) = 0.00e+00 rel. dual " " " = 0.00e+00 norm(X), norm(y), norm(Z) = 5.0e+11, 5.6e+03, 7.9e+03 norm(A), norm(b), norm© = 1.5e+06, 5.0e+11, 1.9e+01 Total CPU time (secs) = 0.62 CPU time per iteration = 0.04 termination code = 0 DIMACS: 2.2e-10 0.0e+00 1.4e-04 0.0e+00 -1.0e+00 2.9e-05

Status: Solved
Optimal value (cvx_optval): -7.53547e+07

Calling SDPT3 4.0: 622 variables, 221 equality constraints For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 221
dim. of socp var = 622, num. of socp blk = 111

SDPT3: Infeasible path-following algorithms

number of iterations = 17 residual of primal infeasibility certificate (y,Z) = 1.21e-11 reldist to infeas. <= 1.63e-12 Total CPU time (secs) = 0.54 CPU time per iteration = 0.03 termination code = 1 DIMACS: 2.4e-10 0.0e+00 1.7e-04 0.0e+00 -1.0e+00 2.0e-05

Status: Unbounded
Optimal value (cvx_optval): -Inf

I replicated your results using SDPT3. On k = 2, cvx_optval = -7.53569e+07. On k = 3, the solver states “sqlp stop: primal problem is suspected of being infeasible” Notice that it doesn’t state that the problem is definitely infeasible (of course, that’s the same message I get when I try it on an actual infeasible problem, such as 1 <= x <= 0). I think it is having numerical difficulty because some of the terms in the sum are abs(x) times 1/sqrt(eps) = abs(x) * 6.7e7… I guess this is giving SDPT3 numerical troubles.

SeDuMi did make it through k = 10, and converged to cvx_optval = 742.242, and was already getting close by k = 3, but was pretty wild on k = 2 (cvx_optbal = 295519). I have no idea whether this converged to the correct answer, but it converged. I’ll let you worry about how to fix things up.

Thank you so much. It works after I switch to SeDumi.

Then I was trying to replace the linear expression with logit with
`minimize (-sum(labelTrain.*log(exp(trainData*x)./(1+exp(trainData*x)))+(1-labelTrain).*log(1-exp(trainData*x)./(1+exp(trainData*x))))+ lambda* sum(abs(x)./(sqrt(abs(beta))+ eps)));`

But it turns out an error

Error using + (line 83)
Disciplined convex programming error:
Illegal operation: {real constant} - {log-concave}

Error in - (line 21)
z = plus( x, y, true, cheat );

Error in test (line 23)
minimize
(-sum(labelTrain.log(exp(trainDatax)./(1+exp(trainDatax)))+(1-labelTrain).log(1-exp(trainDatax)./(1+exp(trainDatax))))+
lambda* sum(abs(x)./(sqrt(abs(beta))+ eps)));

I do not understand this error information and how can I make it work?
Thank you again for your help.

You are in violation of CVX’s rules regarding log-concave functions.

You can find the rules in the CVX 3.0Beta Users Guide at http://web.cvxr.com/cvx/beta/doc/advanced.html#log-convexity . The rules stated there also apply to CVX 2,.1 even though they are not mentioned in the current 2.1 Users’ Guide. They are also discussed in the first answer by mcg in Log of sigmoid function .

“Regular” logistic regression can be done in CVX. See http://cvxr.com/cvx/examples/cvxbook/Ch07_statistical_estim/html/logistics.html for an example.