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, 2021 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, 2021 at 20:30
  • $\begingroup$ @IgorRivin I don't know how to approach it tbh. $\endgroup$
    – statwoman
    Apr 18, 2021 at 23:22
  • $\begingroup$ Yes, I just edited it, thanks for letting me know. @user247327 $\endgroup$
    – statwoman
    Apr 18, 2021 at 23:23

2 Answers 2


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, 2021 at 13:39
  • $\begingroup$ @XanderHenderson Any idea on how to do it? $\endgroup$
    – statwoman
    Apr 20, 2021 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .