1

I am a beginner in convex analysis and optimization, and am teaching myself the basics using Boyd's archived lectures(CVX101/Stanford).

I've run into a problem statement described here : [is this set convex?]

We definte $(x)_+ = \max\{0,x\}$ and $(x)_- = \max\{0, -x\}$, so $x = (x)_+ - (x)_-$. Is $$ \left\{x \in \mathbf R^n: 1^T(x)_- \le \frac 12 1^T(x)_+ \right\} $$ a convex set?

I am unable to figure out the approach to use for this problem; especially on handling the split between positive and negative elements. Any tips on how to think or go about this will be appreciated.

martini
  • 84,101
Mindstorm
  • 115
  • I have drawn that set in $\Bbb{R}^2$, and it turns out to be a cone (so in particular, it is convex). Maybe the same holds for bigger dimension. – Crostul Oct 13 '15 at 13:23
  • Crostul, I do not understand how you visualized the cone. The seemingly nonlinearity in the formula with (x)+ and (x)- is messing with my thought process. Could you please elaborate on this? A geometric interpretation will really aid my understanding of the problem. – Mindstorm Oct 13 '15 at 16:31

1 Answers1

1

Since $x_-=x_+-x$ we get $$ f(x)=\mathbb{1}^Tx_--\frac12\mathbb{1}^Tx_+=\frac12\mathbb{1}^Tx_+-\mathbb{1}^Tx $$ which is a convex function as $\mathbb{1}^Tx_+$ and $-\mathbb{1}^Tx$ are convex, so $\{f(x)\le 0\}$ is convex.

A.Γ.
  • 29,518
  • :D. That was quite straightforward. At this stage of my training in convex analysis, I feel both bad for not getting this myself as well as happy for finally understanding the thought process.

    Thank you A.G.! ))

     – Mindstorm Oct 13 '15 at 16:28
  • @Mindstorm It is OK, you don't have to be sorry, it is at the end just a matter of getting used to few several principles. – A.Γ. Oct 13 '15 at 19:17