6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ First question is tackled with Cauchy-Schwarz, see math.stackexchange.com/questions/218046/… for instance; Second one is even easier $\endgroup$ – Olivier Jul 8 '19 at 13:57
  • 1
    $\begingroup$ 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. $\endgroup$ – pH 74 Jul 8 '19 at 13:59
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.