0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Does your norm satisfies that $0 \le x \le z$ implies $\|x\| \le \|z\|$? This case might be easier. $\endgroup$
    – gerw
    Dec 17, 2021 at 11:48
  • $\begingroup$ @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$ $\endgroup$
    – Kumar
    Dec 17, 2021 at 13:27
  • $\begingroup$ 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$. $\endgroup$
    – gerw
    Dec 18, 2021 at 13:30
  • $\begingroup$ @grew. Perfect. Thank you $\endgroup$
    – Kumar
    Dec 20, 2021 at 16:10

0

You must log in to answer this question.