# Minimizing a linear combination of convex functions

Suppose a series of convex functions $f_1(x), f_2(x), f_3(x), ...$ is given (also, expressions for their derivatives $\nabla f_1, \nabla f_2,...$ are known). Now, suppose a function $g(x)$ is a linear combination of the above functions, eg, $$g(x)=a_1\cdot f_1(x)+a_2\cdot f_2(x)+a_3\cdot f_3(x)...$$ My question is: can function $g(x)$ be minimized by first optimizing each of $f_i(x)$ separately to find corresponding $x_i$ at which $f_i(x)$ is minimum, and then state that a minimum of $g(x)$ is $y=a_1x_i+a_2x_2+a_3x_3...$? I tried to argue via derivatives of each $f_i(x)$, but cannot proceed.

• No. Counter example is $f_1=x^2$, $f_2=x^2+x$. These have different minima(0 and $-1/2$), which is different from the minimum of $g=af_1+bf_2$ as $-b \over 2(a+b)$, which is not a linear combination of the solutions for each function. . Commented Nov 8, 2012 at 18:27
• @Daryl Thanks. Is there any type of functions $f(x)$ that satisfy the above property? Commented Nov 8, 2012 at 18:41
• The only family of functions I can think of are linear functions, but I am happy to be otherwise corrected. Commented Nov 8, 2012 at 19:05

The minima of the sum is the entire interval between the minima of each individual function. You can imagine if you shifted either function up or down slightly, the minima would suddenly snap to one side or the other, regardless of the coefficients $a_i$.
The general answer is no. But, can we tell the class of functions for which this works out? Let $$x^*_1, x^*_2, ..., x^*_n$$ be the minima of $$f_1, f_2, ...,f_n$$ respectively. Hence, $$\ \nabla f_i(x^*_i)=0 \ \forall i\in[n]$$ $$\ \nabla g(x) = \sum_{i=1}^n \nabla f_i(x)$$ We want $$x'=\sum_{i=1}^n a_ix^*_i$$ to be the minima of $$g$$ which is convex function, $$\ \nabla g(x') = \sum_{i=1}^n \nabla f_i(x') = \sum_{i=1}^n \nabla f_i\left(\sum_{i=1}^n a_ix^*_i\right)$$ We see that in general coming up with such a class is very difficult. A rather trivial answer could be when all the functions have same minima i.e. $$x^*_1, x^*_2, ..., x^*_n=b$$