1

I was going through the optimization tutorial of Stephen Boyd. However, I didn't understand how this expression was dervied

$sup\{{a_i^Tu \;|\; ||u||_2 <=r}\}$ = $r||a_i||_2$.

I have attached the screenshot for the context

enter image description here

user34790
  • 4,192
  • If $a_i$ is 0 then there is nothing to prove.

    From Cauchy-Schwarz for any $u$ with $|u|=r$ , $ (a_i^Tu)^2 \leq |a_i|^2 |u|^2 \leq |a_i|^2 r^2$, hence $a_i^Tu \leq | a_i^Tu | \leq |a_i|r $. The equality is obtained when $u_i = r a_i / |a_i|$

     – Arin Chaudhuri Jan 10 '13 at 20:26

1 Answers1

1

Drop the index $i$ for convenience, write $\alpha$ for $||a||$, consider the fact that the squared lengths of vectors are non-negative, and expand the squared length of a suitably chosen linear combination of $a$ and $u$:

$$0 \le || r a - \alpha u||^2 = ||r a||^2 + ||\alpha u||^2 - 2(r a)' (\alpha u).$$

(Equality holds if and only if $ra =\alpha u$.) Adding the last term to both sides and factoring the scalars $r^2$ and $\alpha^2$ out gives

$$\left(2 r \alpha\right) a'u \le r^2\alpha^2 + \alpha^2 ||u||^2 = \alpha^2\left(r^2 + ||u||^2\right).$$

Because $||u|| \le r$, $||u||^2 \le r^2$, whence

$$\left(2 r \alpha\right)a'u \le \alpha^2\left(r^2 + r^2\right) = \left(2 r \alpha\right)r \alpha.$$

Either $2 r \alpha=0$ or we can divide both sides by $2 r \alpha$; in either case,

$$a'u \le r \alpha.$$

Since the value $r \alpha$ can be attained when $\alpha u = r a$, this indeed is the supremum.

This is obvious geometrically: $u$ is constrained to lie in the ball of radius $r$ and $a'u$ is $\alpha$ times the component of $u$ in the $a$ direction. That component is maximal when $u$ is parallel to (and in the direction) of $a$, which occurs when $\alpha u = r a$.

whuber
  • 8,531