1
$\begingroup$

Given $a_1$ and $a_2$ such that $a_1\geq a_2\geq1$, solve the following problem in variables $x_1, x_2, y$

$$\begin{array}{ll} \text{minimize} & x_1+x_2\\\text{subject to} & x_1x_2\geq a_1,\\&\frac{x_1x_2}{y}\geq a_2,\\&x_1\geq y\geq x_2>0\end{array}$$


My attempt:

First rewrite the problem:

\begin{array}{ll} \text{minimize} & x_1+x_2\\ x_1,x_2,y\\\text{subject to} & x_1x_2\geq a_1,\\&x_1x_2\geq ya_2,\\&x_1\geq y,\\&y\geq x_2,\\&x_2>0.\end{array} Lagrange multiplier:

$L(x_1,x_2,y,\lambda_i)=x_1+x_2+\lambda_1(a_1-x_1x_2)+\lambda_2(ya_2-x_1x_2)+\lambda_3(y-x_1)+\lambda_4(x_2-y)-\lambda_5x_2.$

$\begin{bmatrix}\frac{\partial{L}}{\partial{x_1}} \\ \frac{\partial{L}}{\partial{x_2}} \\ \frac{\partial{L}}{\partial{y}}\end{bmatrix} = \begin{bmatrix}1-\lambda_1x_2-\lambda_2x_2-\lambda_3 \\ 1-\lambda_1x_1-\lambda_2x_1+\lambda_4-\lambda_5 \\ \lambda_2a_2+\lambda_3-\lambda_4\end{bmatrix}\Longrightarrow\begin{cases} x_2=\frac{1+\lambda_3}{\lambda_1+\lambda_2}, \\ x_1=\frac{1+\lambda_4-\lambda_5}{\lambda_1+\lambda_2},\\\lambda_4=a_2\lambda_2+\lambda_3. \end{cases}$

$g(\lambda) = \inf_{x_1,x_2,y} L(x_1,x_2,y,\lambda_i) = \frac{1+\lambda_4-\lambda_5}{\lambda_1+\lambda_2}+\frac{1+\lambda_3}{\lambda_1+\lambda_2}+\lambda_1(a_1-\frac{1+\lambda_4-\lambda_5}{\lambda_1+\lambda_2}\frac{1+\lambda_3}{\lambda_1+\lambda_2})-\lambda_2\frac{1+\lambda_4-\lambda_5}{\lambda_1+\lambda_2}\frac{1+\lambda_3}{\lambda_1+\lambda_2}-\lambda_3\frac{1+\lambda_4-\lambda_5}{\lambda_1+\lambda_2}+\lambda_4\frac{1+\lambda_3}{\lambda_1+\lambda_2}-\lambda_5\frac{1+\lambda_3}{\lambda_1+\lambda_2}.$

Dual problem:

\begin{array}{ll} \text{maximize} & g(\lambda) \\\quad \lambda\\ \text{subject to} & \lambda_i \geq 0,\\&\lambda_4=a_2\lambda_2+\lambda_3. \end{array}

$\endgroup$
  • $\begingroup$ Think of the determinant of a $2 \times 2$ matrix. $\endgroup$ – Rodrigo de Azevedo Jan 10 at 7:21
  • 1
    $\begingroup$ Look at Sylvester's criterion, then. Your two inequality constraints can be rewritten as linear matrix inequalities (LMIs), which can then be merged into a single LMI. Since the objective is linear, you have a semidefinite program, which should not be hard to solve numerically. $\endgroup$ – Rodrigo de Azevedo Jan 10 at 9:24
  • 1
    $\begingroup$ From Sylvester's criterion, the LMI $$\begin{bmatrix} x_1 & \sqrt{a_1}\\ \sqrt{a_1} & x_2\end{bmatrix} \succeq 0$$ contains the inequalities $x_1 \geq 0$, $x_2 \geq 0$ and $x_1 x_2 \geq a_1$. Can you take it from here? $\endgroup$ – Rodrigo de Azevedo Jan 10 at 10:24
  • 1
    $\begingroup$ If you don't use @ I am not notified of replies. The 2nd one is wrong. It is not an LMI. You have to use some trick like $z := \sqrt{y}$ and move $z$ to the off-diagonals. The 3rd constraint is the conjunction of two linear inequality constraints, which is easy. Once all is done, you have a (convex) semidefinite program that can be solved using, say, CVX or CVXPY. $\endgroup$ – Rodrigo de Azevedo Jan 10 at 11:13
  • 1
    $\begingroup$ @RodrigodeAzevedo thank you, I managed to use CVX. Answer below is indeed correct. $\endgroup$ – Lee Jan 13 at 7:29
1
$\begingroup$

We want to minimize $x_1+x_2$ and $x_1,x_2 \ge 0$, so we have to get close to origin as much as possible. Consider the problems in $x_1-x_2$ plane, first we have to find the feasible region (I am assuming $a_1,a_2\ge0$):

enter image description here

The blue curve is the boundary of the first inequality $x_1 x_2 \ge a_1$, the feasible region is the region above this curve. The dashed-line orange curves are the second inequality $x_1x_2\ge ya_2$ for different values of $y$, again the area above these curves are the feasible region. This means if $y\le\frac{a_1}{a_2}$, we can ignore the second inequality, otherwise (if $y\ge\frac{a_1}{a_2}$) we can ignore the first inequality. The purple vector shows the direction of movement of curves as we increase $y$. Then we have the third inequality $x_1 \ge y$ which has the boundary of green line, our answer is in the right hand side of green line. And finally we have the forth inequality $x_2 \le y$ with boundary of grey line, our answer is in lower half of this line (below grey line).

With these information at hand, we see that the inequality $x_1\ge y$ must become active at solution point, this means the slackness condition $\lambda_4(y-x_1)=0$ is equivalent to $x_1=y$. Substituting this in the primal, we get three inequalities $x_2 \ge \frac{a_1}{y}$, $y\ge x_2$ and $x_2 \ge a_2$ and the objective is $y+x_2=x_1+x_2$.

Back to primal. Now consider on one hand we have we have $y\ge x_2$ and $x_2 \ge \frac{a_1}{y}$ which means $y \ge \frac{a_1}{y}$ or $y \ge \sqrt{a_1}$. On the other hand we have $y\ge x_2$ and $x_2 \ge a_2$which means $y\ge a_2$. Thus we obtain two main conditions that solves everything: $y \ge \sqrt{a_1}$ and $y\ge a_2$.

Finally if $a_2 \le \sqrt{a_1}$ the solution is $x_1=y=x_2=\sqrt{a_1}$. Otherwise if $\sqrt{a_1} \le a_2$ the solution is $x_1=x_2=y=a_2$. And now we can see the funny part, both $x_1 \ge y$ and $y \ge x_2$ are tight so from start we could have considered the slackness conditions $\lambda_3(y-x_1)=0$ and $\lambda_4(x_2-y)=0$ to be active i.e. $x_1=x_2=y$ to be true and get the solution.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you! this is correct, I got the same results in simulation $\endgroup$ – Lee Jan 13 at 7:30

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.