# Does a convex quadratic program have a unique solution?

$$\min \; x^T Q x \\ s.t. Ax\le b$$

With $Q$ being PSD, is the optimal solution unique?

To add more detail, the objective function I am interested in is $\sum x_i ^2$. For the linear case it is well known that the optimal solution may not be unique. For an unconstrained quadratic problem it is intuitive, based on convexity, that the optimum is unique. For an equality constrained problem, one can express the optimal solution in terms of the KKT system of equations, which has a unique solution. How to go about showing that for an inequality constrained problem the optimal solution is (or it is not) unique?

• If $Q$ is positive definite, then yes there is a unique solution, as long as the constraint set is feasible. Put another way, there is no more than one solution. If $Q$ is only positive semidefinite, then it is possible for multiple solutions to occur. (Consider the extreme case $Q=0$.) – Michael Grant Feb 20 '17 at 14:56
• Thank you. Could you elaborate more on the answer or provide some reference? Since for my case $\sum x_i ^2 > 0$ we can say that Q is PD. – Septimus G Feb 20 '17 at 14:59

Let us define $f(x) = x^\top Q \, x$. In case that $Q$ is PD, it is easy to check that $f$ is strictly convex, i.e., $$f( \lambda \, x + (1-\lambda ) \, y) < \lambda \, f(x) + (1-\lambda) \, f(y)$$ for $x \ne y$ and $\lambda \in (0,1)$. (In this PD case, $f$ is even strongly convex).
Now, let $x$ and $y$ be two different global minimizers of your problem. Since the feasible set is convex, you have that the point $\frac12 \, x + \frac12 \, y$ is feasible. Finally, $f(\frac12 \, x + \frac12 \, y) < \frac12 \, f(x) + \frac12 \, f(y) = f(x)$, which is a contradiction to the optimality of $x$ and $y$. As long as, the constraint set is convex, this proof works.
• So our contradiction arises form $f(\frac12 \, x + \frac12 \, y) < f(x)$. Would you expect for them to be equal? I understand that the convex combination of feasible points must be feasible, but why would you expect that $f(\frac12 \, x + \frac12 \, y) = f(x)$ ? – Septimus G Feb 22 '17 at 16:11
• Since $\frac12 \, x + \frac12 \, y$ is feasible, its objective value cannot be smaller than $f(x)$. – gerw Feb 22 '17 at 18:10
• This answer does not take into account the linear constraints $Ax /ge b$. Is there any way that could affect the proof? – Septimus G May 3 '17 at 15:23