4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. . $\endgroup$
    – Daryl
    Commented Nov 8, 2012 at 18:27
  • $\begingroup$ @Daryl Thanks. Is there any type of functions $f(x)$ that satisfy the above property? $\endgroup$
    – user506901
    Commented Nov 8, 2012 at 18:41
  • $\begingroup$ The only family of functions I can think of are linear functions, but I am happy to be otherwise corrected. $\endgroup$
    – Daryl
    Commented Nov 8, 2012 at 19:05

2 Answers 2

4
$\begingroup$

I think the answer is no. Consider the functions in the following picture: enter image description here

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

These functions are not differentiable but that's not really an issue - just imagine smoothing out the tip of the functions a little bit and the same basic argument applies.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .