0

While going through Boyd & Vandenberghe's Convex Optimization, I saw the following rules, where $f(x) = (h \circ g)(x)$.

  • $f$ is convex if $h$ is convex, $\tilde{h}$ is nondecreasing, and $g$ is convex

  • $f$ is convex if $h$ is convex, $\tilde{h}$ is nonincreasing, and $g$ is concave

  • $f$ is concave if $h$ is concave, $\tilde{h}$ is nondecreasing, and $g$ is concave

  • $f$ is concave if $h$ is concave, $\tilde{h}$ is nonincreasing, and $g$ is convex

Consider the convexity of $f(x)= \sqrt{ 1 + x^2 }$, here $h(x)=\sqrt{x}$ and $g(x)=1+x^2$. The extended value extension $h̃$ is $h=-\infty$ for $x<0.$

Clearly, $h$ is concave and nondecreasing, and $g$ is a convex function.

I want to know if the the above rules are if and only if, i.e if the function does not fit in any of the above conditions, can it still be convex?

Rodrigo de Azevedo
  • 1
Sridhar Thiagarajan
  • 700
  • 2
  • 8
  • 23
  • Your question is unclear. The rules given in Boyd and Vandenberghe's book are if-then rules and your example doesn't fit any of the conditions. The book didn't say that these were the only times that the composition might be concave or convex. – Brian Borchers Aug 12 '18 at 21:51
  • Okay, so if the conditions don't fit, the function might still be convex or concave? – Sridhar Thiagarajan Aug 13 '18 at 04:54
  • 2
    Right- the theorems in Boyd and Vandenberghe simply aren't applicable to your situation. I expect that it will be easy to find a counterexample to the theorem that you proposed but I don't know that for sure. – Brian Borchers Aug 13 '18 at 04:59

1 Answers1

1

Okay, so if the conditions don't fit, the function might still be convex or concave. Consider f to be twice differentiable (not actually necessary, just to illustrate why this is true).

$$f=h(g(x))$$

$$f''(x)=g'(x)^2h''(g(x))+h′(g(x))g''(x).$$

Clearly, the conditions above correspond to both of the terms being individually positive. There can also be the case where one is positive and the other negative, but one is more positive than the other, making the term $f''(x)$ positive, and $f(x)$ convex, while not being included in the cases above.

Sridhar Thiagarajan
  • 700
  • 2
  • 8
  • 23
  • 1
    the log-sum-exp function is a typical example of a function that is concave but does not follow from composition rules. – Casey Aug 17 '18 at 17:03
  • Yes, $\sqrt{1+x^2}$ also seems to be the case considering $h$ and $g$ to be the square root and the polynomial $1+x^2$ – Sridhar Thiagarajan Aug 17 '18 at 17:06
  • 1
    Right, $||x||_2$ (the more general case) is always convex but I don't think it follows from the composition rules. If you ever use Boyd's software CVX, it forces you to work within the rules of Disciplined Convex Programming. Roughly, it means they define some atomic convex operations and all other expressions must be provably convex/concave from he curvature rules above. The result is that you may write things that are actually convex but the program will error because it's not provable from these rules – Casey Aug 17 '18 at 17:47