I have the following optimization problem where $K>0$. \begin{align*} \min_{y_1,\ y_2\ge 0} 2k(\exp(-y_1)+\exp(-\min(y_1,y_2)))+2y_1+y_2. \end{align*}

I divided into two cases:

Case 1: $y_1\le y_2$: \begin{align*} \min_{\substack{y_1,\ y_2\ge 0}} 4k\exp(-y_1)+2y_1+y_2. \end{align*} Assuming Lagrange multipliers $\lambda_1\ge 0$, $\lambda_2\ge 0$, corr. to the constraints $y_1,y_2\ge 0$, the KKT conditions: \begin{align*} -4k\exp(-y_1)+2-\lambda_1 &= 0\\ 1-\lambda_2=0 \end{align*} From the second equation, $\lambda_2=1$, by complementary slackness, $y_2^*=0$, and since $y_1\le y_2$, $y_1^*=0$, and so $-4k+2=\lambda_1$. Since $\lambda_1\ge 0$, this solution is possible for $k\le0.5$, else there is no solution for this case.

Case 2: $y_1\ge y_2$: \begin{align*} \min_{\substack{y_1,\ y_2\ge 0}} 2k\exp(-y_1)+2k\exp(-y_2)+2y_1+y_2. \end{align*}

The KKT conditions: \begin{align*} -2k\exp(-y_1)+2-\lambda_1 &= 0\\ -2k\exp(-y_2)+1-\lambda_2 &= 0 \end{align*}

For $\lambda_1=0$ and $\lambda_2=0$, I get $y_1^*=\log(k)$ and $y_2^*=\log(2k)$ and this violates the constraint. If $y_1^*=\log(k)$ and $y_2^*=0$, $\lambda_2=-2k+1$, and this holds only for $k\le 1/2$.

I get two solutions $(0,0)$ and $(\log(k),0)$ for $k\le 0.5$ and no solutions for $k\ge 0.5$. To find the best among these two solutions, I compare the objective values: $4k$ for $(0,0)$ and $2(1+k+\log(k))$ for $(\log(k),0)$. For $k\le 0.5$, the latter is smaller always, and the unique solution is $(\log(k),0)$.

Is this working correct?

  • $\begingroup$ $(0,0)$ is also a solution to the second case (as it should be, since $y_1=y_2$ falls in both categories). $\endgroup$
    – LinAlg
    Oct 3, 2018 at 18:22
  • $\begingroup$ you may miss points on the boundary, you should add the constraint $y_1\geq y_2$ with a Lagrange multiplier $\endgroup$
    – LinAlg
    Oct 3, 2018 at 18:50
  • $\begingroup$ @LinAlg: Thanks, but arguing with three Lagrange multipliers was difficult. Do you find any error in the above working (apart from (0,0))? $\endgroup$
    – Esha
    Oct 3, 2018 at 19:05
  • $\begingroup$ The math checks out, but the method is incorrect since you omit the boundary. The analysis should not be much harder; just distinguish between $\lambda_3=0$ and $\lambda_3>0$. $\endgroup$
    – LinAlg
    Oct 3, 2018 at 19:17


You must log in to answer this question.