# What is the vector $x ∈ \mathbb{R^3}$ that achieves $max||x||_1$ subject to $||x||_2 = 1$?

I'm trying to answer the questions "What is the vector $$x ∈ \mathbb{R^3}$$ that achieves $$max||x||_1$$ subject to $$||x||_2 = 1$$?" and "What is the vector x ∈ $$R^3$$ that achieves $$max||x||_∞$$ subject to $$||x||_2 = 1$$?

I think the first question is asking me to find a vector with three components that will have the maximum $$||x||_1$$ norm value where $$\sqrt{x_1^2 + x_3^2 + x_2^2} = 1$$, so $$x_1^2 + x_3^2 + x_2^2 = 1$$. I know the The L1 norm is just the sum of the absolute values of the vector's components. After trial and error I came up with $$x = [\sqrt{\frac{1}{3}}, \sqrt{\frac{1}{3}}, \sqrt{\frac{1}{3}}]$$ , but also $$[-\sqrt{\frac{1}{3}}, -\sqrt{\frac{1}{3}}, -\sqrt{\frac{1}{3}}]$$, and $$[-\sqrt{\frac{1}{3}}, \sqrt{\frac{1}{3}}, \sqrt{\frac{1}{3}}]$$, etc.

For my the second question, I think I need to find the vector in $$\mathbb{R^3}$$ that will give me the maximum value of the absolute value of the vector's components given $$x_1^2 + x_3^2 + x_2^2 = 1$$. I came up with $$[1, 0, 0]$$, $$[0, 1, 0]$$ , $$[0, 0, 1]$$, $$[-1, 0, 0]$$, $$[0, -1, 0]$$ , and $$[0, 0, -1]$$.

Am I correct? Is there a more formal way to figure this out and write my solution?

• First question is tackled with Cauchy-Schwarz, see math.stackexchange.com/questions/218046/… for instance; Second one is even easier – Olivier Jul 8 '19 at 13:57
• To solve optimization problems subject to equality constraints Lagrange multipliers are a very popular method. Example 1a in the Wiki article is quite close to your $L_1$ problem. – pH 74 Jul 8 '19 at 13:59

To solve the first question:

By symmetry, we can assume $$x_1,x_2,x_3$$ are all positive (and add the other solutions later).

By the method of Lagrange multipliers

$$L=x_1+x_2+x_3 - \lambda(x_1^2 + x_2^2 +x_3^2-1)$$

$$0=\frac{\partial L}{\partial x_1} = 1-2\lambda x_1$$ $$0=\frac{\partial L}{\partial x_2} = 1-2\lambda x_2$$ $$0=\frac{\partial L}{\partial x_3} = 1-2\lambda x_3$$

These three equations imply $$x_1=x_2=x_3$$ so that by the constraint $$||x||_2=1$$, the solutions is $$x_1=x_2=x_3=\frac{1}{\sqrt{3}}$$

All of the solutions are

$$x_1=\pm \frac{1}{\sqrt{3}},\quad x_2=\pm \frac{1}{\sqrt{3}},\quad x_3=\pm \frac{1}{\sqrt{3}}.$$

To solve the second question:

We want to maximize one of the elements of the vector.

Trivially, the solutions are

$$\begin{pmatrix} \pm 1 \\ 0 \\ 0 \end{pmatrix}, \quad \begin{pmatrix} 0 \\ \pm 1 \\ 0 \end{pmatrix}, \quad \begin{pmatrix} 0 \\ 0 \\ \pm 1 \end{pmatrix}.$$

We can obtain this also with Lagrange multipliers. Since, by symmetry, we can seek to maximize $$|x_1|$$, first constrain $$x_1$$ to be positive as above, and then find the other solution ($$x_1<0$$).

Consider

$$L= x_1 - \lambda (x_1^2 + x_2^2 + x_3^2-1)$$

$$0=\frac{\partial L}{\partial x_1} = 1 + 2 \lambda x_1$$ $$0=\frac{\partial L}{\partial x_2} = 2\lambda x_2$$ $$0=\frac{\partial L}{\partial x_3} = 2\lambda x_3$$ implies that $$x_1=1$$ and $$x_2=x_3=0$$. Similarly for the other cases.

If $$\|x\|_2 = 1$$, the Cauchy-Schwarz inequality implies $$\|x\|_1 = |x_1|+|x_2|+|x_3| \le \sqrt{x_1^2+x_2^2+x_3^2}\cdot\sqrt{1+1+1} = \sqrt{3}$$

For $$(x_1,x_2,x_3) = \left(\frac1{\sqrt3}, \frac1{\sqrt3}, \frac1{\sqrt3}\right)$$ we have $$\|x\|_1 = \sqrt{3}$$ so this is the maximum.

