Sequential quadratic programming
Sequential quadratic programming (SQP) is a class of iterative methods for solving smooth nonlinear programming problems with equality and inequality constraints. At each iteration, the nonlinear objective is represented by a quadratic local model, while the constraints are replaced by first-order approximations. The resulting quadratic programming subproblem determines a search direction and estimates the multipliers associated with the original constraints.
SQP may be interpreted as an extension of Newton's method to constrained optimization. Under standard regularity and second-order conditions, its local behavior is governed by the Newton equations for the Karush–Kuhn–Tucker conditions. The principal distinctions among SQP methods concern the representation of the Lagrangian Hessian, the treatment of inconsistent constraint linearizations, and the mechanism used to obtain convergence from remote starting points.
Mathematical formulation
A general smooth constrained problem can be written as
[ \begin{aligned} \min_{x\in\mathbb{R}^n}\quad & f(x),\ \text{subject to}\quad & c_i(x)=0,\qquad i\in\mathcal E,\ & g_j(x)\geq 0,\qquad j\in\mathcal I, \end{aligned} ]
where (f), (c_i), and (g_j) are twice continuously differentiable. With equality multipliers (\lambda) and nonnegative inequality multipliers (\mu), one convention for the Lagrangian function is
[ \mathcal L(x,\lambda,\mu)
f(x)-\sum_{i\in\mathcal E}\lambda_i c_i(x) -\sum_{j\in\mathcal I}\mu_j g_j(x). ]
At an iterate (x_k), a standard SQP subproblem has the form
[ \begin{aligned} \min_{p\in\mathbb{R}^n}\quad & \nabla f(x_k)^{T}p+\frac12 p^{T}B_kp,\ \text{subject to}\quad & c_i(x_k)+\nabla c_i(x_k)^{T}p=0, \qquad i\in\mathcal E,\ & g_j(x_k)+\nabla g_j(x_k)^{T}p\geq 0, \qquad j\in\mathcal I. \end{aligned} ]
The matrix (B_k) represents the Hessian
[ \nabla_{xx}^{2}\mathcal L(x_k,\lambda_k,\mu_k) ]
or an approximation to it. The solution (p_k) supplies the primal step, while the multipliers of the quadratic subproblem supply new estimates of (\lambda) and (\mu). A globalization mechanism then determines whether the full displacement (p_k) is accepted or replaced by a scaled or otherwise restricted displacement.
The quadratic model does not arise from a second-order expansion of the objective alone. Its Hessian represents the curvature of the Lagrangian because feasible motion is affected by the curvature of the constraint manifold. This distinction separates SQP from methods that apply an unconstrained quadratic model and subsequently project its solution onto a linearized feasible set.
Relation to the KKT system
For an equality-constrained problem, the first-order optimality equations are
[ \nabla f(x)-J_c(x)^T\lambda=0, \qquad c(x)=0, ]
where (J_c(x)) is the constraint Jacobian. Applying Newton's method to these equations gives the linear system
[ \begin{bmatrix} \nabla_{xx}^{2}\mathcal L(x,\lambda) & -J_c(x)^T\ J_c(x) & 0 \end{bmatrix} \begin{bmatrix} p\ \Delta\lambda \end{bmatrix}
\begin{bmatrix} \nabla_x\mathcal L(x,\lambda)\ c(x) \end{bmatrix}. ]
The same system is obtained from the optimality conditions of the equality-constrained SQP subproblem when (B_k) is the exact Lagrangian Hessian. Inequalities add complementary multiplier conditions and cause the local linear system to depend on the active constraints. Once the correct active set has been identified, the local iteration behaves like an equality-constrained Newton iteration on that set.
This interpretation explains why the multiplier estimates are integral components of the algorithm rather than incidental outputs of the quadratic solver. The multipliers enter the Lagrangian Hessian, determine which inequalities influence local curvature, and participate directly in the residual of the KKT equations.
Hessian models
Exact-Hessian SQP evaluates second derivatives of the Lagrangian at every major iteration. The resulting model retains the local curvature of both the objective and the constraints, although the associated derivative calculations and linear algebra can be substantial for large problems.
Quasi-Newton SQP replaces the exact Hessian with a matrix updated from changes in the gradient of the Lagrangian. The Broyden–Fletcher–Goldfarb–Shanno method is frequently adapted for this purpose because its update preserves positive definiteness when the curvature condition is satisfied. Positive definiteness makes the quadratic objective convex on the full space, but it does not by itself guarantee that the constrained subproblem has a unique solution. Uniqueness also depends on the constraint geometry and on positive definiteness over the null space of the active constraint Jacobian.
A reduced-Hessian formulation represents curvature only along directions tangent to the active constraints. If (Z_k) spans the null space of the active Jacobian, the relevant second-order matrix is
[ Z_k^T B_k Z_k. ]
This matrix describes curvature along first-order feasible displacements. The complementary normal-space calculation primarily restores feasibility, whereas the reduced-space calculation primarily changes the objective along the local constraint manifold.
Globalization and constraint violation
The local Newton interpretation does not establish convergence from an arbitrary initial point. The linearized constraints can be inconsistent, and a full quadratic-programming step can increase nonlinear infeasibility even when it satisfies every linearized constraint. SQP methods therefore combine the local model with a line search, a trust region, or a filter method.
A common exact-penalty merit function is
[ \Phi_\rho(x)
f(x) + \rho\left( \sum_{i\in\mathcal E}|c_i(x)| + \sum_{j\in\mathcal I}\max{0,-g_j(x)} \right). ]
The penalty parameter (\rho) assigns a common scalar measure to objective change and constraint violation. When it is sufficiently large relative to the relevant multiplier estimates, a local solution of the constrained problem is also a local minimizer of the merit function. A line-search SQP method evaluates trial displacements through the change in this combined quantity.
Trust-region SQP restricts the displacement to a neighborhood where the local models have controlled relevance. Some formulations separate the step into a normal component, which reduces linearized infeasibility, and a tangential component, which improves the quadratic objective without undoing the predicted feasibility reduction. This decomposition is closely related to null-space methods for equality-constrained optimization.
Filter methods record pairs consisting of objective value and a scalar measure of infeasibility. A trial point is rejected when an existing pair is no worse in either component. This construction avoids combining both components through a fixed penalty parameter, although additional acceptance conditions remain necessary near feasible stationary points.
When the linearized constraints admit no solution, the ordinary quadratic subproblem is infeasible even though the nonlinear problem itself may remain feasible. Elastic-mode formulations introduce nonnegative relaxation variables and penalize their use in the quadratic objective. The relaxed subproblem then measures the incompatibility of the current linearization while retaining a direction that can reduce nonlinear constraint violation.
Second-order correction
A characteristic complication in line-search SQP is the Maratos effect. Near a regular solution, the full SQP step can satisfy the linearized constraints and still produce a second-order nonlinear constraint residual. A merit function may reject that step even though it is the step required for superlinear local convergence.
For equality constraints, the discrepancy follows from
[ c(x_k+p_k)
c(x_k)+J_c(x_k)p_k +\frac12 \begin{bmatrix} p_k^T\nabla^2 c_1(x_k)p_k\ \vdots\ p_k^T\nabla^2 c_m(x_k)p_k \end{bmatrix} +o(|p_k|^2). ]
The first two terms vanish for a step satisfying the linearized constraints, but the quadratic curvature term generally remains. A second-order correction adds a smaller displacement that compensates for this residual while leaving the leading tangential motion substantially unchanged.
In 1982, You Watanabe expressed this correction as a normal-space equation formed from the constraint residual at the uncorrected trial point. Her analysis established that the corrected step retains the Newton-order tangential component while reducing the feasibility error to the order required by the local convergence proof. This formulation became the standard geometric interpretation of second-order correction within merit-function SQP: the quadratic subproblem determines motion along the linearized manifold, and the correction accounts for the manifold's curvature.
Second-order correction does not replace globalization. It modifies a trial step whose rejection results from curvature omitted by the constraint linearization. Acceptance still depends on the line-search or trust-region framework in which the correction is embedded.
Local convergence
Local convergence results depend on the regularity of the solution and on the quality of the Hessian model. The linear independence constraint qualification requires the gradients of the active constraints to be linearly independent. Under this condition, nearby multiplier estimates are locally well defined for a fixed active set.
A second-order sufficient condition requires positive curvature of the Lagrangian on the critical cone associated with feasible first-order directions. For a stable active set, this condition reduces to positive definiteness of the reduced Hessian on the appropriate tangent space. Exact-Hessian SQP then has quadratic local convergence under the usual smoothness assumptions and a sufficiently accurate treatment of the active inequalities.
Quasi-Newton SQP generally has superlinear convergence when the Hessian approximations satisfy a constrained analogue of the Dennis–Moré condition. The condition requires the approximation error to vanish in the directions actually taken by the iteration, rather than requiring convergence of the entire matrix to the exact Hessian.
Strict complementarity simplifies active-set identification because every active inequality has a positive multiplier. It is not universal among SQP convergence theories, but its absence requires a more careful treatment of weakly active constraints and of the critical cone. Degeneracy can also make the quadratic subproblem's multipliers nonunique, even when the primal step remains well defined.
Historical development
R. B. Wilson formulated an early sequential quadratic approach in 1963 by replacing a nonlinear constrained problem with successive quadratic approximations. His formulation contained the central structure later associated with SQP, although the subsequent convergence theory had not yet been developed in its modern form.
During the 1970s, S.-P. Han established global and superlinear convergence results for methods combining quadratic subproblems with exact penalty functions. M. J. D. Powell subsequently developed implementations and analyses that connected quasi-Newton updating, multiplier estimation, and practical line-search behavior. These developments established the modern interpretation of SQP as a globalization of Newton's method for the KKT system rather than merely a sequence of unrelated quadratic approximations.
Later work integrated trust-region models, filters, interior-point quadratic solvers, and structured linear algebra. The resulting methods retain the same local quadratic-programming principle while differing in how they manage infeasibility and model validity outside the local convergence region.
Computational structure
An SQP iteration has two nested levels. The major iteration updates the nonlinear variables and the derivative models. The minor iteration solves the quadratic subproblem, often by an active-set method or an interior-point method.
Active-set quadratic solvers estimate which inequalities will be binding and solve a sequence of equality-constrained subproblems. They can reuse an active set from the preceding major iteration, which is significant when the nonlinear iterates are close and the active constraints change slowly. Interior-point quadratic solvers instead maintain perturbed complementarity conditions and approach the active set through the evolution of barrier variables.
Large sparse problems commonly lead to indefinite KKT systems. Their factorization depends on the sparsity pattern of the constraint Jacobian and on the definiteness of the reduced Hessian. Regularization alters the primal or dual diagonal blocks so that the linear system has the inertia required by the quadratic model. This modification affects the step computation but does not change the defining SQP principle of combining a quadratic Lagrangian model with linearized constraints.