3
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Jul 18 '20 at 21:25
  • $\begingroup$ @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. $\endgroup$ – Jens Renders Jul 18 '20 at 22:24
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Jul 18 '20 at 23:08
  • $\begingroup$ @BrianBorchers Okay so then my answer there is also because it takes multiple minimizations. Why is it strange to solve the saddle point problem with Newton? Maybe that leads to an answer to my question? Newton doesn't care wether the stationary point is a saddle point right? In my applications it works really wel, But I currently have to resort to Newton-Krylov for the very large scales. I was hoping to get an algorithm without inner iterations, so I looked into the quasi-Newton methods. $\endgroup$ – Jens Renders Jul 18 '20 at 23:25
  • $\begingroup$ For very large-scale, can use L-BFGS or L-SR1. Athough BFGS guarantees descent direction, SR1works better on certain non-convex, or even concave, functions than BFGS because eigenvalues of its Hessian (or inverse Hessian) approximation can adapt to better match those of the true Hessian than can BFGS. Also, when working with nonlinear constraints, and therefore Quasi-Newton is approximating Hessian of Lagrangian, don't expect Hessian of Lagrangian to be positive semidefinite, even in vicinity of or at a (local) minimum (psd only when project into nullspace of Jacobian of active constraints). $\endgroup$ – Mark L. Stone Jul 19 '20 at 1:22
0
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ $J$ isn't square in general and doesn't have an inverse in such cases. $\endgroup$ – Brian Borchers Jul 22 '20 at 3:19
  • $\begingroup$ @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. $\endgroup$ – Jens Renders Jul 22 '20 at 10:39

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.