$\max \{\sum \limits_{i=1}^n z_i w_i \}$ where $\sum \limits_{j=1}^n |w_j| = 1$

Question

How can we find $\max \{\sum \limits_{i=1}^n z_i w_i \}$ where $\sum \limits_{i=1}^n |w_j| = 1$? $z, w \in \mathbb{R}^n$

Answer 1

Note that $|\sum_{i=1}^{n}z_iw_i| \leq \sum_{i=1}^{n}|z_iw_i| \leq (max_{i}|z_i|) \sum_{i=1}^{n}|w_i|=(max_{i}|z_i|)$.

So you maximum is less than or equal to $(max_{i}|z_i|) $. Now can you find a seq of $w_i$'s which achieve the maximum?

Answer 2

Voldemort's answer is right and I've upvoted it... however...

This is not actually convex as written. To make it so you must write it this way: $$\begin{array}{ll} \text{maximize} & \sum_i z_i w_i \\ \text{subject to} & \sum_i |w_i| \leq 1 \end{array}$$ Fortunately, you can prove this is equivalent. To see why, suppose that you have found an optimal $w^*$ satisfying $\sum_i |w_i^*|=\alpha<1$. If $\sum_i z_i w_i^* > 0$, then $\alpha^{-1} w^*$ will give a larger objective value of $\alpha^{-1} \sum_i z_i w_i^*$, a contradiction. (This isn't quite complete; you'd need to show that the objective has to be nonnegative, and address the zero case explicitly.)

Furthermore, this is actually an instance of Hölder's inequality, a generalization of the Cauchy-Schwarz inequality: $$z^Tw\leq \|z\|_p \|w\|_q \qquad \forall~p,q\in[1,+\infty],~1/p+1/q=1$$ In this case, $p=\infty$ and $q=1$. In fact, this can be generalized to any dual pair of norms: $$\langle z, w \rangle \leq \|z\|\|w\|_*$$ In this case, $\|z\|\triangleq\|z\|_\infty$ and $\|w\|_*=\|w\|_1$. To be fair, this definition is a bit circular, since the dual norm is defined by $$\|w\|_* \triangleq \max_{z:~\|z\|\leq 1} \langle z, w \rangle$$ which puts us right back to your question. (Who knows, perhaps that's exactly why you asked it! :-))