I know that the minimum of a set of convex functions is not necessarily convex. However, are there quick numerical techniques that can be used to find the minimum of a set of convex functions?
In other words, let
$$f(x) = \min_x\{g_1(x), g_2(x), ... g_n(x)\}.$$
If $g_i$ are all convex, then what is a good strategy for minimizing $f$?
EDIT: several people have brought up the fact that the answer depends on the details about $n$ and the computational cost of computing the minima for each $g$. Some more details that might help:
- $n$ is very large, generally $100!$ to $1000!$. These are functions in $R^{100} \to R$, or in other words $x \in R^{100}$, but each $g_i$ can be minimized quite quickly.
- The connection between each function is that each $g_i$ is defined as the distance between a particular permutation of the entries of a vector $y \in R^{100}$ and $x$.
If the number of your convex functions is finite, it's available to find their minimum respectively and compare them together to find the "minimum minimum". Because a convex function has only one or doesn't have a minimum value.
If one of the convex functions doesn't have a minimum value, then your $f(x)$ doesn't have one too.
I don't know if it's the best way but maybe it is in all probability because we don't know the connection between these functions. The minimum of $f(x)$ indeed lies in one of the minimums among $g(x)$'s. If you don't know their connection, there's no way you find which one is the smallest unless you check them all.