1

Sorry in advance if this question is very simple for some. I need to minimize the sum of positive 2-D functions: $\sum_{i=1}^{N} f_i(k_0,k_1)$, and say that the values that optimize each of these functions are known, i.e., $k_{0,i}, k_{1,i}$. Is there a way to prove that the values $K_0, K_1$ that optimize the sum of the functions above satisfy the following

$\underset{i}{\mathrm{min}} \{k_{1,i}\} \leq K_1 \leq \underset{i}{\mathrm{max}} \{k_{1,i}\}$,

$\underset{i}{\mathrm{min}} \{k_{0,i}\} \leq K_0 \leq \underset{i}{\mathrm{max}} \{k_{0,i}\}$?

Yaz
  • 97
  • If you don't know anything more about the functions, they could have a mean value lower anywhere really. You could imagine the max for one function could overlap the min of another then the collective sum could be minimum somewhere entirely different than the $k_{1,i}$s. But maybe if you add some extra constraint on the functions. – mathreadler Sep 17 '17 at 21:55
  • Imagine the functions being at most polynomially growing modulated by a function with exponential decay as a function of the distance to their minimum. We can get arbitrary close to 0 far away from the box containing the minima and the individual minima can coincide with maxima for the other functions ensuring non 0 sum at all of the the individual minima. – mathreadler Sep 17 '17 at 22:18
  • @mathreadler I appreciate your reply. What if the functions $f_i(k_0,k_1)$ are convex, is it possible then to prove the previous relationship? – Yaz Sep 18 '17 at 07:30
  • If they have to be convex it sounds more reasonable, but I am not sure. – mathreadler Sep 18 '17 at 07:48
  • Sounds like it could be a great question number 2. – mathreadler Sep 18 '17 at 07:55

1 Answers1

1

Already in one dimension we can construct functions which are counterexamples.

Here are three $k=\{0,1,2\}$:

$$f_k(x) = \exp\left(-\frac{|x-k|^{1.6}}{6}\right)\cdot (1-\text{sinc}(x-k)^2)^6$$ As we can see they do have local minima in between the individual minima but they have pairwise maximas exactly on each others minima. The global minimum for the sum is $0$ ( at $x = \pm \infty$ ): enter image description here

For two dimensions we can for example create separable functions with similar properties, global minimum in the middle but local maxima overlapping each others minimum. For example a separable one: $\text{sinc}(x)\text{sinc}(y)$ or a radial one: $\text{sinc}(\sqrt{x^2+y^2})$, which looks like this:

enter image description here

mathreadler
  • 25,824
  • +1 for very nice graph, may I know which tool did you use? – Vikram Sep 18 '17 at 07:53
  • @Vikram : I used Gnu Octave for creating the functions and the plotting functions used the fltk plotting library for these plots. But I am sure you could get comparable graphs using gnuplot instead of fltk or Matlab instead of Octave if you want. – mathreadler Sep 18 '17 at 07:59