Now let $$x$$ be a minimizer. We then have equality in the Cauchy-Schwarz inequality above so there exists $$t \in \mathbb{R}$$ such that $$(|x_1|,|x_2|,|x_3|) = t(1,1,1) = (t,t,t)$$ Taking $$\|\cdot\|_2$$ norm gives $$t = \frac1{\sqrt{3}}$$ so $$x=\left(\pm\frac1{\sqrt3}, \pm\frac1{\sqrt3}, \pm\frac1{\sqrt3}\right)$$

• so would the answer to the first question be the set of vectors x where $\|x\|_1 = \sqrt{3}$ ? – John Jul 8 '19 at 15:39
• @John Precisely, it is the sphere around the origin of radius $\sqrt{3}$ w.r.t. the norm $\|\cdot\|_1$. – mechanodroid Jul 8 '19 at 16:04
• @John Of course, intersect the set above with the unit sphere. There are only $4$ solutions, see above. – mechanodroid Jul 8 '19 at 17:15
• There are eight solutions! They lie on the vertices of a cube. – mjw Jul 8 '19 at 21:54
• @mjw Whoops, $2^3= 8$ and not $4$, thanks. – mechanodroid Jul 8 '19 at 21:57

In general, $$\|x\|_1 \le \sqrt{n}\|x\|_2$$, where $$n$$ is the dimension of the space.

If $$\|x\|_2 = 1$$ then we have $$\|x\|_1 \le \sqrt{n}$$, to achieve equality, note that $$\|{1 \over \sqrt{n}}(1,...,1) \|_1 = \sqrt{n}$$.

For the solution of your first question, you should also add the follwoing points: $$\left(\sqrt{\frac{1}{3}}, -\sqrt{\frac{1}{3}}, -\sqrt{\frac{1}{3}}\right), \left(\sqrt{\frac{1}{3}}, -\sqrt{\frac{1}{3}}, \sqrt{\frac{1}{3}}\right), \left(\sqrt{\frac{1}{3}}, \sqrt{\frac{1}{3}}, -\sqrt{\frac{1}{3}}\right), \left(-\sqrt{\frac{1}{3}}, -\sqrt{\frac{1}{3}}, \sqrt{\frac{1}{3}}\right)$$ and $$\left(-\sqrt{\frac{1}{3}}, \sqrt{\frac{1}{3}}, -\sqrt{\frac{1}{3}}\right)$$.

To intuitively guess them, you need to think that both L1 and L2 are symmetric metrics. So you should consider points $$(x_1, x_2, x_3)$$ where $$|x_1| = |x_2| = |x_3|$$. The constraint of $$x_1^2 + x_2^2 + x_3^2 = 1$$ would give you $$|x_1| = |x_2| = |x_3| = \sqrt{\frac{1}{3}}$$.

For a geomteric solution, let us first consider the case in 1st octant i.e. where $$x_1 \geq 0, x_2 \geq 0,$$ and $$x_3 \geq 0$$. Thus $$L_1 = |x_1| + |x_2| + |x_3|$$ is equivalent to $$L_1 = x_1 + x_2 + x_3$$. Now geometrically, one needs to find the point where the plane $$x_1 + x_2 + x_3 = constant$$ touches the sphere $$x_1^2 + x_2^2 + x_3^2 = 1$$ in the first octant.

If you want to formally and algebraically compute the values in the 1st oactant, then you need to write the Lagrangian function $$L(x_1, x_2, x_3, \lambda) = x_1 + x_2 + x_3 + \lambda(x_1^2 + x_2^2 + x_3^2 - 1)$$. Now equate all the partial derivatives to 0. This will get you $$\lambda = -\frac{1}{2x_1} = -\frac{1}{2x_2} = -\frac{1}{2x_3}$$. This leads to $$x_1 = x_2 = x_3 = \frac{1}{\sqrt{3}}$$. In the other octant (where $$x_1 \le 0, x_2 \geq 0,$$ and $$x_3 \geq 0$$) the Lagrangian function will change sign: $$L(x_1, x_2, x_3, \lambda) = -x_1 + x_2 + x_3 + \lambda(x_1^2 + x_2^2 + x_3^2 - 1)$$. This would yield an answer of $$-x_1 = x_2 = x_3 = \frac{1}{\sqrt{3}}$$.

For the second problem, let us take the first case where the $$L_\infty$$ norm $$= Max(x_1, x_2, x_3) = x_1$$. Then the Lagrangian function $$L(x_1, x_2, x_3, \lambda) = x_1 + \lambda(x_1^2 + x_2^2 + x_3^2 - 1)$$.