BMIBNB global optimum found?

38 views
Skip to first unread message

researcher

unread,
Aug 4, 2020, 1:21:34 PM8/4/20
to YALMIP
I'm trying to find the global optimum a nonconvex problem using BMIBNB, and the output is this one:


+ Solver chosen : BMIBNB
+ Processing objective function
+ Processing constraints
+ Branch and bound started
+ Calling FMINCON
...
+ Calling LINPROG
* Starting YALMIP global branch & bound.
* Branch-variables : 84
* Upper solver     : fmincon
* Lower solver     : fmincon
* LP solver        : LINPROG
* Warning: 84 branch variables are unbounded from below
* Warning: 84 branch variables are unbounded from above
 Node       Upper      Gap(%)       Lower    Open
+ Calling LINPROG
...
+ Calling LINPROG
+ Calling FMINCON
    1 :   -3.319E-01     0.00     -3.319E-01   0  Infeasible  
* Finished.  Cost: -0.33187 Gap: 0
* Termination with all nodes pruned 
* Timing: 58% spent in upper solver (1 problems solved)
*         9% spent in lower solver (169 problems solved)
*         8% spent in LP-based domain reduction (48 problems solved)

result = 

  struct with fields:

    yalmipversion: '20200116'
       yalmiptime: 0.5609
       solvertime: 4.3685
             info: 'Successfully solved (BMIBNB)'
          problem: 0
      solverinput: []

Does this guarantee that the global optimum has been found for this problem? 
The reason I'm asking this is because it says "Infeasible" when calling fmincon, even when the residuals of the solution found are these ones (within the fmincon tolerance 1e-11 that I'm using):
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|    ID|                            Constraint|   Primal residual|   Dual residual|
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|    #1|    Elementwise inequality (quadratic)|        6.7152e-12|             NaN|
|    #2|                Elementwise inequality|        1.2037e-05|             NaN|
|    #3|    Elementwise inequality (quadratic)|        1.1201e-06|             NaN|
|    #4|                Elementwise inequality|           0.43064|             NaN|
|    #5|    Elementwise inequality (quadratic)|        1.1202e-06|             NaN|
|    #6|                Elementwise inequality|           0.43061|             NaN|
|    #7|    Elementwise inequality (quadratic)|        4.2142e-12|             NaN|
|    #8|                Elementwise inequality|        1.0081e-05|             NaN|
|    #9|    Elementwise inequality (quadratic)|        1.1206e-06|             NaN|
|   #10|                Elementwise inequality|            1.3345|             NaN|
|   #11|    Elementwise inequality (quadratic)|        7.2245e-12|             NaN|
|   #12|                Elementwise inequality|        9.1685e-06|             NaN|
|   #13|    Elementwise inequality (quadratic)|        2.5386e-13|             NaN|
|   #14|                Elementwise inequality|        3.1141e-06|             NaN|
|   #15|    Elementwise inequality (quadratic)|        1.1206e-06|             NaN|
|   #16|                Elementwise inequality|            1.3345|             NaN|
|   #17|                   Equality constraint|       -7.7727e-13|             NaN|
|   #18|                   Equality constraint|       -3.4615e-12|             NaN|
|   #19|   Elementwise inequality (polynomial)|           0.13187|             NaN|

 I've also tried to use a different lower solver (I'm using fmincon right now), but when I try mosek or gurobi it says "No suitable solver", and with snopt or sdpt3 it doesn't converge. 

Thanks

Johan Löfberg

unread,
Aug 4, 2020, 1:51:43 PM8/4/20
to YALMIP
Yes, a solution with objective -.3319 has been found, and it's been proven there is no better solution (unless there are bugs etc of course, the global optimality is never more safe than the trust in the solver)

The fact that fmincon fails to find a solution says nothing (that's precisely why you use a global solver)

lpsolver/lowersolver should work with mosek whih also is much preferred over linprog. If not, you should post a reproducible example as that indicates a bug or something)
Reply all
Reply to author
Forward
0 new messages