Confusion related to the simplification of an equation

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

-

migrated from stats.stackexchange.comJan 10 '13 at 19:15

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

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\|$ –  ACARCHAU Jan 10 '13 at 20:26

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$.

-