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.
Looking for saddle point in scalar function with multiple parameters
optimization;julia
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. 