0
$\begingroup$

$$\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?

$\endgroup$
  • 3
    $\begingroup$ 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$.) $\endgroup$ – Michael Grant Feb 20 '17 at 14:56
  • $\begingroup$ 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. $\endgroup$ – Septimus G Feb 20 '17 at 14:59
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$ ? $\endgroup$ – Septimus G Feb 22 '17 at 16:11
  • $\begingroup$ Since $\frac12 \, x + \frac12 \, y$ is feasible, its objective value cannot be smaller than $f(x)$. $\endgroup$ – gerw Feb 22 '17 at 18:10
  • $\begingroup$ This answer does not take into account the linear constraints $Ax /ge b$. Is there any way that could affect the proof? $\endgroup$ – Septimus G May 3 '17 at 15:23
  • $\begingroup$ My answer takes into account the linear constraints: "Since the feasible set is convex..." $\endgroup$ – gerw May 3 '17 at 18:11
  • 1
    $\begingroup$ @WesamF. Yes. This proof only uses that the feasible set is convex. This is satisfied for convex inequality constraints together with affine equality constraints. $\endgroup$ – gerw Jun 27 '18 at 6:58

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.