2
$\begingroup$

I have following optimization problem $$\underbrace{\max}_{x,y,u,v,\eta} \eta \\ \text{s.t: } u\log(1+ax)\geq \eta \\ v\log(1+by)\geq\eta\\ u+v\leq1\\ux+vy\leq c\\x\geq0\\y\geq 0$$ where $a,b,c$ are some positive constants. Any help in this regard will be much appreciated. Thanks in advance.

$\endgroup$
  • $\begingroup$ what about $a$ and $b$? No constraints? $\endgroup$ – sredni vashtar Apr 6 '18 at 5:34
  • $\begingroup$ @Sun edited. $a,b$ are constants $\endgroup$ – Frank Moses Apr 6 '18 at 5:40
  • $\begingroup$ Is $ux+uy\le c$ perhaps a typo for $ux+vy\le c$? I just ask because it breaks the $u-v$ symmetry I see in the other inequalities. $\endgroup$ – saulspatz Apr 6 '18 at 5:49
  • $\begingroup$ @saulspatz spot on. It was a typo. Corrected now. $\endgroup$ – Frank Moses Apr 6 '18 at 6:13
  • $\begingroup$ It seems plausible that the optimum occurs when all the constraints (except $x,y\ge0$) are active, i.e. $u\log(1+ax)=\eta=v\log(1+by)$, $u+v=1$, $ux+vy=c$. Have you tried writing out the KKT conditions? $\endgroup$ – user856 Apr 6 '18 at 6:59
2
$\begingroup$

Depends on what you mean with possible? Of course you can just throw the problem at any nonlinear solver. Here I use the MATLAB toolbox YALMIP (disclaimer, developed by me) and use its internal spatial branch&bound global solver to compute a globally optimal solution. The global solver requires bounds on all variables, so I just added some without much thought, I think you can derive valid upper bounds on $x$ and $y$ easily from the bounds you have.

The globally optimal solution is the solution that the local solver computes in the first iteration, hence the problem is probably fairly easy, and all effort spent (1 second) is basically just to prove optimality. Same thing when I use the global solver in the package SCIP.

a = 1; b = 2; c = 3;
sdpvar x y u v eta

Model = [u*log(1+a*x) >= eta, v*log(1+b*y) >= eta, u+v <= 1, u*x + v*y <= c];
Model = [Model, 0 <= [x y ] <= 100, 0 <= [u v] <= 1]
Objective = -eta;
optimize(Model,Objective,sdpsettings('solver','bmibnb'))
| cite | improve this answer | |
$\endgroup$

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.