# Lagrange Multipliers and quasi-Newton methods

Consider an optimisation problem of the form \begin{aligned} &\min f(x)\\ &\text{s.t. } g(x) = 0 \end{aligned} with $$f,g: \mathbb{R}^n \to \mathbb{R}$$ convex and twice continuously differentiable. For small scale problems (i.e. $$n$$ small), a simple method of solving this is to consider the lagrangian $$L(x, \lambda) = f(x) + \lambda g(x)$$ and solve $$\nabla_{x,\lambda} L(x,\lambda) = 0$$ using Newton's method.

For larger scale problems this becomes difficult because in each step of Newton's method we need to solve the system $$\nabla_{x,\lambda}^2 L(x_k,\lambda_k) (\Delta x,\Delta\lambda) = - \nabla_{x,\lambda} L(x_k,\lambda_k)$$ where the Hessian $$\nabla_{x,\lambda}^2 L(x_k,\lambda_k)$$ is of shape $$(n+1, n+1)$$. For an unconstrained problem it is then common to use a quasi-Newton method, such as BFGS, which iteratively builds up an estimation of the inverse hessian, and thus avoids solving the large system.

When I try to use the same approach for a problem with one constraint like above, I run into the problem that most quasi-Newton methods are only capable of finding minima of the objective as their estimates of the Hessian are positive definite. But the approach with the Lagrangian actually requires us to find a saddle point of the Lagrangian. If I'm not mistaken, The Hessian at the stationary point we are looking for has all but one positive eigenvalues and so it is indefinite.

## Question

What quasi-Newton methods can find the stationary point of the above Lagrangian, even though the Hessian will not be positive definite? Why does this seem like an unpopular approach? (Judging by the fact that the most popular quasi Newton methods have positive definite Hessian estimates)

I know the Symmetric Rank One method does not guarantee a positive definite Hessian, but this is often seen as a downside of this method. Should this method be able to find the stationary point of the above Lagrangian? There is also Broyden's method but this does not exploit the fact that the Hessian is symmetric.

• Is there some reason that you're not using the more conventional method of multipliers or an augmented Lagrangian method? Those approaches avoid any need to solve this saddle point problem. Commented Jul 18, 2020 at 21:25
• @BrianBorchers Is this not the conventional method of Lagrange multipliers? I am also using other approaches such as augmented Lagrangians but everything has ups and downs. Augmented Lagrangian method has extra tunable parametres and multiple minimizations to solve. I am always looking for the simplest method. Commented Jul 18, 2020 at 22:24
• The conventional method is to minimize with respect to $x$, adjust the multipliers $\lambda$, and iterate. You don't ordinarily solve the saddle point problem. Commented Jul 18, 2020 at 23:08
• @ Sam Yes, as stated in a previous comment, I currently use Newton-Krylov with good results. I just aim to remove tunable parameters. Commented Jul 19, 2020 at 11:16
• Note that in quasi-newton SQP, the quasi-newton approximation is an approximation to the Hessian of the objective function rather than the full Lagrangian. This is clear in both Biegler and Nocedal and Wright. Commented Jul 19, 2020 at 17:20

Thanks to the discussion in the comments and the mentioned sources I figured out the answer. The Hessian of the Lagrangian has the following block matrix structure: $$\begin{bmatrix} H & J\\ J^T & 0 \end{bmatrix}$$ where $$H = \nabla^2_{x}L(x, \lambda)$$ and $$J = \nabla_x g(x)$$. This is indeed not positive definite, but the block $$H$$ is positive definite because of the convexity of $$f$$ and $$g$$. To exploit this, you can use BFGS updates on only this part. Using this approach, the entire Hessian of the Lagrangian is still easily invertible, because if we can compute (the action of) $$H^{-1}$$, the entire Hessian can be inverted as $$\begin{bmatrix} H & J\\ J^T & 0 \end{bmatrix}^{-1} = \begin{bmatrix} H^{-1} - sH^{-1} JJ^TH^{-1} & sH^{-1} J\\ sJ^TH^{-1} & -s \end{bmatrix}$$ where the scalar $$s$$ is given by $$s = \frac{1}{J^T H^{-1}J}$$.
If you have more than 1 equality constraint then this does become more difficult, as the computation of $$s$$ now requires the inverse of $$J^T H^{-1} J$$ as well. If this is to difficult, then you can approximate $$J$$ using Broyden's method, combined with BFGS for $$H$$.
• $J$ isn't square in general and doesn't have an inverse in such cases. Commented Jul 22, 2020 at 3:19
• @BrianBorchers You never have to invert $J$. In my case it is also not square but a single column. I misspoke in the last sentence, I will edit. Commented Jul 22, 2020 at 10:39