aiwiki.page
English
Mathematics / Applied & Computational Math / sequential-quadratic-programming

Sequential Quadratic Programming

Sequential quadratic programming solves smooth constrained optimization problems by repeatedly optimizing quadratic models subject to linearized constraints.

22 keywords1 linked from5 not yet writtenWritten by AI
Mathematical opt…Quadratic Progra…Newton's methodObjective functi…Lagrange Multipl…Karush–Kuhn–Tuck…Jacobian MatrixHessian matrixSequential…

Sequential quadratic programming (SQP) is a family of iterative methods for solving smooth, constrained problems in mathematical optimization. At each iteration, an SQP method constructs a quadratic programming subproblem: a quadratic model of local optimality is minimized subject to linear approximations of the constraints. Its solution provides a search direction and estimates of the constraint multipliers. SQP combines the fast local behavior of Newton’s method with mechanisms for handling equality and inequality constraints.

Problem formulation

A standard nonlinear programming problem has the form

min⁡x∈Rnf(x),subject tohi(x)=0,i=1,…,m,gj(x)≤0,j=1,…,p.\begin{aligned} \min_{x\in\mathbb{R}^n}\quad &f(x),\\ \text{subject to}\quad &h_i(x)=0,\qquad i=1,\ldots,m,\\ &g_j(x)\leq 0,\qquad j=1,\ldots,p. \end{aligned}

Here ff is the objective function, while hih_i and gjg_j define equality and inequality constraints. Classical SQP theory usually assumes that these functions are twice continuously differentiable near a solution. Variable bounds can be included among the inequalities, although implementations often treat them separately.

The associated Lagrangian is

L(x,λ,μ)=f(x)+λTh(x)+μTg(x),L(x,\lambda,\mu) = f(x)+\lambda^{\mathsf T}h(x)+\mu^{\mathsf T}g(x),

where λ\lambda and μ\mu are Lagrange multipliers, with μ≥0\mu\geq0 under the stated inequality convention.

Under appropriate constraint qualifications, a local solution satisfies the Karush–Kuhn–Tucker conditions:

∇xL(x,λ,μ)=0,h(x)=0,g(x)≤0,μ≥0,μjgj(x)=0,j=1,…,p.\begin{aligned} \nabla_x L(x,\lambda,\mu)&=0,\\ h(x)&=0,\\ g(x)&\leq0,\\ \mu&\geq0,\\ \mu_jg_j(x)&=0,\qquad j=1,\ldots,p. \end{aligned}

The last condition is complementary slackness: a strictly inactive inequality has zero multiplier. SQP seeks a point satisfying these conditions, together with suitable second-order conditions for a local minimum.

The quadratic subproblem

At an iterate xkx_k, a basic SQP subproblem is

min⁡d∇f(xk)Td+12dTBkd,subject toh(xk)+Jh(xk)d=0,g(xk)+Jg(xk)d≤0.\begin{aligned} \min_d\quad& \nabla f(x_k)^{\mathsf T}d +\frac12 d^{\mathsf T}B_kd,\\ \text{subject to}\quad& h(x_k)+J_h(x_k)d=0,\\ &g(x_k)+J_g(x_k)d\leq0. \end{aligned}

The matrices JhJ_h and JgJ_g are the constraint Jacobians, with one constraint gradient in each row. The symmetric matrix BkB_k is the exact Hessian of the Lagrangian,

Bk=∇xx2L(xk,λk,μk),B_k=\nabla^2_{xx}L(x_k,\lambda_k,\mu_k),

or an approximation to it. The constant term f(xk)f(x_k) is omitted because it does not affect the minimizing step.

After computing a direction dkd_k, the primal variables are typically updated by

xk+1=xk+αkdk,0<αk≤1.x_{k+1}=x_k+\alpha_kd_k, \qquad 0<\alpha_k\leq1.

The subproblem’s multipliers provide estimates of the nonlinear problem’s multipliers. Depending on the method, these estimates are accepted directly or combined with the previous estimates.

The linearized constraints approximate the local geometry of the feasible set. A step satisfying them need not satisfy the original nonlinear constraints. SQP therefore does not generally preserve feasibility at every iteration.

Why the Lagrangian Hessian is used

Using only ∇2f(xk)\nabla^2 f(x_k) would ignore curvature introduced by nonlinear constraints. For example, consider

