# Minimize $x_1 + x_2$ subject to inequality constraints

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}$$

• Think of the determinant of a $2 \times 2$ matrix. Jan 10 '20 at 7:21
• 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. Jan 10 '20 at 9:24
• 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? Jan 10 '20 at 10:24
• 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. Jan 10 '20 at 11:13
• @RodrigodeAzevedo thank you, I managed to use CVX. Answer below is indeed correct.
– Lee
Jan 13 '20 at 7:29

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$$):

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.

• thank you! this is correct, I got the same results in simulation
– Lee
Jan 13 '20 at 7:30