Sequential Quadratic ProgrammingEdit

Sequential Quadratic Programming

Sequential Quadratic Programming ( Sequential Quadratic Programming ) is a cornerstone method for solving constrained nonlinear optimization problems. It targets problems of the form minimize f(x) subject to equality constraints h(x) = 0 and inequality constraints g(x) ≤ 0, where f, h, and g are smooth functions. The core idea is to approximate the original problem locally by a quadratic model of the objective and by linearized constraints, solve a small quadratic programming (Quadratic programming ) subproblem, and use the resulting step to update the decision variables. The process repeats, driving the iterates toward a point that satisfies the optimality conditions for the original problem.

SQP is valued for both its solid theoretical foundations and its practical performance across a range of disciplines, including engineering design, trajectory optimization, control, economics, and operations research. Its effectiveness rests on exploiting structure: many real-world problems feature smooth objectives and constraints with sparsity patterns in their derivatives, which SQP can leverage to solve subproblems efficiently. Because the method works with well-understood objects like the Lagrangian and the KKT conditions, it connects closely to classical ideas in constrained optimization while delivering modern, scalable algorithms.

Overview

The standard constrained nonlinear program (CNP) addressed by SQP can be written as:

minimize f(x)
subject to h(x) = 0
g(x) ≤ 0

where x ∈ R^n is the decision vector, h : R^n → R^p collects equality constraints, and g : R^n → R^m collects inequality constraints. At a given iterate x_k, SQP builds a quadratic model of the objective and linear models of the constraints. The quadratic model is a second-order approximation to f, often using an approximation of the Hessian of the Lagrangian L(x, λ, μ) = f(x) + λ^T h(x) + μ^T g(x). The resulting subproblem is:

minimize 1/2 d^T B_k d + ∇f(x_k)^T d
subject to h(x_k) + ∇h(x_k) d = 0
g(x_k) + ∇g(x_k) d ≤ 0

where d is the search direction, B_k is the current approximation to the Hessian of the Lagrangian, ∇f, ∇h, and ∇g are the gradients (Jacobians) of f, h, and g at x_k. If the current iterate is feasible, h(x_k) = 0 and the equality constraints simplify to ∇h(x_k) d = 0. Solving this small QP yields d_k, and the next iterate is typically x_{k+1} = x_k + α_k d_k with a line search or a trust-region strategy to enforce global convergence and robust progress.

Key ingredients in this framework include:

Lagrangian and KKT conditions: The KKT conditions provide necessary conditions for optimality in constrained problems and guide the update of multipliers KKT conditions and the construction of the QP subproblem through the Lagrangian Lagrangian.
Hessian/Hessian-approximation: The matrix B_k approximates the Hessian of the Lagrangian. Positive definiteness of B_k on the subspace tangent to the constraints helps ensure well-behaved search directions. Quasi-Newton updates (such as BFGS) are commonly used to maintain a good approximation without forming second derivatives explicitly.
Linearization of constraints: Equality constraints are handled by linearization, while inequality constraints are incorporated via the QP subproblem and, in practice, via active-set strategies or merit-function mechanisms.

Subproblem formulation and variants

Active-set SQP: A common implementation maintains a working set of active inequality constraints. The QP subproblem is solved with these constraints treated as equalities, and the active set is updated as iterations proceed. This approach is particularly effective when the active constraints stabilize near the solution.
Trust-region SQP: To improve robustness in difficult regions (e.g., nonconvex landscapes or ill-conditioned problems), a trust-region constraint bounds the step size. This prevents overly aggressive steps and can aid convergence when curvature is challenging.
Line-search and merit functions: To ensure global convergence from arbitrary starting points, practitioners often use a merit function that trades off objective improvement against constraint violation. A typical merit function balances f(x) and a penalty for constraint residuals, guiding both the direction and the step length.
Large-scale and sparse problems: For problems with large dimension but sparse derivatives, specialized linear algebra and sparse QP solvers are employed. This allows SQP to exploit problem structure and keep per-iteration costs manageable.

