Develop Branch vs Main Branch of YALMIP: BMIBNB issue

[AS95]

I have this small non-convex optimization problem:

x = sdpvar(2,1);
Objective = log_sum_exp(x);
a = [2;1];
rho = 2;
Constraints = (norm(x-a, 2) <= rho^2);


solution = optimize(Constraints, -Objective, sdpsettings('solver', 'bmibnb'));

This was working in the main version of YALMIP, but the develop version has issues. It gives a lot of errors, and also complains that I am using logsumexp() but should switch to log_sum_exp() which is what I am doing.

Is this an expected thing?

[Johan Löfberg]

There is no command in yalmip called log_sum_exp, and never has been. You must have destroyed your installation, or you have some other software interfering ("which logsumexp")

Runs without problems here when using yalmip code, i.e. logsumep or log(sum(exp(x)))

I am a bit concerned though as it picks mosek as upper bound solver, which shouldn't be possible as the problem isn't exp-cone representable since you maximize a convex function.

* Starting YALMIP global branch & bound.

* Branch-variables : 2

* Upper solver     : MOSEK

* Lower solver     : CPLEX

* LP solver        : CPLEX

 Node       Upper      Gap(%)       Lower    Open

    1 :   -5.787E+00     5.94     -6.203E+00   2  Improved solution  

    2 :   -5.954E+00     3.51     -6.203E+00   3  Improved solution  

    3 :   -6.007E+00     0.26     -6.025E+00   4  Improved solution  

* Finished.  Cost: -6.0068 Gap: 0.25807

* Termination with relative gap satisfied 

* Timing: 2% spent in upper solver (3 problems solved)

*         5% spent in lower solver (7 problems solved)

*         46% spent in LP-based domain reduction (40 problems solved)

I would make sure I use a nonlinear solver here

>> solution = optimize(Constraints, -Objective, sdpsettings('solver', 'bmibnb','bmibnb.uppersolver','fmincon'));

* Starting YALMIP global branch & bound.

* Branch-variables : 2

* Upper solver     : fmincon

* Lower solver     : MOSEK

* LP solver        : SCIP

 Node       Upper      Gap(%)       Lower    Open

    1 :   -6.007E+00     2.76     -6.203E+00   2  Improved solution  

    2 :   -6.007E+00     2.76     -6.203E+00   3    

    3 :   -6.007E+00     2.48     -6.183E+00   2  Infeasible  

    4 :   -6.007E+00     2.48     -6.183E+00   3    

    5 :   -6.007E+00     0.44     -6.038E+00   2  Poor bound  

* Finished.  Cost: -6.0068 Gap: 0.44374

* Termination with relative gap satisfied 

* Timing: 57% spent in upper solver (3 problems solved)

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

*         39% spent in LP-based domain reduction (38 problems solved)

[Mark L. Stone]

log_sum_exp is a CVX command. 

More confusingly, there is also a logsumexp command in CVX which tells you to use log_sum_exp and then calls log_sum_exp .With CVX ahead of YALMIP in the path, attempts to use logsumexp in YALMIP fail.

The same also applies to geo_mean and geomean in CVX.

My "solution" is to delete (or rename out of effective existence) the CVX functions, logsumexp and geomean .

[Johan Löfberg]

Ok, problem solved then

[Johan Löfberg]

my concern there was false alarm. YALMIP does indeed select mosek for the nonconvex case thinking it will be able to exp-cone represent the logsum exp, but it never uses this incorrectly during the branching process. It will only lead to no upper bound solutions being made available from the selected upper bound solver (but YALMIP is able to construct a good solution rather quickly from the lower bound relaxations anyway in this particular case)

[AS95]

Great, thank you!! Is there an easy way to obtain the best lower and upper bound values found by bmibnb? 

[Johan Löfberg]

solution = optimize(Constraints, -Objective, sdpsettings('solver', 'bmibnb','savesolveroutput',1));
solution.solveroutput
ans =


  struct with fields:


         lower: -6.0325
    lower_hist: [-6.2028 -6.2028 -6.1853 -6.1853 -6.0325]
    upper_hist: [-5.7877 -5.9914 -5.9914 -5.9914 -6.0068]

[AS95]

Thank you very much!

[AS95]

There is no lower_hist or upper_hist in other solvers like IPOPT. I guess this is because they are using interior point methods and stopping at the first local optimum. Can I always obtain upper and lower values with global solvers, e.g., BARON? Sorry for the off-topic questions, I am going to stop now:)!

[Johan Löfberg]

If they don't output it when turning on savesolveroutput then it is not available (although it is a bit odd that you talk about ipopt in this context as it is not a global solver, however ipopt is primal-dual solver as far as I remember hence it has a similar concept for convex problems)

[AS95]

Thank you. The reason I talk about ipopt is such a problem is solvable by a general purpose nonlinear solver, not CPLEX GUROBI or MOSEK, so I just wanted to find methods to compare lower&upper bounds given by many solvers.

[Johan Löfberg]

these bound only make sense in global solvers