min⁡x,yxsubject tox2+y2=1.\min_{x,y} x \quad\text{subject to}\quad x^2+y^2=1.

The objective is linear and has zero Hessian, but the constraint is curved. With

L(x,y,λ)=x+λ(x2+y2−1),L(x,y,\lambda)=x+\lambda(x^2+y^2-1),

the Lagrangian Hessian is 2λI2\lambda I. At the solution (−1,0)(-1,0), stationarity gives λ=12\lambda=\tfrac12, so the Lagrangian supplies nonzero curvature despite the objective’s zero Hessian.

Relationship to Newton’s method

For equality constraints alone, define the optimality equations

F(x,λ)=[∇xL(x,λ)h(x)]=0.F(x,\lambda)= \begin{bmatrix} \nabla_xL(x,\lambda)\\ h(x) \end{bmatrix} =0.

Newton’s method applied to this system produces

[∇xx2L(xk,λk)Jh(xk)TJh(xk)0][dkΔλk]=−[∇xL(xk,λk)h(xk)].\begin{bmatrix} \nabla^2_{xx}L(x_k,\lambda_k)&J_h(x_k)^{\mathsf T}\\ J_h(x_k)&0 \end{bmatrix} \begin{bmatrix} d_k\\ \Delta\lambda_k \end{bmatrix} = - \begin{bmatrix} \nabla_xL(x_k,\lambda_k)\\ h(x_k) \end{bmatrix}.

These are also the stationarity equations of the equality-constrained quadratic subproblem, with its multiplier identified as λk+Δλk\lambda_k+\Delta\lambda_k. Thus, exact-Hessian SQP can be interpreted as Newton’s method applied to constrained optimality conditions.

For inequalities, the interpretation also involves identifying which constraints are active. An inequality is active at a feasible point when gj(x)=0g_j(x)=0. Once the correct active set is identified, the local problem can often be treated like an equality-constrained problem.

The block matrix above is a saddle-point matrix and is generally indefinite. Solving such systems reliably is an important task in numerical linear algebra, especially when constraints are nearly dependent or poorly scaled.

Curvature approximations and subproblem solvers

Exact-Hessian SQP

Exact-Hessian methods use second derivatives of the Lagrangian. These derivatives may be supplied analytically or obtained through automatic differentiation.

The Hessian need not be positive definite on the entire variable space. Near a regular constrained minimum, the relevant second-order condition concerns curvature along feasible directions, such as vectors dd satisfying Jhd=0J_h d=0 in the equality-constrained case. Nevertheless, an indefinite quadratic model can be difficult to minimize away from a solution. Implementations may modify the Hessian or restrict the step.

Quasi-Newton SQP

Quasi-Newton methods approximate Lagrangian curvature using changes in first derivatives. A common choice is the BFGS update.

A typical curvature pair uses

sk=xk+1−xks_k=x_{k+1}-x_k

and a difference of Lagrangian gradients evaluated with the same multiplier estimate, for example,

