I had an exam question today and want to check if my answer is right or if there was a mistake...

Consider the following convex optimisation problem:

$$\begin{array}{ll} \text{minimize} & - \ln(1+x_1)- \ln(\frac{3}{2}+x_2)- \ln(4+x_3)\\ \text{subject to} & x_1+x_2+x_3=1\\ & x_1, x_2, x_3\geq0\end{array}$$

I got that the dual has optimal solution $\lambda =\frac{2}{5}$ and $x=(\frac{3}{2},1, -\frac{3}{2})$. However, obviously, the third variable violates its constraint. I'm thinking either I got the answer wrong or the question was wrong! Can someone help me here?

  • $\begingroup$ You should share your work on this, so that we can see where you might have gone astray. $\endgroup$ – Michael Grant Jun 7 '17 at 12:36

I am sorry to tell you this, but you did not get the correct answer (which I guess you already know since you have $x_3<0$ in your solution). The correct solution is

$$ x_1 = \frac{3}{4}\\ x_2 = \frac{1}{4}\\ x_3 = 0 $$

You can find this answer just by reasoning. How? Well as you know, $\ln(x)$ has a negative second derivative. This means that an increase in $x$, say $\Delta x$, will have less impact on $\ln(x)$ for larger values of $x$ than for smaller. You can interpret the first constraint as a resource constraint. Thus, you have a total of $1$ to distribute over the three non-negative variables. If you give all your resources to $x_1$ it will still not "catch up" to $\ln(4)$. The same goes for $x_2$. So there is little point in giving any resources to $x_3$, thus $x_3=0$. Now the best way of distributing the resources between $x_1$ and $x_2$ is to make the two first terms equal (due to the negative second derivative). Thus solving $$ \ln(1+x_1)=\ln(\frac{3}{2}+x_2) \text{ for $x_1+x_2=1$, and $x_1,x_2\geq0$} $$ yielding $$ x_1=\frac{3}{4}\\ x_2= \frac{1}{4} $$ So the result can be derived just by realizing that the second derivative of $\ln{x}$ is negative. Hope this was helpful!


Question is correct but your answer is not! If you put more detail here about your solution I can explain why you got wrong answer. Anyway here it is my guess about your solution:

The problem is a convex optimization over compact constraint, and slater CQ holds therefore, $x^* $ is an optimal solution iff $x^*$ is KKT point. so if you set up KKT sys, you get a simple system of non linear equations and inequalities including the primal inequality i.e., $x=(x_1,x_2,x_3) \ge 0$. So if you have taken into account the later inequality you should have came up right answer which satisfies non-negativity condition! I bet you didn't consider this condition....

  • $\begingroup$ And what is this answer you speak of? $\endgroup$ – Vladimir Nabokov Jun 7 '17 at 7:18
  • $\begingroup$ down voter care to comment ? $\endgroup$ – Red shoes Jun 8 '17 at 4:38

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.