BARON Problem 3

[Aras]

Hi!!

I am using Baron with: 

P = optimize(Constraints,-Objective,sdpsettings('solver','baron', 'baron.maxtime', 999999))

However, I get the following error:

 *** Normal completion ***             

 

 Wall clock time:                   111.50 

 Total CPU time used:               111.31 

 

 Total no. of BaR iterations:       1 

 Best solution found at node:      -1 

 Max. no. of nodes in memory:       1 

  

 All done 

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

P = 

  struct with fields:

    yalmipversion: '20190425'

       yalmiptime: 0.1313

       solvertime: 111.7707

             info: 'Maximum iterations or time limit exceeded (BARON)'

          problem: 3

Is there any option other than maxtime to prevent this? I think maxiter: -1 is a correct option.

[Johan Löfberg]

It is not clear what has happened, looks like it has terminated successfully, but returned a weird code? Impossible to answer without reproducible code.

[Aras]

I get this Problem 3 error most of the time from BARON. IPOPT and Knitro terminate successfully (but they are local solvers so maybe in globality I am doing a mistake).

I added one example. Sorry for the trouble. After loading this mat-file I run:

function [Objective, x, time,prob] = opt_solver(D,d,A,b)
n = size(D,2);
x = sdpvar(n,1);
Objective = (logsumexp(A*x+b));
Constraints = [D*x <= d, x>= 0];
P = optimize(Constraints,-Objective,sdpsettings('solver','baron'));
%P = optimize(Constraints,-Objective,sdpsettings('solver','knitro','knitro.optionsfile','fileopt.txt'));
%P = optimize(Constraints,-Objective,sdpsettings('solver','knitro', 'verbose',0));
%P = optimize(Constraints,-Objective,sdpsettings('solver','ipopt','ipopt.max_iter',999999, 'ipopt.max_cpu_time',999999));


x = value(x); Objective = value(Objective); time = P.solvertime; prob = P.problem;
end

[Aras]

Of course, the run command is:

 opt_solver(D,d,A,b)

[Johan Löfberg]

Yes, the code returned by baron is misinterpreted. The correct baron status is "Intermediate feasible" as seen when extracting everything (not sure what I should map that to)

  struct with fields:

       Model_Status: 'Intermediate feasible'

       BARON_Status: 'Normal completion'

         Total_Time: 24.4000

     BaR_Iterations: 1

          Best_Node: 1

    Max_Nodes_InMem: 1

        Lower_Bound: -1.0000e+51

        Upper_Bound: -76.0362

         Bad_Bounds: 'Missing 2 bounds! Global Optimality not Guaranteed.'

     Unbounded_Rays: 0

                IIS: [0 0]

[Johan Löfberg]

A bit surprising though that baron doesn't manage to fix the lower bound. YALMIPs global solver solves it easily to global optimality

* Starting YALMIP global branch & bound.

* Branch-variables : 30

* Upper solver     : knitro

* Lower solver     : GUROBI

* LP solver        : GUROBI

 Node       Upper      Gap(%)       Lower    Open

    1 :   -7.604E+01     0.77     -7.663E+01   2  Improved solution  

* Finished.  Cost: -76.0362 Gap: 0.77064

* Termination with relative gap satisfied 

* Timing: 40% spent in upper solver (1 problems solved)

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

*         33% spent in LP-based domain reduction (120 problems solved)

P = 

  struct with fields:

    yalmipversion: '20190425'

       yalmiptime: 0.0890

       solvertime: 1.5020

             info: 'Successfully solved (BMIBNB)'

          problem: 0

could be related to the fact that YALMIP works with the logsumexp operator as an operator, while baron works with the individual exp/log functions in a disaggregated way

[Johan Löfberg]

Hmm, although that solution is sub-optimal. Appears to be some bug in the logsumexp use inside bmibnb

[Johan Löfberg]

scratch that, missed it was a maximization problem

[Aras]

Ah, yes it is a convex maximization problem. Shall I change logsumexp to the classical way? Or is there a way to fix this?

[Johan Löfberg]

yalmip automatically flattens the logsumexp operator to log(sum(exp)) when calling baron as it doesn't support anything else (the model is normalized to z==Ax+b and then the objective in baron is -log(sum(exp(zi)), and then it turns out that baron struggles with bound propagation on those variables)

bmibnb simply performs better here.

[Aras]

Thank you very very much. Do you think the reason is just Baron is poor in these problems? Can I assume I am doing the correct thing and even if I model this directly with Baron the result will be poor again?

[Johan Löfberg]

The problem is that baron works with exp(z) and the bound on z is somewhere around 60

z = sdpvar(length(b),1);

Constraints = [D*x <= d, x >= 0, z == A*x+b];

[~,l,u] = boundingbox(Constraints)

Hence, when working in the branch tree with these terms, it will fail as they are infinite, i.e. unbounded, and thus the log result is also unbounded

yalmip on the other hand will never touch the intermediate exp expressions, but work with the map from z to log output