Re: Model not available in objective at level 4 error

[Johan Löfberg]

When you use the operator norm, you implicitly tell YALMIP that this is SOCP-representable, which it isn't.

Hence, you have to write the norm explicitly, i.e., instead of norm(x-y) use sqrtm((x-y)'(x-y))

bmibnb solves this nonconvex problem in 3 iterations

[Jack]

Thank you so much for that. I changed the norm in my "g" function accordingly and did the following

% Define variables

x1 = sdpvar(2,1); x2 = sdpvar(2,1);

f = @(y) g(x1,y)+g(x2,y)-g(x1,y)*g(x2,y); 

% Define constraints and objective

Constraints = [x1(1)+x1(2) <= C, x1 >= 0, x2(1)+x2(2) <= C, x2 >= 0, sqrtm((x1-x2)'*(x1-x2)) >= l];

Objective = -(log(f(y1))+log(f(y2)));

% Set some options for YALMIP and solver

options = sdpsettings('verbose',1,'solver','bmibnb');

% Solve the problem

sol = optimize(Constraints,Objective,options);

However, I get the error

info: 'Infeasible problem (BMIBNB)'

If you can kindly point me where I may be mistaken. Also, I read that this solver is not global, but can I still say something about the optimality of it? does the gap give an idea about this? Can you direct me to something simple to understand where I  can understand better how this solver works? thank you again.

[Jack]

I found a nice discussion on the solver here

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Solvers.BMIBNBTheory

:-) Would I quantify the degree of optimality of the solution via the gap? Looking forward to hearing from you. 

[Johan Löfberg]

works here

most likely you don't have any good lp solver. your lp solver fails miserably and thinks a relaxation is feasible

[Johan Löfberg]

the gap tells you precisely how far from optimality you can be, if the computed solution isn't optimal

[Jack]

thank you again. which solver would you suggest that I need? just need to get this work....is there something freely available? I have SDPT3 and SEUDMI...do I need PENBI? 

[Johan Löfberg]

lp solver? gurobi, mosek, cplex, scip, etc etc

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Category.LinearProgrammingSolver

[Jack]

I downloaded the solvers from TomLab and when I debugged an error, I got

 

info: 'Solver not applicable (gurobi)'

I also received the license from them, but I am not sure if it was only for gurobi? any advice on this....sorry, I am not sure. 

[Jack]

I also tried MOSEK and I am getting infeasible problem :( Can you please tell me which solver worked for you?  

[Johan Löfberg]

YALMIP doesn't support stuff from Tomlab

Why don't you simply download gurobi from gurobi?

And from the error message above, it looks like you've tried to solve the problem using gurobi. that is impossible as gurobi is a MISOCP solver, not a general nonlinear solver. YALMIP needs the LP solver inside bmibnb to solve the LP relaxations

[Johan Löfberg]

Are you sure you really used mosek? Did bmibnb display that in its header print out?

I tried with mosek, and got a strange crash, which I have to investigate.

[Johan Löfberg]

The crash appears to be related to a new license file. Now it worked, and I get infeasibility also. Most likely a numerical issue due to bad numbers in your model 

The problem is not infeasible, as you can see with mosek, if you simply solve the feasibility problem

sol = optimize(Constraints,[],sdpsettings(options,'debug',1))

Hence, something numerical is happening with the LP relaxations of the objective function

[Jack]

thank you for your reply. I am using gurobi now for the lower/LP solver and fmincon for upper. I get a solution after about 70 iterations

with output (should it take this long?)

* Starting YALMIP global branch & bound.

* Branch-variables : 17

* Upper solver     : fmincon

* Lower solver     : GUROBI

* LP solver        : GUROBI

 Node       Upper      Gap(%)       Lower    Open

    1 :   -8.134E-04    60.26     -8.639E-01   2  Improved solution  

    2 :   -8.134E-04    60.26     -8.639E-01   3    

    3 :   -8.134E-04    10.45     -1.112E-01   4    

    4 :   -8.134E-04    10.45     -1.112E-01   5    

   65 :   -8.134E-04    15.62     -1.704E-01  50    

   66 :   -8.134E-04    15.62     -1.704E-01  51    

   67 :   -8.134E-04    15.62     -1.704E-01  52    

   68 :   -8.134E-04    15.62     -1.704E-01  53    

   69 :   -1.678E-01     0.09     -1.689E-01  16  Improved solution  

* Finished.  Cost: -0.1678 Gap: 0.091853

* Timing: 80% spent in upper solver (61 problems solved)

*         1% spent in lower solver (95 problems solved)

*         13% spent in LP-based domain reduction (1429 problems solved)

My cost is negative and it should be positive since this is a probability so I am not sure here. I negated the objective (since I want to maximize originally) to put in YALMIP.

this is my code:

R_min = 200e3;

y1 = [R_min; 100e3];

y2 = [R_min+100e3; 200e3];

C = 100e3;

l = 4e3;

b = 1.041;

c = 2.583e5;

d = 1.221e4;

g = @(x,y) b./(1+exp((sqrtm((x-y)'*(x-y))-c)/d));

% Define variables

x1 = sdpvar(2,1); x2 = sdpvar(2,1);       

f = @(y) g(x1,y)+g(x2,y)-g(x1,y)*g(x2,y); 

% Define constraints and objective

Constraints = [x1(1)+x1(2) <= C, x1 >= 0, x2(1)+x2(2) <= C, x2 >= 0, sqrtm((x1-x2)'*(x1-x2)) >= l];

Objective = -(f(y1))*(f(y2));

% Set some options for YALMIP and solver

options = sdpsettings('verbose',1,'solver','bmibnb');

% Solve the problem

sol = optimize(Constraints,Objective,options);

kindly help me with this. thank you again 

[Jack]

for some reason MOSEK doesn't even come into the solver even though i added its path. only gurobi comes in.

do I need to do something else with 

options = sdpsettings('verbose',1,'solver','bmibnb')

to make MOSEK come in? 

[Johan Löfberg]

Wrong mex? Added wrong directory?

>> which mosekopt

C:\Program Files\Mosek\7\toolbox\r2013aom\mosekopt.mexw64

[Johan Löfberg]

I don't have gurobi here

Is the computed solution feasible? What is the objective value of the solution.

With a complex objective like this, a lot of reformulations are done internally to get it in a computable canonical format, and along that, internal equality constrints are introduced, and with the bad numbers in the objective, it could be that small violations of those intermediate equalities lead to negative objectives

[Jack]

yup, the solution is improved according to the output:

69 :   -1.678E-01     0.09     -1.689E-01  16  Improved solution  

* Finished.  Cost: -0.1678 Gap: 0.091853

* Timing: 80% spent in upper solver (61 problems solved)

*         1% spent in lower solver (95 problems solved)

*         13% spent in LP-based domain reduction (1429 problems solved) 

the cost for both my max and min problems would be  -0.1678...is that correct? since I am minimizing the negative of the original objective. Should I scale my problem to get rid of the big numbers?

===================

for the MOSEK, I get

>> which mosekopt

C:\Users\Jack\mosek\7\toolbox\r2013a\mosekopt.mexw64

should it be aom? On their website, they said to use r2013a

[Johan Löfberg]

bmibnb has found a solution with objective -0.1678, and proves (within numerical issues) that the global objective, if the computed solution isn't globally optimal) has an optimal value of no less than -0.1689. The solution is thus guaranteed to be within 0.09% from optimalilty

Yes, a reformulation which gets rid of ugly numbers is recommended. The LP relaxations involve numbers on the order of 1e11, causing issues for many solvers.