I have an optimization problem of the following form: $$\min_y\left[\max_x f(x,y)\right].$$ It is fairly straightforward to minimize $f(x,y)$ over $y$ with $x$ fixed, and similarly to maximize $f(x,y)$ over $x$ with $y$ fixed. If it helps, my $x$ problem is concave---but while I can solve the $y$ problem in closed-form it is not convex.

An obvious candidate for an optimization algorithm for the minimax problem might look something like the following: $$ \begin{array}{rl} x_{k+1}&\gets\arg\max_x f(x,y_k)\\ y_{k+1}&\gets\arg\min_y f(x_{k+1},y) \end{array} $$ But, this algorithm doesn't have to converge.

Given oracles for optimizing in one variable at a time, can we construct an optimization algorithm for the minimax problem?

The gradient descent-ascent (GDA) algorithm has a similar flavor, but for our problem finding the global optima for $x,y$ independently is possible so it doesn't seem necessary to just take small gradient steps. If it helps, I'm happy to add a quadratic term to $f$ and assume I can optimize the objective $f(x,y)+\alpha\|y-y_0\|_2^2-\beta\|x-x_0\|_2^2$.

  • $\begingroup$ Can you speak of some properties of $f(x,y)$? Is it possible to split it for instance such that $f(x,y)=g(x) \cdot h(y)$ or can $f$ take some similar special form? $\endgroup$ – Tolga Birdal Dec 6 '20 at 23:49
  • $\begingroup$ No special form, I'm afraid! The x problem is concave, and the y problem is on a low-dimensional compact group, if that helps. $\endgroup$ – Justin Solomon Dec 7 '20 at 4:22

Your Answer

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

Browse other questions tagged or ask your own question.