# On solution methods for min-min optimization problems

Closely related (although not equivalent) to minimax optimization problems is the following:

$$\min_{x \in \Omega} \min_{i=1,...,q} f_i (x).$$ Here, $$\Omega \subset \Bbb R^n$$ and $$f_i: \Bbb R^n \to \Bbb R$$ is continuously differentiable. I am looking for references on algorithms for this kind of problems. Specifically, I am interested in steepest- descent -like methods. Can you suggest a good reference/survey?

• Notice that you could exchange the minimum in any case without changing the final value. So your problem is equivalent to $\min_{i=1,...,q}\min_{x\in\Omega}f_i(x)$, and you just need to optimize each function. Jul 30 '19 at 3:04
• @foxell thanks for the comment. However, note that in general, you can't find global minimums. The idea is to build a method that converges to a stationary point of the problem. Jul 30 '19 at 8:07

This comment is too long so I directly post it as an answer. It is not hard to propose such a method.

Assumption: Every $$f_i(x)$$ is Lipschitz differentiable with constant $$L$$, and define $$h(x):=\min_{i=1,...,q}f_i(x)$$. Suppose further that $$h(x)$$ is bounded from below.

First, it is easy to prove:

Optimality condition:Assume for every $$j$$ such that $$f_j(z)=h(z)$$ we have $$\nabla f_j(z)=0$$, then $$h(x)$$ is differentiable at $$z$$ and $$\nabla h(z)=0$$.

Second, start from $$x_k$$, let $$f_{j_k}(x_k)=h(x_k)$$, and $$\|\nabla f_{j_k}(x_k)\|$$ is the largest one among the index set such that $$f_j(x_k)=h(x_k)$$. Compute $$x_{k+1}:=x_k-\frac{1}{L}\nabla f_{j_k}(x_k)$$. Then you could prove that $$h(x_k)\leq h(x_0)-\frac{1}{2L}\sum_{i=0}^{k-1}\|\nabla f_{j_i}(x_i)\|^2$$. Push to the limit, it is easy to prove that any cluster point of $$x_k$$ is a stationary point of $$h(x)$$.

By the way, in general, I think your problem is a special form of bilevel optimization.

• thanks for the answer! Do you know of any reference that deals with something like this? Jul 30 '19 at 14:38
• I am sorry that I have never seen a textbook which deals with this kind of problem. The algorithm used here is mainly inspired by the sub-gradient method, which I learned from Nesterov's book "Lectures on Convex Optimization". Jul 31 '19 at 0:39