Looking for saddle point in scalar function with multiple parameters

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.

• 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? – Memming Aug 4 '16 at 17:33
• Is $f$ conditionally convex given $x$ or given $y$ by any chance? It would be helpful if you tell us more about $f$. – Memming Aug 4 '16 at 17:35

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.

• 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. – ngiann Jul 29 '16 at 14:49
• 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. – Christian Clason Jul 29 '16 at 15:18
• 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)? – Mark L. Stone Jul 29 '16 at 16:30
• @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). – Christian Clason Jul 29 '16 at 16:36
• @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.) – Christian Clason Jul 29 '16 at 16:45