Convergence and practical considerations

Under standard regularity conditions (for example, Mangasarian-Fromovitz or LICQ-type conditions on the constraints) and with a suitable positive-definite Hessian approximation B_k, SQP methods exhibit favorable convergence properties. In the vicinity of a solution that satisfies the KKT conditions, SQP often achieves superlinear convergence, and with exact or highly accurate Hessian information, quadratic convergence can be observed. The practical performance of SQP hinges on:

Quality of the Hessian approximation: Positive definiteness in the feasible subspace helps ensure meaningful search directions. Poor approximations can degrade performance or cause instability.
Quality of constraint handling: Accurate Jacobians ∇h(x_k) and ∇g(x_k) support reliable subproblems. When constraints are nonlinear or ill-conditioned, careful numerical treatment (regularization, scaling) is important.
Solver efficiency: The cost of each iteration is dominated by solving the QP subproblem. Exploiting sparsity, structure, and robust QP solvers is crucial for performance.
Problem structure: Problems with smooth, well-behaved objectives and moderately sized, well-posed constraint sets are especially amenable to SQP. For very large-scale problems, interior-point methods or alternative approaches may offer scalability advantages, though SQP remains competitive in many engineering applications.

History and applications

SQP traces its development to the work of researchers who combined classical nonlinear programming ideas with quadratic approximations to create a practical, reliable approach for constrained problems. Its lineage includes connections to Newton-type methods for constrained optimization and to active-set strategies that track the current set of binding constraints. Over time, SQP has matured into a standard tool in optimization toolkits and software packages, frequently used for design optimization, trajectory planning, calibration tasks, and control problems.

Prominent application areas include aerodynamics and structural optimization, process engineering, robotics, and automotive and aerospace design. The method’s flexibility in handling both equality and inequality constraints, along with its ability to exploit derivative information, makes it a preferred choice when accurate models are available and the problem size is moderate to medium.

Within the broader landscape of optimization, SQP sits alongside alternative approaches such as Interior-point methods, augmented Lagrangian methods, and penalty-based strategies. Each family has its own strengths and trade-offs in terms of robustness, scalability, and sensitivity to problem conditioning. In practice, practitioners select based on problem size, sparsity, constraint structure, and the cost of evaluating derivatives.

Controversies and debates

As with many numerical optimization methods, the choice of algorithm often reflects problem characteristics and engineering judgment rather than a universal best option. Debates in the optimization community focus on issues such as:

Scalability to very large problems: For extremely large-scale problems, interior-point methods and first-order approaches can offer better memory footprints and parallel scalability. SQP remains highly effective for problems with rich structure and high accuracy requirements, but practitioners weigh these considerations when selecting a method.
Robustness to nonconvexity: In nonconvex settings, the local nature of SQP means convergence may depend on the starting point and the Hessian approximation. Alternative methods that emphasize global strategies, such as certain penalty or trust-region variants, are sometimes favored when global optimality is a concern.
Dependence on derivative information: SQP relies on accurate gradients and Jacobians. In settings where derivatives are expensive to compute or noisy, derivative-free methods or stabilized approximate derivatives may be preferred, though this often comes at a cost to convergence speed.
Choice of Hessian updates: Different quasi-Newton schemes (e.g., BFGS, SR1) lead to different convergence behavior. The positivity properties of the Hessian approximation in the presence of active constraints are a practical concern, and regularization or damped updates are common remedies.
Problem conditioning and scaling: Poorly scaled problems can hinder convergence. Preconditioning, rescaling of variables, and reformulation of the problem can significantly affect performance, sometimes more than the choice of the optimization engine itself.

In practice, many practitioners adopt a hybrid approach: they use SQP for problems where derivative information is reliable and the problem size is manageable, while turning to alternative methods when those conditions fail. The ongoing dialogue in the field emphasizes empirical performance on representative benchmarks, the development of robust QP solvers, and the integration of SQP with problem-specific structure to push efficiency and reliability further.