3
$\begingroup$

I have a convex objective function, e.g., minimizing the negative entropy function. My constraints are also linear. The only issue is that I also have binary variables.

I am currently aware of AIMMS's outer approximation (AOA) that is said to be a good options. My questions are:

  1. Is such an outer approximation method using another solver to solve each relaxed problem? For example, if the variables were continuous, then minimizing the negative entropy function would be solved with MOSEK. Do you think solvers like AOA will still use MOSEK but will apply some sort of branch&bounding?
  2. What other options than AOA do I have? I prefer using MATLAB and YALMIP.
$\endgroup$
6
$\begingroup$

Mosek 9.x can natively solve mixed-integer exponential cone problems.

Formulate the problem in YALMIP, specifying the binary variables as binvar, and Mosek as the solver. YALMIP will call Mosek to exploit its native mixed-integer exponential cone capability.

Here is a mixed-integer example (mixture of binary and continuous):

x = binvar(3,1); % binary
y = sdpvar(2,1); % continuous
optimize([A*[x;y] <= b,0 <= y <= 1],-entropy([x;y]),sdpsettings('solver','mosek'))
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Wow! That MOSEK... $\endgroup$ – independentvariable Apr 4 at 16:28
  • 1
    $\begingroup$ You can also throw in some Second Order Cone constraints, it you're feeling chipper. BTW, this can also be solved in CVX 2.2, with Mosek 9.x as solver, and will utilize Mosek's native mixed-integer exponential cone capability. CVXPY as well. $\endgroup$ – Mark L. Stone Apr 4 at 16:32
  • $\begingroup$ Actually I dont have binary variables but a negative one norm in the objective function. I know that YALMIP logical modelling will hopefully first reformulate this with binary variables and then call MOSEK. $\endgroup$ – independentvariable Apr 4 at 17:21
  • 1
    $\begingroup$ Yes, that works in YALMIP. CVX would require you to manually do the logic (Big M) modeling. $\endgroup$ – Mark L. Stone Apr 4 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.