1
$\begingroup$

I'm doing some convex optimisation where I'm minimising sum function $f(x) = \sum g_i(x)$, where the $g$'s are convex (and hence so is $f$) and the sum is finite.

In doing so it turns out that $f$ is a linear function between any two (global) optima. Apparently $f$ being linear here implies that the $g$'s are also linear, why is this so?

  • 0
    If f is linear, then f is convex as well as concave.2012-12-27

1 Answers 1

1

The second derivative of the linear function $f$ is $0 = \sum_{i} g_i''(x)$ where $g_i'' \geq 0$ for every $i$.

We can do the same thing without regularity assumption: if $f$ is defined on the interval $[a,b]$, then for every $t \in[0,1]$ we write $ 0 = f(ta + (1-t)b) - tf(a)-(1-t)f(b) = \sum_{i} g_i(ta + (1-t)b) - tg_i(a)-(1-t)g_i(b). $