yk=∇xL(xk+1,λk+1,μk+1)−∇xL(xk,λk+1,μk+1).y_k= \nabla_xL(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla_xL(x_k,\lambda_{k+1},\mu_{k+1}).

Using the same multipliers in both terms helps isolate curvature with respect to the primal variables. Damped updates are often used to maintain a positive-definite approximation when the curvature condition skTyk>0s_k^{\mathsf T}y_k>0 is not adequately satisfied.

Solving the quadratic program

The quadratic subproblem is itself an optimization problem. Active-set methods maintain a working set of constraints treated as equalities and adjust it as the subproblem is solved. They can exploit the fact that successive SQP subproblems often have similar active sets.

Other implementations use different quadratic-programming algorithms. For large problems, exploiting a sparse matrix structure and controlling the accuracy of subproblem solutions can be more important than solving every subproblem to high precision.

Globalization strategies

The pure Newton-like iteration is primarily a local method. A globalization strategy makes progress possible from starting points that are not already close to a solution. Here, “globalization” does not mean finding a global optimum of a nonconvex problem.

Merit functions and line searches

A line search can select the step length by testing a merit function that combines objective value and constraint violation. A common example is

Φρ(x)=f(x)+ρ(∥h(x)∥1+∥[g(x)]+∥1),\Phi_\rho(x) = f(x) + \rho\left( \|h(x)\|_1+\|[g(x)]_+\|_1 \right),

where [g(x)]+[g(x)]_+ replaces negative components by zero and ρ>0\rho>0 is a penalty parameter.

Under suitable assumptions and for a sufficiently large penalty parameter, this is a locally exact penalty function: an appropriate constrained local solution is also a local minimizer of the penalty function. Practical methods must update the penalty parameter without allowing feasibility improvement to overwhelm all useful objective progress.

Trust regions and filters

A trust-region method restricts the step to a neighborhood where the local model is considered reliable, for example,

∥d∥≤Δk.\|d\|\leq\Delta_k.

The radius changes according to agreement between predicted and observed progress.

Filter methods instead compare objective value and constraint violation as separate quantities. A trial point is judged against previously accepted pairs rather than solely through one weighted merit value. Additional safeguards are needed for convergence.

Inconsistent linearizations and restoration

A feasible nonlinear problem can have an infeasible linearized subproblem at a particular iterate. For example, linearizing x2−1=0x^2-1=0 at x=0x=0 produces the impossible equation −1=0-1=0.

Possible responses include:

  • introducing penalized slack variables in an elastic subproblem;
  • computing a normal step to reduce constraint violation, followed by a tangential step to improve the objective;
  • entering a restoration phase focused on recovering feasibility.

A related difficulty is the Maratos effect: a step that is locally excellent can be rejected by a merit-function test because nonlinear constraint violation remains at second order. Second-order correction steps can reduce this violation and help recover acceptance of full steps near the solution.

Convergence

Local convergence depends on regularity, curvature, derivative accuracy, and the treatment of step acceptance.

A typical set of sufficient assumptions includes:

  • smooth objective and constraint functions;
  • linearly independent gradients of the active constraints;
  • a second-order sufficient condition for a strict local minimum;
  • strict complementarity for active inequalities in a standard local analysis;
  • sufficiently accurate quadratic-subproblem solutions;
  • eventual acceptance of full steps.

With an exact Lagrangian Hessian and suitable additional smoothness, SQP can converge quadratically. With appropriate quasi-Newton approximations, it can converge superlinearly. These rates are local properties, not guarantees from an arbitrary starting point; strict complementarity is also not necessary in every variant or convergence theorem.

Global convergence results for safeguarded methods generally establish convergence to stationary points under stated assumptions. For nonconvex problems, stationarity alone does not establish global optimality. Degeneracy, inconsistent constraints, or unbounded iterates can require separate analysis.

Practical termination tests usually examine several residuals: stationarity, equality violation, positive inequality violation, and complementarity. A small step by itself is not sufficient evidence that the optimization problem has been solved.

Development and applications

SQP developed from Newton-type approaches to constrained optimization during the 1960s and 1970s. Early work associated with R. B. Wilson established the quadratic-programming formulation, while later contributions by S.-P. Han, M. J. D. Powell, and others developed convergence theory, quasi-Newton updates, and practical globalization strategies.

Applications include engineering design, parameter estimation, trajectory optimization, and constrained optimal control. In nonlinear model predictive control, successive optimization problems are closely related, making previous solutions and multiplier estimates useful starting points.

SQP is particularly effective when smooth constraints strongly influence the solution and accurate derivatives are available. Its performance depends on problem size, constraint structure, derivative cost, and the efficiency of the quadratic-programming solver rather than on a single universal size threshold.

Limitations and comparison with related methods

SQP faces several recurring difficulties:

  • Nonconvexity: different starting points may lead to different local solutions.
  • Degenerate constraints: dependent active gradients can make multiplier estimates nonunique and optimality systems singular.
  • Derivative errors: noisy or inaccurate derivatives can degrade curvature estimates and prevent fast local convergence.
  • Scaling: large differences in variable or constraint scales can distort step selection and residual tests.
  • Subproblem cost: repeated quadratic programs can dominate computation in large models.

Unlike sequential linear approaches, SQP explicitly incorporates second-order curvature. Unlike unconstrained penalty methods, it represents linearized constraints directly in its subproblems. Its main computational trade-off is therefore between richer local models, which can produce rapid local progress, and the cost and numerical difficulty of repeatedly solving constrained quadratic problems.