0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – foxell
    Jul 30 '19 at 3:04
  • $\begingroup$ @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. $\endgroup$
    – John D
    Jul 30 '19 at 8:07
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thanks for the answer! Do you know of any reference that deals with something like this? $\endgroup$
    – John D
    Jul 30 '19 at 14:38
  • $\begingroup$ 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". $\endgroup$
    – foxell
    Jul 31 '19 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.