I have two problems, where $A$ is positive definite:
$$\inf \{ x^TAx + b^Tx : 1-x^Tx \ge 0,\ x \in \mathbb R^n\} \ (1)$$
and
$$ max_\lambda \ q(\lambda) = -0.25b^T(A+\lambda I)^{-1}b - \lambda : \lambda \ge0 \ (2)$$
and I want to show that the solutions to (1) and (2) are the same.
What I have tried:
- Used spectral decomposition to find the inverse of $(A+\lambda I)$ to understand the behavior of (2)
- Given that, I think that the solution is at the border of the unit ball, so that $x^Tx = 1$ but I am having trouble expressing this.
- My approach is to solve (2) and then prove that it is also the solution of (1)
The problem in (1) is convex (since $\mathbf{A}$ is positive definite). It is also strictly feasible, since any x such that $\|x\| < 1$ is a (strictly) feasible solution. By Slater's condition strong duality holds and the optimal value of (1) will be equal to the optimum of its dual.
The Lagrangian of (1) is $$ L(x, \lambda) = x^{T}\mathbf{A}x + b^{T}x - \lambda (1-x^{T}x) = x^{T}(\mathbf{A}+\lambda \mathbf{I})x + b^{T}x - \lambda. $$ By the (stationarity) KKT condition, we know that the optimal $x$, $x^{\star}$, must satisfy $$ 2 \cdot (\mathbf{A}+\lambda \mathbf{I})x^{\star} + b = 0 $$ and hence, $$ x^{\star} = -\frac{1}{2}(\mathbf{A}+\lambda \mathbf{I})^{-1}b. $$ Substituting $x^{\star}$ into the Lagrangian, it is straightforward to verify that $(2)$ is the dual of (1), and according to the above, the optimal value for the two problems is equal.