# Does linearity decompose down convex sums?

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?

-

If f is linear, then f is convex as well as concave. – TenaliRaman Dec 27 '12 at 9:45

## 1 Answer

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).$$

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 13, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9278892874717712, "perplexity_flag": "head"}