KKT multiplier for quadratic minimization over Euclidean ball

94 Views Asked by At

I have a question about the minimization problem

$$\begin{array}{ll} \text{minimize} & \frac{1}{2} x^T A x + b^T x\\ \text{subject to} & \frac{1}{2}\|x\|^2_2 \leq \frac{1}{2}\delta^2\end{array}$$

where $A \in \mathbb{R}^{n \times n}$ is symmetric and $b \in \mathbb{R}^n$.

Now the KKT conditions state that if x* is a solution, then

$Ax^{*}+b+\lambda x^{*} = 0$ where $\lambda \geq 0 $

and

$\lambda (\frac{1}{2}||x||_2 - \frac{1}{2}\delta) = 0$,

So I assume that $||x^{*}|| = \delta$ or $\lambda = 0$.

Now what I need to show is that $A+\lambda I$ is a positive semidefinite matrix.

Could you kindly give me some ideas for solving this?