$$\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?
Best Answer
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.