2
$\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$
2
  • 5
    $\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, 2017 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, 2017 at 14:59

1 Answer 1

Reset to default
7
$\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$
6
  • $\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, 2017 at 16:11
  • $\begingroup$ Since $\frac12 \, x + \frac12 \, y$ is feasible, its objective value cannot be smaller than $f(x)$. $\endgroup$
    – gerw
    Feb 22, 2017 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, 2017 at 15:23
  • $\begingroup$ My answer takes into account the linear constraints: "Since the feasible set is convex..." $\endgroup$
    – gerw
    May 3, 2017 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, 2018 at 6:58

You must log in to answer this question.

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