SLEQP: An open-source package for nonlinear programming

LP phase

An initial step based at the current point is computed by minimizing the piecewise linear approximation

(2)

of Φ over the trust region . This optimization problem can be reformulated into a linear program (LP) to be solved by state-of-the-art LP solvers:

(LP)

where and are the matrices composed of the gradients of the equality and inequality constraints respectively. Note that this program is always feasible and bounded, and therefore guaranteed to have an optimal solution. What is more, the solution of (LP) is connected to first-order optimality conditions (see ref. [11]): Iterate is first-order optimal iff the criticality is zero for some . Indeed, it can be shown [12] that the series of iterates satisfies , implying the existence of a first-order optimal accumulation point .

Working set identification

If (2) is solved using a simplex-type algorithm, the solution not only provides a direction of descent but also a row basis , that is, a subset of of the constraints of (LP) such that is the unique solution of the system of rows in against the corresponding right hand side. Due to the structure of the constraints of (LP) the basis must contain at least one of the two rows involving each of the variables in and two involving each pair of variables in and respectively. A working set is constructed from the basis, which includes

• 1. iff both of the rows and are contained in , and
• 2.  iff all three of the rows , , and are contained in .

Simple linear algebra shows that the rows of the constraint Jacobian, , defined in terms of the rows associated with , has full (row) rank of . As we will see later, this identification of the working set makes the subsequent identification of the multipliers substantially easier.

Cauchy direction

The Cauchy direction is obtained by optimizing a quadratic model of Φ, given by along the interval . Here, the Hessian of the Lagrangian can be either exact or a quasi Newton approximation, while the multipliers will be introduced later. This one-dimensional optimization problem can be solved exactly, given that is known to be piecewise quadratic, or based on an inexact Armijo-type line search, yielding the Cauchy direction . Recall that a trust-region method based on Cauchy steps alone is already convergent [5, Chapter 6].

Dual estimation

The estimation of multipliers based on can be formulated as a quadratic problem:

(3)

The incorporation of the equality constraint is easily achieved by restricting the variables λ to , whereas the inequality constraint makes the estimation significantly more complicated. We can simplify the problem by disregarding the constraints, leading to a linear least squares problem, which can be optimized by solving the system

(4)

and then clipping negative multipliers, which we call of inequality constraints to zero. Note that due to having full rank, the linear system in (4) is regular.

EQP phase

In order to enable locally quadratic convergence, an equality-constrained quadratic programming (EQP) phase can be added to the algorithm, yielding an EQP step used to augment the Cauchy step. Its goal is two-fold: For one, we aim at finding a stationary point of the Lagrangian, for another, we want to decrease the violation of the nonlinear constraints. The classical trust-region subproblem [5, Chapter 7] is concerned with the optimization of quadratic problems subject to a trust-region constraint of the form . The subproblem, having been studied extensively, has a rich structure which can be exploited to yield highly efficient and readily available algorithms such as refs. [13, 14], based on Krylov methods.

An obvious choice regarding the objective is the function introduced above. It is however necessary to deal with the non-smoothness of . In particular, has kinks whenever any passes zero. To alleviate this problem, we fix the variables in to their respective bounds by requiring that . We can decompose into , where d⁰ is the orthogonal projection of the zero vector onto the set feasible set and .

To achieve our goals in terms of the objective, we choose multipliers based on the dual estimation with additional penalties added for the constraints violated at d⁰. Specifically, we let

and set . To compute the initial solution, the projection onto the feasible set can be computed by optimizing another least squares problem, which reduces to solving (4) against a different right hand side. To ensure that remains in the kernel of , if is sufficient to project the steps in the respective Krylov spaces back onto the kernel, which once more involves the solution of (4).

Finally, special care must be taken when the initial projection d⁰ is not feasible with respect to the trust region constraint. In this case the trust-region subproblem as formulated above is infeasible itself. A simple workaround is to relax the linear feasibility requirements.

Step acceptance

The step to be ultimately used is computed based on the Cauchy and EQP steps and using a line search as before. The step is tested against the original model, yielding the reduction ratio . The step is accepted iff and rejected otherwise. In the former case, we set , in the latter we keep . Optionally, a second-order correction (SOC) is computed based on the system (4) to avoid the Maratos effect [15]. Next, the trust-region radii and are updated (see ref. [9] for details). In terms of the LP trust radius, any update needs to satisfy certain conditions to ensure convergence [5, Chapter 6], while the EQP trust radius can be chosen more liberally. Similarly, the penalty parameter ν can be periodically updated in order to improve convergence speed.

