The uniqueness of global minimum for quadratic programs

474 Views Asked by At

I have a question about the uniqueness of the solution for the following quadratic program:

$$\begin{array}{ll} \underset{x \in \mathbb{R}^{n}}{\text{minimize}} & Q(x) := X^T B X - X^T b\\ \text{subject to} & \sum_{i} X_{i} = 1\\ & X_{i} \geq 0\end{array}$$

where matrix $B$ is positive semidefinite. The feasible region is convex, bounded, and closed, so there exists a global minimum. My question is whether the minimum is unique.

I have not taken classes in convex optimization. The question may be naive. Thank you very much for taking the time to read the question. I have searched online. And the results I found were either for equality-constrained optimization or inequality-constrained. In this problem, both forms exist, so I don't know how to conclude in this situation.

2

There are 2 best solutions below

1
On BEST ANSWER

If $B$ is (strictly) positive definite, there is a unique global minimum. Among other things, that precludes $B$ being the zero matrix, which would reduce this to a Linear Programming problem, as pointed out in another answer.

1
On

It need not be unique.

For example if $B=0$ and $b=0$, then every feasible solution is optimal.

If $B=0$ and $b=0$, then we have a linear programming problem, of which it need not have a unique solution.