6
$\begingroup$

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

$\endgroup$

1 Answer 1

4
$\begingroup$

I figured out what the issue was with my algorithm. It turns out that skipping an L-BFGS update when $\mathbf{s}_t^\mathrm{T}\mathbf{y}_k \leq 0$ was not the cause of the problem but rather how I was choosing my search direction, $\mathbf{p}$, when the L-BFGS memory was empty (i.e. at initialization or when the memory was flushed due to several bad updates). When the L-BFGS memory was empty, I chose $\mathbf{p} = -\mathbf{g}$ where $\mathbf{g}$ is the gradient of the Lagrangian with respect to $\mathbf{x}$ and $\boldsymbol{\lambda}$. Unlike unconstrained optimization, this will not always give a reasonable search direction leading to the algorithm getting stuck. The correct search direction when the L-BFGS memory is empty is $\mathbf{p} = -\mathbf{H}^{-1}\mathbf{g}$ where $\mathbf{H}$ is the Hessian with, for example, $\boldsymbol{\nabla}_\mathbf{xx}^2 \mathcal{L} \approx \delta \mathbf{I}$ (a scaled identity matrix).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .