Consider the following quadratic program

$$\begin{array}{ll} \underset{x_1,x_2,x_3}{\text{minimize}} & x_1 x_2 +\frac{1}{2} x_1^2 + \frac32 x_2^2 + 2 x_3^2 + 2 x_1 + x_2 + 3x_3\\ \text{subject to} & x_1 + x_2 + x_3 = 1\\ & x_1 - x_2=0\\ & x_1, x_2, x_3 \geq 0\end{array}$$

First, I want to check if the objective function is convex. I did this by finding the eigenvalues and they were all positive so this is positive definite and is strictly convex.

Now, I am trying to show that $x^*=(\frac12, \frac12, 0)$ is an optimal solution to this problem by finding vectors $y$ and $s$ that satisfy the optimality conditions jointly with $x^*$. I think this should be done via Primal-Dual Interior-Point Method but I am not much familiar with this approach and am pretty confused.

Thanks for your help in advance!

  • 2
    $\begingroup$ What have you tried? $\endgroup$
    – Igor Rivin
    Apr 18 at 20:13
  • $\begingroup$ Do you mean $x_1x_2+ x_1^2+ (3/2x_2^2)+ 2x_2^2+ 2x_3^2+ 2x_1+ x_2+3x_1$ or $(x_1x_2+ x_1^2+ 3)/(2x_2^2+ 2x_2^2+ 2x_3^2+ 2x_1+ x_2+3x_1)$? And should that last "$3x_1$" be "$3x_3$"? If not, $2x_1+ 3x_1= 5x_1$! $\endgroup$
    – user247327
    Apr 18 at 20:30
  • $\begingroup$ @IgorRivin I don't know how to approach it tbh. $\endgroup$
    – statwoman
    Apr 18 at 23:22
  • $\begingroup$ Yes, I just edited it, thanks for letting me know. @user247327 $\endgroup$
    – statwoman
    Apr 18 at 23:23

Well, first, from $x_1- x_2= 0$, $x_1= x_2$ of course so we can write the expression to be minimized as $x_1^2+ x_1^2+ \frac{3}{2}x_1^2+ 2x_3^2+ 2x_1+ x_1+ 3x_3= \frac{7}{2}x_1^2+ 3x_1+ 3x_3$

And from $x_1+ x_2+ x_3= 2x_1+ x_3= 1$, $x_3= 1- 2x_1$

So we can write the expression as a function, $\frac{7}{2}x_1^2+ 3x_1+ 3- 6x_1= \frac{7}{2}x_1^2- 3x_1+ 3$, of the single variable $x_1$!

That will have an extremum where $7x_1- 3= 0$ so at $x_1= \frac{3}{7}$, $x_2= x_1= \frac{3}{7}$, and $x_3= 1- 2x_1= 1- \frac{6}{7}= \frac{1}{7}?$.

The second derivative is 7, positive, so that is a minimum. (We could also have observed that the function in $x_1$ is a parabola opening upward.)

  • $\begingroup$ Please do not post duplicate answers. $\endgroup$
    – Xander Henderson
    Apr 20 at 13:39
  • $\begingroup$ @XanderHenderson Any idea on how to do it? $\endgroup$
    – statwoman
    Apr 20 at 17:44

Let $f$ be the cost function and note that ${\partial f(x^*) \over \partial x} = (3,3,3)$. Let $g(x) = x_1+x_2+x_3-1$ and note that $g(x^*) = 0$ and ${\partial f(x^*) \over \partial x} + \lambda {\partial g(x^*) \over \partial x} = 0$ with $\lambda = -1$. Hence we see that $x^*$ solves the convex problem $\min \{ f(x) | g(x) = 0 \}$ and hence is a solution for the more restrictive problem in the question.


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.