Ask an optimization problem

Question

Consider $x,y,z$ are $n$-dimensional variables, and $a,b,c$ are three nonnegative vectors.

Let $f(x,y,z)=a^T x+b^T y+c^T z-\left(\|x\|_2^{2/3}+\|y\|_2^{2/3}+\|z\|_2^{2/3}\right)^3$. How to find the maximum of $f(x,y,z)$ over $x,y,z\ge 0$?

Answer 1

Here is my attempt: $$ \frac{\partial}{\partial x_i} f = a_i - 3 \left( \lVert x\rVert_2^{2/3} + \lVert y\rVert_2^{2/3} + \lVert z\rVert_2^{2/3} \right)^2 \frac{2 x_i}{3\lVert x \rVert_2^{4/3}} $$ We have critical points for $$ 0 = \frac{\partial}{\partial x} f = a - \frac{2 \left( \lVert x\rVert_2^{2/3} + \lVert y\rVert_2^{2/3} + \lVert z\rVert_2^{2/3} \right)^2}{\lVert x \rVert_2^{4/3}} x = a - \lambda x \\ 0 = \frac{\partial}{\partial y} f = b - \frac{2 \left( \lVert x\rVert_2^{2/3} + \lVert y\rVert_2^{2/3} + \lVert z\rVert_2^{2/3} \right)^2}{\lVert y \rVert_2^{4/3}} y = b - \mu y \\ 0 =\frac{\partial}{\partial z} f = c - \frac{2 \left( \lVert x\rVert_2^{2/3} + \lVert y\rVert_2^{2/3} + \lVert z\rVert_2^{2/3} \right)^2}{\lVert z \rVert_2^{4/3}} z = c - \nu z $$ for some non-negative numbers $\lambda, \mu, \nu$.

If $a=0$ then $x=0$, if $b=0$ then $y=0$ and if $c=0$ then $z=0$. Otherwise choose from below for the non-zero $a, b, c$ cases:

\begin{align} x &= \alpha\, a \quad (\alpha = 1 / \lambda > 0) \\ y &= \beta\, b \quad (\beta = 1 / \mu > 0) \\ z &= \gamma\, c \quad (\gamma = 1 / \nu > 0) \\ \end{align} This leads to up to three equations in the real unknowns $\alpha$, $\beta$, $\gamma$: \begin{align} \frac{1}{\alpha} &= \frac{2 \left( \lVert \alpha a \rVert_2^{2/3} + \lVert \beta b \rVert_2^{2/3} + \lVert \gamma c \rVert_2^{2/3} \right)^2}{\lVert \alpha a \rVert_2^{4/3}} \\ &= \frac{2 \left( \alpha^{2/3} \lVert a \rVert_2^{2/3} + \beta^{2/3} \lVert b \rVert_2^{2/3} + \gamma^{2/3} \lVert c \rVert_2^{2/3} \right)^2}{\alpha^{4/3} \lVert a \rVert_2^{4/3}} \iff \\ \alpha^{1/3} \lVert a \rVert_2^{4/3} &= 2 \left( \alpha^{2/3} \lVert a \rVert_2^{2/3} + \beta^{2/3} \lVert b \rVert_2^{2/3} + \gamma^{2/3} \lVert c \rVert_2^{2/3} \right)^2 \end{align} which is equivalent to \begin{align} 2^{1/2} \left( \lVert a \rVert_2^{2/3} \alpha^{2/3} + \lVert b \rVert_2^{2/3} \beta^{2/3} + \lVert c \rVert_2^{2/3} \gamma^{2/3} \right) &= \lVert a \rVert_2^{2/3} \alpha^{1/6} \quad (*) \\ &= \lVert b \rVert_2^{2/3} \beta^{1/6} \\ &= \lVert c \rVert_2^{2/3} \gamma^{1/6} \end{align}

Example: For non-zero $a, b, c$ the RHS give $$ \lVert a \rVert_2^4 \alpha = \lVert b \rVert_2^4 \beta = \lVert c \rVert_2^4 \gamma $$ Expressing $\beta$ and $\gamma$ in terms of $\alpha$ in $(*)$ gives \begin{align} 2^{1/2} \left( \lVert a \rVert_2^{2/3} + \lVert b \rVert_2^{2/3} \left( \frac{\lVert a \rVert_2}{\lVert b \rVert_2} \right)^{8/3} + \lVert c \rVert_2^{2/3} \left( \frac{\lVert a \rVert_2}{\lVert c \rVert_2} \right)^{8/3} \right) \alpha^{2/3} &= \lVert a \rVert_2^{2/3} \alpha^{1/6} \iff \\ 2^{1/2} \left( 1 + \frac{\lVert b \rVert_2^{2/3}}{\lVert a \rVert_2^{2/3}} \left( \frac{\lVert a \rVert_2}{\lVert b \rVert_2} \right)^{8/3} + \frac{\lVert c \rVert_2^{2/3}}{\lVert a \rVert_2^{2/3}} \left( \frac{\lVert a \rVert_2}{\lVert c \rVert_2} \right)^{8/3} \right) \alpha^{1/2} &= 1 \iff \\ 2^{1/2} \left( 1 + \frac{\lVert a \rVert_2^2}{\lVert b \rVert_2^2} + \frac{\lVert a \rVert_2^2}{\lVert c \rVert_2^2} \right) \alpha^{1/2} &= 1 \iff \\ \alpha = \frac{\lVert b \rVert_2^4 \, \lVert c \rVert_2^4} { 2 \left( \lVert b \rVert_2^2\, \lVert c \rVert_2^2 + \lVert a \rVert_2^2\, \lVert c \rVert_2^2 + \lVert a \rVert_2^2\, \lVert b \rVert_2^2 \right)^2 } \\ \beta = \frac{\lVert a \rVert_2^4 \, \lVert c \rVert_2^4} { 2 \left( \lVert b \rVert_2^2\, \lVert c \rVert_2^2 + \lVert a \rVert_2^2\, \lVert c \rVert_2^2 + \lVert a \rVert_2^2\, \lVert b \rVert_2^2 \right)^2 } \\ \gamma = \frac{\lVert a \rVert_2^4 \, \lVert b \rVert_2^4} { 2 \left( \lVert b \rVert_2^2\, \lVert c \rVert_2^2 + \lVert a \rVert_2^2\, \lVert c \rVert_2^2 + \lVert a \rVert_2^2\, \lVert b \rVert_2^2 \right)^2 } \end{align}

