Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am interested in the following convex optimization problem:

\begin{align*} \max & \lVert x \rVert_1 \\ \text{s.t.} & \lVert x -a\rVert_1 \le K \\ & \lVert b\circ x\rVert_2 \le 1\\ & x \in \mathbb{R}^n \end{align*} where $a, b$ are positive vectors in $\mathbb R^n$ and $\circ$ is the Hadamard (element-wise) product. Assume that the feasible region is non-empty. What is a tight upper bound dependent on $a, b, K$?

share|improve this question
I believe that if $x$ is feasible, then so is $\mbox{sign}(a)\cdot|x|$, so you may assume WLOG that $\mbox{sign}(x) = \mbox{sign}(a)$, and the objective becomes $\mbox{sign}(a)^{\top}x$. From there, probably you have to break it into two cases, depending on whether $a$ meets the $L_2$ feasibility condition or not. Perhaps the two cases are amenable to Lagrange multiplier technique. –  shabbychef Oct 10 '12 at 4:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.