Working set identification

While the convergence of the sequence is guaranteed, the working sets and the resulting multipliers are not guaranteed to result in correct residuals that is, in general. The problem is particularly pronounced in problems without constraint qualification. Consider for example, the problem

with optimal solution , which does not satisfy qualifications such as the Linear Independence (LICQ) / Mangasarian-Fromovitz (MFCQ) constraint qualifications. The resulting (LP) at the optimal solution with a suitable trust region of say and a sufficiently large penalty parameter ν has two optimal bases, containing one of the two respective linear constraints, yielding two different working sets. The multipliers obtained from (3) are 0.8 and 0 respectively. While the former choice ensures a vanishing Lagrangian gradient, the latter does not. Since termination criteria are often based on this gradient, the solver never terminates, even though it has reached an optimum. What is more, the incorrect multipliers may also impede the effectiveness of the EQP phase, leading to poor convergence. If an LP has multiple optimal bases, it is generally considered an implementation detail which of these bases is returned by an LP solver. Therefore, the behavior of our algorithm attempting to solve (LP) can change significantly, even between different versions of an underlying LP solver.

The problem of identifying an active set has been examined and can be solved exactly using an integer program [22]. Of course, such an approach is intractable in general. A simpler enhancement of the original approach, implemented in SLEQP, consists of fixing the variables to their solutions in (LP), and to resolve the LP for the remaining variables d in order to obtain a row basis in which can be directly turned into a working set. Of course, such a resolve is often unnecessary. An indicator for a problem such as introduced above to occur is that LP rows which are active, that is, having nonzero multipliers in the LP, are excluded during the standard working set identification.

Local infeasibility

As mentioned above, the algorithm underlying SLEQP is guaranteed to converge to a local optimum of the penalty function Φ. However, such a point is not guaranteed to be feasible for (NLP). Consider the following example, introduced in [23]:

While the problem is supposed to illustrate the failure of certain interior point algorithms, our implementation encounters convergence problems in this situation as well: the algorithm terminates at the (infeasible) point , at which point the solution step of (LP) becomes the zero vector, indicating a local optimum of Φ. Following this, no further progress is made. Recall that this is not a theoretical contradiction: First-order optimal points of (NLP) are local minima of the penalty function Φ, but not all local optima of Φ need to be feasible.

One attempt to escape such points is to include a so-called restoration phase, used in filter–SQP algorithms [6], in which the original objective is discarded in favor of a term designed to solely reduce a measure of infeasibility, such as . Switching between restoration and optimization phases ensures convergence to a local optimum for the particular instance introduced above.

Preprocessing

Preprocessing techniques have been widely studied in the context of linear or quadratic programming problems [24], where the richer problem structure enables significant speed ups. For general nonlinear programs of type (NLP), there is less structure to be exploited during preprocessing. The general constraints c do however often include bound constraints of the type for as well as linear constraints of the form for , . If the presence of these types of constraints are made available to the solver, some forms of preprocessing, such as discarding redundant linear constraints or removing fixed variables, are possible. The test suite used in the numerical experiments in Section 4 contains several instances where a significant portion of variables is fixed, such as the A0ENDNDL instance, where 35 000 of the about 60 000 variables are fixed. Removing the fixed variables during preprocessing about halves the required solution time. Similar effects are likely to occur on computer-generated instances.

Least-squares problems

An important special case of NLPs occurs when the objective f is given in terms of a least-squares function, that is, if . Clearly, its gradient is given by and its Hessian may be approximated using the Gauss-Newton term , which becomes increasingly accurate when approaching a critical point with a small objective, that is, a small residual. We make algorithmic use of this particular structure by using the Gauss-Newton approximation in the EQP phase instead of the Lagrangian of the Hessian. Due to the iterative nature of our trust region solvers, we only require callbacks to compute the residuals as well as forward and adjoint sweeps with respect to the Jacobian . As an alternative to the standard EQP objective, we offer the computation of a step d obtained by solving the following linear least-squares problem

To solve this subproblem to high accuracy even for badly conditioned problems, we use an implementation of the LSQR [25] algorithm as a numerically more reliable variant to standard conjugate gradient approaches. Specifically, we compute an initial step in the same way as in the standard EQP phase and proceed to solve the linear least-squares problem on the kernel of using LSQR iterations.