1

I am self-studying Boyd's convex optimization textbook, and I am befuddled by Example 9.1 shown here in screenshot. Specifically, I am confused how he gets that the supremum of $q^{\top} z$ over the ellipsoid is equal to that first term on the right-hand side.

I tried to formulate it as a constrained optimization problem on the surface of the ellipsoid, with a Lagrange multiplier, but it doesn't seem to work.

Any insights?

Example 9.1 from Boyd's Convex Optimization textbook

sudeep5221
  • 2,736
Ifkaluva
  • 13
  • 2

1 Answers1

0

So try centering it first, $\mathcal{E}_0 = \{x| x^TA^{-1}x \leq 1 \}$ then we have that $$\sup_{z \in \mathcal{E}}q^Tz = \sup_{y\in \mathcal{E_0}}(q^Ty) + q^Tx_0.$$

Now consider $\mathcal{E_0}$, since $A$ is positive definite we have that $\mathcal{E} = \{x| \langle A^{-1/2}x, A^{-1/2}x \rangle \leq 1 \} = A^{1/2}B$ where $B$ is the unit ball in whatever Hilbert space you're working in. So for the last part $$\sup_{y \in \mathcal{E}_0}q^Ty = \sup_{\|u\|\leq 1}(q^T A^{1/2}u) = \|A^{1/2}q\|_2$$

The last step again used positive definiteness.

Lee Fisher
  • 1,934
  • That is delightfully short and elegant, thank you! Could I ask about the last step—could you unpack it a bit for me? I can see that q^T A u will be a scalar, and at the supremum u has magnitude 1, but I can’t see how the norm is introduced. – Ifkaluva Mar 08 '24 at 05:32
  • Okay so $q^TA^{1/2}$ is a vector and the dot product $\langle A^{1/2}q, u\rangle$ will be maximized over $u\in B$ if $u$ is a unit vector parallel to $A^{1/2}q$. Recall that $\langle v, v \rangle =|v|_2^2$ – Lee Fisher Mar 08 '24 at 15:19
  • So isn’t it $\left< A^{1/2} q, u\right> = ||A^{1/2} q||_2^2$? I am confused why the square falls off – Ifkaluva Mar 08 '24 at 15:41
  • Since $u$ is a unit vector the optimal choice is $u = \tfrac{A^{1/2}q}{|A^{1/2}q|}$ – Lee Fisher Mar 08 '24 at 16:18
  • I see, the picture is complete now. Thank you! – Ifkaluva Mar 08 '24 at 21:55