# Norm with non-negativity constraint

Is it possible to solve the following problem for general norm

$$\max_{x \geq 0, \|x\| \leq \lambda} y^{\top} x$$

In the special case of infinity norm we have

\begin{aligned} \max_{x \geq 0,\; \|x\|_{\infty} \leq \lambda} y^{\top} x = \max_{x \geq 0,\; x \leq \lambda \boldsymbol{1}} y^{\top} x = \lambda \min_{u \geq 0} \Big\{\boldsymbol{1}^{\top}u: y \leq u\Big\} = \lambda \sum_{\forall i}\max{\{y_i, 0\}} \leq \lambda\|y\|_1 \end{aligned}

where $$\boldsymbol{1}$$ is a vector or all ones. The first equality follows from non-negativity of $$x$$, the second follows from strong duality of linear program. The last inequality binds only in the special case when $$y$$ is non-negative.

• Does your norm satisfies that $0 \le x \le z$ implies $\|x\| \le \|z\|$? This case might be easier.
– gerw
Dec 17, 2021 at 11:48
• @grew Could you please elaborate. Are you implying that if your condition is satisfied, then there exists a $z$ for a fixed lambda, and so I can drop the norm constraint and just have the inequality constraint $0 \leq x \leq z$ Dec 17, 2021 at 13:27
• If this condition is satisfied, I think that you can ignore components $i$ with $y_i \le 0$. On the remaining components, you should get some kind of conjugate norm. This should work for the $p$-norm, $1 \le p \le \infty$.
– gerw
Dec 18, 2021 at 13:30
• @grew. Perfect. Thank you Dec 20, 2021 at 16:10