The L-BFGS algorithm can be used to minimize an unconstrained, continuously differentiable function, $f(\mathbf{x})$, with respect to a weight vector, $\mathbf{x}$, by storing the $m$ most recent displacements $\mathbf{s}_k = \mathbf{x}_k - \mathbf{x}_{k-1}$ and $\mathbf{y}_k = \boldsymbol{\nabla}f(\mathbf{x}_k) - \boldsymbol{\nabla}f(\mathbf{x}_{k-1})$ under the condition that $\mathbf{s}_k^\mathrm{T}\mathbf{y}_k > 0$ (to maintain positive definiteness of the Hessian approximation; the update is either skipped or damped otherwise) where $k$ is the current iteration. Transitioning to a constrained optimization requires replacing $f(\mathbf{x})$ with the Lagrangian $\mathcal{L}(\mathbf{x},\boldsymbol{\lambda})$ in $\mathbf{y}_k$ such that $\mathbf{y}_k = \boldsymbol{\nabla}_\mathbf{x}\mathcal{L}(\mathbf{x}_k,\boldsymbol{\lambda}_k) - \boldsymbol{\nabla}_\mathbf{x}\mathcal{L}(\mathbf{x}_{k-1},\boldsymbol{\lambda}_k)$ where $\boldsymbol{\lambda}$ is a vector of Lagrange multipliers. For an interior-point algorithm, the Lagrangian would be $$ \mathcal{L}(\mathbf{x},\boldsymbol{\lambda}) = f(\mathbf{x}) - \boldsymbol{\lambda}^\mathrm{T}\mathbf{c}(\mathbf{x}) - \mu \sum_i c_i(\mathbf{x})\text{ subject to }\boldsymbol{\lambda} \geq \mathbf{0}, \ \mu \geq 0 $$ where the last term on the right-hand-side is an additional barrier function, $\mu$ is a scalar barrier parameter, and $\mathbf{c}(\mathbf{x})$ is a vector of inequality constraints.
I implemented a backtracking line-search algorithm using the exact Hessian based on reference (1) which I tested and works great at finding solutions to nonconvex, constrained minimization problems. I then implemented the L-BFGS algorithm as an option for my interior-point algorithm following along to (1,2) and it manages to always quickly converge to a solution on convex problems. On nonconvex problems, on the other hand, L-BFGS only converges to a solution when $\mathbf{s}_k^\mathrm{T}\mathbf{y}_k > 0$ at every iteration. If at any point, $\mathbf{s}_k^\mathrm{T}\mathbf{y}_k \leq 0$ (in which case I skip the update), the algorithm instead proceeds to converge to a non-stationary point (and the algorithm continues stuck at the same point until the iteration limit is reached). If $\mathbf{s}_k^\mathrm{T}\mathbf{y}_k \leq 0$ on the first iteration, I end up taking gradient steps only (because all L-BFGS updates are rejected) that end up getting stuck as well and not reaching a solution.
Has anybody else seen this problem before and know what can be done to make sure L-BFGS converges to a local minimum on nonconvex problems? I suspect it may have something to do with satisfying the "curvature condition" of the Wolfe conditions but I am uncertain since backtracking line-search did not require this for the exact Hessian (although the exact Hessian did have a positive diagonal shift matrix added to maintain the correct matrix inertia as prescribed in (1) which guaranteed that the appropriate portion of the Hessian was positive definite). I looked around at the IPOPT code and it appears that, like me, they just skip updates but I am not sure if they also do something else to aid convergence.
References:
(1) Nocedal & Wright, Numerical Optimization, 2nd Edition, Chapter 19.
(2) Byrd, Nocedal, & Schnabel, Representations of quasi-Newton matrices and their use in limited memory methods, (1996).
