How would I maximizing the sum of elements given the squared sum?

Question

The question is a more broad approach, but as a concrete example, if I have a point represented by the vector v on a d-dimensional unit sphere, how would I find the elements of the vector v that would maximize the L1 norm of v?

So for a 2 dimensional circle, if I have a point (x,y) on the circle, we know that $x^{2} + y^{2} = 1$, how would I find at which point $x + y$ is maximized.

I’ve gone about it backwards, where if we theorize that when x = y, x + y is maximized, then the rate at which x is decreased by will be more than how much y gains therefore since the equation is convex, that’s the maximum.

Is there a prettier and/or more intuitive way to go about this?

Answer 1

Note that if $v$ maximises the one norm on the unit sphere then so do any of $(\pm v_1,...,\pm v_d)$, so we can assume that $v_k \ge 0$ for all $k$. Hence we can see that $v$ solves the problem $\max_{\|x\|_2 \le 1} \sum_k x_k $ which can be solved using Lagrange multipliers to get $v_1=\cdots = v_d = {1 \over \sqrt{d}}$. Hence the maximisers are $(\pm \sqrt{d}, ..., \pm \sqrt{d})$.

Answer 2

We begin with a thought experiment with a unit circle. If $\space x\approx 0\space$ or $\space y\approx 0,\space$ then $\space x+y\approx 1\space$ while if $\space x=y,\space$ then $\space x+y=\sqrt{2}\approx 1.414213562373095.\quad$

If we can step outside the unit circle we can generate Pythagorean triples $\space (A,B,C:\space A^2+B^2=C^2)\space $ where $\space A\approx B\space$ by using Pell Numbers to feed Euclid's Formula shown here as $\quad A=m^2-k^2\qquad B=2mk\qquad C=m^2+k^2.\quad$ The Pell Numbers required are found with:

$$ m_n= \frac{(1 + \sqrt{2})^{n+1} - (1 - \sqrt{2})^{n+1}}{2\sqrt{2}}\qquad k_n= \frac{(1 + \sqrt{2})^n - (1 - \sqrt{2})^n}{2\sqrt{2}}$$

The higher the value of $\space n, \space$ the higher the pair of Pell Numbers and the higher the ratio $\quad R=\dfrac{A+B}{C}\longrightarrow\sqrt{2}.\quad$ $\space (A,B,C)\space$ values exceed $\space 15\space$ digits after the $19^{th}$ triple but, with arbitrary precision, we can come arbitrarily close to $\space \sqrt{2}$.

Examples:

\begin{align*} F(2,1)&=(3,4,5)& R = 1.40000000000000\\ F(5,2)&=(21,20,29)& R\approx 1.41379310344828\\ F(12,5)&=(119,120,169)& R\approx 1.41420118343195\\ F(29,12)&=(697,696,985)& R\approx 1.41421319796954\\ F(70,29)&=(4059,4060,5741)& R\approx 1.41421355164605\\ F(169,70)&=(23661,23660,33461)& R\approx 1.41421356205732\\ F(408,169)&=(137903,137904,195025)& R\approx 1.41421356236380\\ F(985,408)&=(803761,803760,1136689)&R\approx 1.41421356237282\\ \end{align*}

Answer 3

Lagrange Multipliers might do it.

Suppose $f=\sum_{k=0}^nx_k^2=D^2$ What selection of $x_k$ maximizes $g=\sum_{k=0}^nx_k$

Using langrange multipliers, $\frac{\partial f}{\partial x_k}=\lambda \frac{\partial g}{\partial x_k}\implies 2x_k=\lambda\implies x_k=\lambda/2$ for all $x_k$.

Since all $x_k$ are equal, their squares are equal and we have $nx_k^2=D^2\implies x_k=\sqrt{\frac{D^2}{n}}$

Suppose $g=\sum_{k=0}^n=|x_k|$

$2x_k=\lambda\frac{x_k}{|x_k|}\implies 4x_k^2=\lambda^2\implies x_k=\pm\lambda/2$

$f\implies n\lambda^2/4=D^2\implies\lambda = \sqrt{4D^2/n}$, so $g=\sqrt{nD^2}$