# Convexity and solution of a 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.

• What have you tried? Apr 18, 2021 at 20:13
• 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$! Apr 18, 2021 at 20:30
• @IgorRivin I don't know how to approach it tbh. Apr 18, 2021 at 23:22
• Yes, I just edited it, thanks for letting me know. @user247327 Apr 18, 2021 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.)

• Please do not post duplicate answers. Apr 20, 2021 at 13:39
• @XanderHenderson Any idea on how to do it? 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.