3
$\begingroup$

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.

Thank you.

$\endgroup$
2
  • $\begingroup$ What good is surely convergent if there is no requirement on what it converges to? Presuming you are able to find feasible (x,y), why not just choose one such (x,y) and have every iteration produce that (x,y). Of course that is meaningless, but it satisfies your criterion as written. $\endgroup$ Oct 22 at 15:25
  • $\begingroup$ @MarkL.Stone I think Keith is asking for a best effort approach i suggested such an approach. $\endgroup$ Oct 22 at 17:34
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I appreciate your detailed answer to this question. I do not know much about global optimization so it helped me to understand the practical way to solve the minimax problem. Unfortunately, the problem I consider is that the dimension of y is much high, that's why it is enough to obtain the solution that does not necessarily converge to the global optimal point but local optimal point for the inner maximization problem. $\endgroup$
    – Keith
    Oct 23 at 8:52
  • $\begingroup$ If you don't care about evaluating $\max _{y\in Y} f(x,y)$ correctly, you can just use a local NLP solver instead but you will be solving a very different problem, $\endgroup$ Oct 23 at 10:16
  • $\begingroup$ The term "globally convergent" is frequently misunderstood. it means the algorithm converges to something, no matter the starting point. It does not means it converges to a global optimum. $\endgroup$ Oct 23 at 14:01
  • $\begingroup$ I understood "globally convergent" as guaranteeing to hit a point with certain properties (such as first or second order optimality criteria) from every (or no) starting point. $\endgroup$ Oct 24 at 10:08
  • $\begingroup$ As @worldsmithhelper said, I want to obtain a solution that has a certain property. $\endgroup$
    – Keith
    Oct 25 at 2:30

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.