The maximum is: \begin{align} f(\alpha\, a, \beta\, b, \gamma\, c) &= \alpha\, \lVert a \rVert_2^2 + \beta\, \lVert b \rVert_2^2 + \gamma\, \lVert c \rVert_2^2 - \left( \lVert \alpha a \rVert_2^{2/3} + \lVert \beta b \rVert_2^{2/3} + \lVert \gamma c \rVert_2^{2/3} \right)^3 \\ &= \alpha\, \lVert a \rVert_2^2 + \beta\, \lVert b \rVert_2^2 + \gamma\, \lVert c \rVert_2^2 - \left( \lVert a \rVert_2^{2/3} \alpha^{2/3} + \lVert b \rVert_2^{2/3} \beta^{2/3} + \lVert c \rVert_2^{2/3} \gamma^{2/3} \right)^3 \\ &= \alpha\, \lVert a \rVert_2^2 + \beta\, \lVert b \rVert_2^2 + \gamma\, \lVert c \rVert_2^2 - \left( \frac{1}{2^{1/2}} \lVert a \rVert_2^{2/3} \alpha^{1/6} \right)^3 \\ &= \alpha\, \lVert a \rVert_2^2 + \beta\, \lVert b \rVert_2^2 + \gamma\, \lVert c \rVert_2^2 - \frac{1}{2^{3/2}} \lVert a \rVert_2^{2} \alpha^{1/2} \\ &= \lVert a \rVert_2^2 \alpha + \frac{\lVert a \rVert_2^4}{\lVert b \rVert_2^2} \alpha + \frac{\lVert a \rVert_2^4}{\lVert c \rVert_2^2} \alpha - \frac{1}{2^{3/2}} \lVert a \rVert_2^{2} \alpha^{1/2} \\ &= \lVert a \rVert_2^2 \alpha \left( 1 + \frac{\lVert a \rVert_2^2}{\lVert b \rVert_2^2} + \frac{\lVert a \rVert_2^2}{\lVert c \rVert_2^2} \right) - \frac{1}{2^{3/2}} \lVert a \rVert_2^{2} \alpha^{1/2} \\ &= \lVert a \rVert_2^2 \alpha \frac{ \lVert b \rVert_2^2 \, \lVert c \rVert_2^2 + \lVert a \rVert_2^2 \, \lVert c \rVert_2^2 + \lVert a \rVert_2^2 \, \lVert b \rVert_2^2 }{\lVert b \rVert_2^2 \, \lVert c \rVert_2^2} - \frac{1}{2^{3/2}} \lVert a \rVert_2^{2} \alpha^{1/2} \\ &= \lVert a \rVert_2^2 \alpha \frac{1}{(2a)^{1/2}} - \frac{1}{2^{3/2}} \lVert a \rVert_2^{2} \alpha^{1/2} \\ &= \frac{7}{8\, 2^{1/2}} \lVert a \rVert_2^{2} \alpha^{1/2} \\ &= \frac{7}{16} \frac{\lVert a \rVert_2^{2} \, \lVert b \rVert_2^2 \, \lVert c \rVert_2^2} { \lVert b \rVert_2^2\, \lVert c \rVert_2^2 + \lVert a \rVert_2^2\, \lVert c \rVert_2^2 + \lVert a \rVert_2^2\, \lVert b \rVert_2^2 } \end{align}

Example: E.g. $a \ne 0$, $b = c = 0$:

$$ f(x,y,z) = a^T x - \left( \lVert x\rVert_2^{2/3} + \lVert y\rVert_2^{2/3} + \lVert z\rVert_2^{2/3} \right)^3 $$ It seems reasonable that $y = z = 0$ for a maximum, otherwise they would decrease the value of $f$.

So we continue maximizing $$ f(x,0,0) = a^T x - \lVert x\rVert_2^2 \quad (**) $$ From the above we assume $x = \alpha a$ and use equation $(*)$ without the terms in $\beta, b, \gamma, c$ and have $$ 2^{1/2} \lVert a \rVert_2^{2/3} \alpha^{2/3} = \lVert a \rVert_2^{2/3} \alpha^{1/6} \iff \\ 2^{1/2} \alpha^{2/3} = \alpha^{1/6} \iff \\ 2 \alpha^{4/3} = \alpha^{1/3} \iff \\ \alpha = \frac{1}{2} $$ which is what we would get from analyzing equation $(**)$.

The maximum is: $$ f((1/2)a,0,0) = \frac{1}{4} \lVert a \rVert_2^2 $$