1
$\begingroup$

Define $f:\mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}$ by $f(u,v)=\displaystyle\sum_{i=1}^n|u_i-v_i|^p$.
Assume $p>1$.

We'd like to maximize $f$ under the following constraints: $$ \left\{\begin{array}{l} g_1(u,v):=f(u,0)=1 \\ g_2(u,v):=f(0,v)=1 \\ g_3(u,v):=\langle u,v\rangle=0\end{array}\right. . $$

The problem is very similar to one posed by Andre Porto here: Help minimizing function

Only I want to maximize, not minimize.

I tried setting up Lagrange multipliers, but I got no further than staring at the system. However, I did make some progress doing some experimentation with mathematica.

It seems that the maximizer $(u,v)$ will satisfy $$u_1 = -v_1$$, $$u_2=v_2$$ $$\dots{}$$ $$u_n=v_n$$

and $$|u_2|=|v_2|=...=|u_n|=|v_n|$$

This implies $$f(u,v)=\frac{2^p}{1+(n-1)^{1-\frac{p}{2}}}$$ which then must be the maximum. I am fairly sure this is right(I tried it with a bunch of $n$ and $p$ values). But how can I prove it? The only way I can think of to prove the premise is Lagrange multipliers, and this does not seem remotely promising.

Partial results are welcome! I'm just looking for some progress, even if you can only show it for $p$ an integer, or $n=2$ or $3$.

$\endgroup$
  • $\begingroup$ You won't have that much luck with Lagrange multipliers because your function isn't differentiable (the absolute value is not). $\endgroup$ – Fimpellizieri Dec 10 '16 at 21:57
  • $\begingroup$ We would have to restrict the domain to make it differentiable, then show that whatever critical points there are produce a value less than or equal to the values I described in the question... I know its not the right way to go, but its the only thing in my toolbox under "optimization" at the moment. $\endgroup$ – Retired account Dec 10 '16 at 22:02
  • $\begingroup$ That's a completely fine way to go about it! $\endgroup$ – Fimpellizieri Dec 10 '16 at 22:03
  • $\begingroup$ What is exactly in the dots in the condition $u_1=-v_1$, $u_2=v_2$, ..., $u_n=v_n$? Does it keep going with same sign for $u_i$ and $v_i$? $\endgroup$ – coconut Dec 15 '16 at 17:59
  • $\begingroup$ Yes. They all have the same sign except the first. $\endgroup$ – Retired account Dec 15 '16 at 18:08
2
+50
$\begingroup$

