4

I know a nonmonotonic convex function which attains its minimum value at a unique point only is strictly convex. I didn't get how lasso is not strictly convex. For eg if I consider two dimensional case.

$||x||_1$ attains its minimum value at (0,0) which is unique

user34790
  • 4,192
  • 3
    Why do you believe your first sentence is true? As an antidote, try $f(x) = \sqrt{|x|}$ and $g(x) = e^x$, both defined on $\mathbb R$. One has no minimum at all and the other has a unique one. Which is which? One is strictly convex and the other is not convex at all. Which is which? – cardinal Aug 15 '13 at 23:31
  • @cardinal. I have changed the question. In your case the first one is not convex at all even it has a unique minimum and the second one is strictly convex but has no minimum(or infinity). I have modified the question. – user34790 Aug 15 '13 at 23:45
  • 1
    $f(x) = |x|$ has a unique minimum, as you've pointed out. It is not strictly convex. So your (new) first sentence also needs modification. :-) One candidate: A nonmonotonic strictly convex function has a unique minimum. – cardinal Aug 15 '13 at 23:56
  • @cardinal. That's my original question. Why is $|x|$ not strictly convex – user34790 Aug 16 '13 at 00:38
  • 1
    Do you know the definition of 'strictly convex'? – Glen_b Aug 16 '13 at 00:46
  • @Glen_b. I think I got it – user34790 Aug 16 '13 at 00:50
  • @Glen_b. If I take any points lets say 0 and 1, and another point 0.5 in between them. The average of the functional value f(0) and f(1) is equal to the functional value at 0.5. so not strictly convex. I had this definition in my mind, that it has a unique minimizer, is it wrong then? I guess I had the wrong definition. Just because a function has unique minimum, it isn't strictly convex – user34790 Aug 16 '13 at 00:53
  • Sorry, I can't work out which of several possible things on this page is being referred to by 'it' there -- you thought that that what in particular had a unique minimizer? – Glen_b Aug 16 '13 at 00:55
  • @Glen_b. I thought that a strictly convex function is a convex function which has a unique minimizer. I am saying this was the wrong definition – user34790 Aug 16 '13 at 00:58
  • @cardinal's example of $e^x$ already showed you that a strictly convex function needn't have a unique minimizer. – Glen_b Aug 16 '13 at 01:01
  • @Glen_b. Yeah, I got it now. Come on guys, I am just a beginner so don't be hard on me :) – user34790 Aug 16 '13 at 01:05
  • My apologies; I didn't intend to make you feel I was being harsh. – Glen_b Aug 16 '13 at 01:08

1 Answers1

1

I thought that a strictly convex function is a convex function which has a unique minimizer. I am saying this was the wrong definition.

Indeed, this was quite wrong, and the source of confusion here. What is true is that strict convexity is related to uniqueness of minimizer: if a strictly convex function attains its minimum, then it does so at exactly one point. However, having unique minimizer does not imply strict convexity, or any convexity at all.

It's important to remember that there are two different notions of strict convexity. Namely, we have:

  1. Strictly convex functions: $u(ta+(1-t)b)<tu(a)+(1-t)u(b)$ for $0<t<1$
  2. Strictly convex norms: $\|ta+(1-t)b\|<t\|a\|+(1-t)\|b\|$ for $0<t<1$, unless $a$ and $b$ are parallel vectors.

A norm can never be strictly convex function in the sense of definition 1, because for any nonzero vector $x$ we have $$\|2x\|=\frac12({\|x\|+\|3x\|}),\quad \text{where }\ 2x=\frac12(x+3x)$$ This is why the definition of a strictly convex norm requires non-parallel vectors. But $\|\cdot\|_1$ fails the second definition too: for example, $$\|e_1+e_2\|=\frac12({\|2e_1\|+\|2e_2\|}),\quad \text{where }\ e_1+e_2=\frac12(2e_1+2e_2)$$ and $e_1,e_2$ are standard basis vectors.

user90090
  • 1,426
  • 7
  • 6