Maximizing a linear function over an ellipsoid

Solution 1:

The goal is to solve the following maximization problem:

\begin{align*} & \max c^Ty \\ & \text{s.t. } (y-x)^TA^{-1}(y-x) \leq 1 \end{align*}

Consider the Langrangian approach

\begin{align*} & \max c^Ty+\lambda(1-(y-x)^TA^{-1}(y-x))\\ & \text{s.t. } \lambda \geq 0 \end{align*}

Differentiating w.r.t. $y$,

$$c+2\lambda \left[ A^{-1}x-A^{-1}y\right]=0$$

If $\lambda=0$, the equation above will give us a contradiction, hence $\lambda>0$.

Also, $$y=x+\frac{1}{2\lambda}Ac$$

Hence, if I can solve for $\lambda$, I have solve the whole thing.

Substitute that the equation above to the equation of the ellipsoid(Since $\lambda>0$, the optimal solution must occur at the boundary by complementary slackness condition.)

$$\left(\frac{1}{2\lambda}Ac\right)^TA^{-1}\left(\frac{1}{2\lambda}Ac\right)=1$$

and hence,

$$\lambda^2=\frac{1}{4}c^TAc$$

Hence $$y=x+\frac{1}{\sqrt{c^TAc}}Ac$$