Convex-Constrained Nonconvex-Nonconcave Minimax Problem

Question

In the mathematical optimization theory, I have taken a glance at many papers which deal with the unconstrained convex-concave or nonconvex-concave minimax optimization, i.e.,

$$ \min_{x\in X}\ \max_{y\in Y}\ f(x,y), $$

where the function $f\colon X\times Y\to \Re$ is nonconvex and nonconcave w.r.t. x and y, respectively, and also is continuously differentiable (ONLY ONCE), and the sets $X$ and $Y$ are convex on the Euclidean space.

However, I cannot find a paper that treats convex-constrained nonconvex-nonconcave minimax problem. So, for such problems, I want to ask that

Do you know an algorithm that guarantees global convergence*?

* I mean "global convergence" that has certain properties such as first order optimality.

I have also searched from the perspective of the semi-infinite programming. This is because this minimax problem can be reformulated as follows by the epigraphical expression:

$$ \begin{array}{cl} \displaystyle\min_{x\in X, x_0} & x_0\\ \text{subject to} & x_0\geq f(x,y)\quad\forall y\in Y. \end{array} $$

But in this field of studies also, many studies assume convexity of $f$ or sufficient smoothness of $f$.

I do NOT require the efficiency of computation. I want to implement an algorithm that is surely convergent to some points, not necessarily converges to a global optimal (saddle) point.

Answer 1

I got bad news for you: The problem is as long as you care about the inner max being the actual max and not just some local maxima (which might make sense with multiple roll outs for a game theory simulation) you are stuck with calling an global optimizer to just evaluate $x \mapsto \max_{y_\in Y} f(x,y)$ correctly. If $\dim(y)$ is small you might want to try interval newton method for the inner, maybe branch and bound with interval arithmetic for the relaxation (unless you can come up with a better relaxation) and if not or there are constraints on $y$ use some global NLP solver of your choice to sufficient precision.

Maybe you can analytically define gradients for $x \mapsto \max_{y_\in Y} f(x,y)$ it might be worth evaluating passing those to an local NLP solver like IPOPT, WORHP (worth it if you have 0's in the hessian structure you know about) or FilterSQP for minimizing $x$. If such gradients are not available, $\dim(x)$ is big you are only left with local NLP solver (now also including COBYLA2) calling the global optimizer really often or black box optimization of $x \mapsto \max_{y_\in Y} f(x,y)$. If $\dim(x)$ is small you could get away with a method that construct a surrogate of $x \mapsto \max_{y_\in Y} f(x,y)$ which might allow you to call it less often and spent more time picking good points to search instead evaluating bad values (recommend if evaluating $x \mapsto \max_{y_\in Y} f(x,y)$ takes on the order of second). My first pick for that would be the quiet obscure sqpdfo algorithm which constructs a quadratic surrogate what should lead you to a local minima in $x$.

It is my understanding that sqpdfo, IPOPT, WORHP and FilterSQP claim to be able to be globally convergent and all handle constraints. If this is not the case then you can just hope that some black box approach (evolutionary algorithms, simulated annealing, particle swarm optimization) would work well enough for you.

If there are constraints that both include $x$ and $y$ add those fully to other outer problem and with $y$ not occurring in the objective to ensure feasibility of the inner problem and run the global optimization with $x$ fixed from the outer problem. The fact that your constraints are convex is not exploited by any approach i presented, however it will make the inner optimization faster and the outer optimization more likely to find something good. Also if you have equality constraints, please see to eliminating as many inner variables as possible.