$\newcommand{\Reals}{\mathbf{R}}\newcommand{\Basis}{\mathbf{e}}\newcommand{\Brak}[1]{\left\langle #1\right\rangle}$tl;dr The case $n = 2$ can be handled with trigonometry and elementary calculus; the constrained extreme values are $2$ and $2^{p-1}$.


Fix $p > 1$. The "unit circle" in the $p$-norm, a subset of $\Reals^{2}$, can be parametrized as a polar graph: $$ u_{1} = r(t) \cos t,\qquad u_{2} = r(t) \sin t, $$ with $r$ a positive function and $t$ real. Since $1 = |u_{1}|^{p} + |u_{2}|^{p} = r(t)^{p}\bigl(|\cos t|^{p} + |\sin t|^{p}\bigr)$, we have $$ r(t)^{p} = \frac{1}{|\cos t|^{p} + |\sin t|^{p}}. \tag{1} $$ There are two choices of $v$ orthogonal to $u$, given by $$ v_{1} = -r(t) \sin t,\qquad v_{2} = r(t) \cos t $$ and its negative. By the sum formulas for $\cos$ and $\sin$, $$ \sqrt{2} \cos(t - \tfrac{\pi}{4}) = \cos t + \sin t,\qquad \sqrt{2} \sin(t - \tfrac{\pi}{4}) = \sin t - \cos t. $$ For either choice of $v$, equation (1) gives \begin{align*} f(u, v) &= |u_{1} - v_{1}|^{p} + |u_{2} - v_{2}|^{p} \\ &= r(t)^{p} \bigl(|\cos t + \sin t|^{p} + |\sin t - \cos t|^{p}\bigr) \\ &= r(t)^{p} 2^{p/2} \bigl(|\cos(t - \tfrac{\pi}{4})|^{p} + |\sin(t - \tfrac{\pi}{4})|^{p}\bigr) \\ &= 2^{p/2} \frac{|\cos(t - \tfrac{\pi}{4})|^{p} + |\sin(t - \tfrac{\pi}{4})|^{p}}{|\cos t|^{p} + |\sin t|^{p}}. \tag{2} \end{align*} For $p \neq 2$, the function $$ \phi(t) := |\cos t|^{p} + |\sin t|^{p} $$ is even, periodic with period $\frac{\pi}{2}$, strictly monotone on $[0, \frac{\pi}{4}]$, and has extreme values $\phi(0) = 1$ and $\phi(\frac{\pi}{4}) = 2^{1 - (p/2)}$. (If $p = 2$, then $\phi(t) = 1$ for all $t$.) Consequently, when subject to the constraints $$ |u_{1}|^{p} + |u_{2}|^{p} = |v_{1}|^{p} + |v_{2}|^{p} = 1,\qquad u_{1}v_{1} + u_{2}v_{2} = 0, $$ we have:

  • If $1 < p < 2$, then $\phi$ has a minimum value of $1$ at $0$, a maximum value of $2^{1 - (p/2)}$ at $\frac{\pi}{4}$, and $$ 2^{p-1} \leq f(u, v) = 2^{p/2}\, \frac{\phi(t - \frac{\pi}{4})}{\phi(t)} \leq 2. $$

  • If $2 < p$, then $\phi$ has a minimum value of $2^{1 - (p/2)}$ at $0$, a maximum value of $1$ at $\frac{\pi}{4}$, and $$ 2 \leq f(u, v) = 2^{p/2}\, \frac{\phi(t - \frac{\pi}{4})}{\phi(t)} \leq 2^{p-1}. $$

In other words, $$ 1 + 2^{p-2} - |1 - 2^{p-2}| = \min(2, 2^{p-1}) \leq f(u, v) \leq \max(2, 2^{p-1}) = 1 + 2^{p-2} + |1 - 2^{p-2}|. $$

Constrained extrema of the $p$-norm


These values can obviously be achieved in higher dimensions by "padding with $0$'s", and the "natural generalizations" do no better: If $n = 2m$ is even, for example, the vectors $$ u = m^{-1/p}(\underbrace{1, \dots, 1}_{m}, \underbrace{0, \dots, 0}_{m}),\qquad v = m^{-1/p}(\underbrace{0, \dots, 0}_{m}, \underbrace{1, \dots, 1}_{m}) $$ satisfy $f(u, v) = 2$, and the vectors $$ u = (2m)^{-1/p}(\underbrace{1, \dots, 1}_{m}, \underbrace{1, \dots, 1}_{m}),\qquad v = (2m)^{-1/p}(\underbrace{1, \dots, 1}_{m}, \underbrace{-1, \dots, -1}_{m}) $$ satisfy $f(u, v) = 2^{p-1}$. (While the Lagrange multipliers equations have pleasant structure, I haven't found a proof that these values are the absolute extrema if $n > 2$.)

$\endgroup$
  • $\begingroup$ Thank you! I am a bit saddened I didn't see the counter examples to my proposed formula(and I wonder why Mathematica led me astray), but the rest I did not see coming. Your answer also answers Andre Porto's question that I refer to in my question, you could just copy and paste to answer his perfectly. $\endgroup$ – Retired account Dec 16 '16 at 3:34
  • $\begingroup$ You're very welcome. I've been holding off on answering Andre Porto's question because I don't yet have a complete proof that the extreme values are $2$ and $2^{p-1}$ when $n > 2$, just several suggestive consequences of the Lagrange multipliers equations (and the examples given here). $\endgroup$ – Andrew D. Hwang Dec 16 '16 at 12:40

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.