3
$\begingroup$

I have a real valued function, let's call it $f(\mathbf{x}, \mathbf{y})$, which I would like to maximise with respect to $\mathbf{x}\in\mathrm{R}^d$ and minimise it with respect to $\mathbf{y}\in\mathrm{R}^q$. After a while I realised that I am looking for a solution that is a saddle point. I have no experience with such kind of problems.

Could anyone inform me what algorithms there are for dealing with such problems? I am working in Julia, so in case anyone knows some implementation in Julia that would help me even further.

Note: this was originally posted in the CrossValidated forum, but I was suggested to move it here instead.

$\endgroup$
  • $\begingroup$ Sounds like a differentiable minimax problem. Do you know that there are desired saddle points for sure? If so, is it unique? If not, do you want all of them or just one? $\endgroup$ – Memming Aug 4 '16 at 17:33
  • 1
    $\begingroup$ Is $f$ conditionally convex given $x$ or given $y$ by any chance? It would be helpful if you tell us more about $f$. $\endgroup$ – Memming Aug 4 '16 at 17:35
4
$\begingroup$

That depends on whether $f$ is differentiable with respect to $x$ and $y$, and whether the function is convex/concave in $x$/$y$. In the simplest case, you can just write down the necessary optimality conditions $$ \begin{pmatrix} \nabla_x f(\bar x,\bar y) \\ \nabla_y f(\bar x,\bar y) \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} $$ for the saddle point $(\bar x,\bar y)$, where $\nabla_x f(x,y)\in \mathbb{R}^d$ is the gradient with respect to $x$ etc., and apply a Newton method to that system of nonlinear equations.

Alternatively, you could use an iterative method (variously called ascent-descent, Arrow--Hurwicz or alternating directions method): Start with $x^0,y^0$ and set $$ \begin{aligned} x^{k+1} &= x^k + \alpha_k \nabla_x f(x^k,y^k)\\ y^{k+1} &= y^k - \alpha_k \nabla_y f(x^k,y^k) \end{aligned} $$ for a suitable choice of step sizes $\alpha_k>0$. There are various versions that use $x^{k+1}$ in place of $x^k$ in the update for $y$ or (after reordering the iteration) vice versa, or include an extrapolation step.

If $f$ is not differentiable but convex/concave, similar approaches are possible by using proximal mappings instead of gradients; the currently most widely used approach for the special case $f(x,y) = g(x)+h(y)$ is known under the name primal-dual hybrid gradient method (or often, after the authors of a paper that proposed it, Chambolle--Pock method).

All of these are fairly straightforward to implement in Matlab (and hence easily ported to Python or Julia).

EDIT: I should point out that in contrast to nonlinear optimization, there's no general theory of finding saddle points of nonconvex differentiable functions (as far as I and Google know); all works I am familiar with either assume convexity/concavity or a very specific structure for $f$ (e.g., being the difference of convex functions or coming from the Lagrangian of a constrained optimization problem). The above is merely a description of the two rough classes of approaches used in these papers.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for the quick response. Indeed f is differentiable in both x and y and is nonconvex. Two questions please: how do we instruct the newton method to maximise wrt x and minimise wrt y? If left to its own devices, it may even do the opposite, or? Your second suggestion, the ascent-descent, is clear to me and is sth I also thought about. Trouble is that you have to set step sizes. I typically use conjugate-gradient for my optimisations and what is great about it is that I don't have to tune any step sizes. I was hoping that a method like this would be available also for this type of problem. $\endgroup$ – ngiann Jul 29 '16 at 14:49
  • $\begingroup$ 1) Indeed, Newton's method only cares about getting a root of the necessary optimality condition; if that's a saddle point, fine, if not, you're out of luck. If you have access to the dual problem, you can try to use the duality gap for a line search. 2) Conjugate gradient without line search only works for quadratic problems, otherwise that's something you always have to worry about. However, convergence proofs for a specific ascent-descent method usually give some indication how to choose them; look for example at arxiv.org/pdf/1305.0546.pdf. $\endgroup$ – Christian Clason Jul 29 '16 at 15:18
  • $\begingroup$ Is there any reason for the ascent-descent family why line search or trust regions can't be (separately) used on the x and y pieces, and even to use a Quasi-Newton or Newton method with line search or trust region for each piece? O.k., granted I'm not too sure how well Quasi-Newton would work on the x piece, say, as y is also varying with every x step. What about alternatively, using a bi-level optimization, in which for every x (outer) iteration, y is minimized (not just one iteration as per ascent-descent)? $\endgroup$ – Mark L. Stone Jul 29 '16 at 16:30
  • $\begingroup$ @MarkL.Stone Because then you're only looking at the curvature along the coordinate axes, which doesn't tell you much about the curvature along the path $(x^k,y^k)$ you're actually taking. You'd need some sort of mixed derivatives for that. Bilevel optimization could work, in principle -- it amounts to minimizing the function $x\mapsto \min_y f(x,y)$ using inexact (numeric) function evaluation; if you can get a similar numerical (sub)gradient evaluation, you'd be in business. In general, it is too much work, though (if at all feasible, especially for the gradient). $\endgroup$ – Christian Clason Jul 29 '16 at 16:36
  • $\begingroup$ @MarkL.Stone Maybe you can look at it this way: The fundamental difference between 1d (minimize w.r.t. $x$) and 2d (minimize/maximize with respect to $(x,y)$) is that in 2d, you can run around the stationary point. This is a new problem which the standard 1d line searches are not equipped to deal with. (That is not to say that you shouldn't do a line search in each step, just that it isn't enough.) $\endgroup$ – Christian Clason Jul 29 '16 at 16:45

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.