Sequential Quadratic Programming

Intuition Beginner

Suppose you must find the lowest point of a curved landscape while staying exactly on a set of curved paths painted on the ground. Two things are hard at once: the cost curves, so you cannot just slide downhill, and the paths curve, so you cannot just walk in a straight line. Sequential quadratic programming handles both by refusing to solve the real, hard problem directly. Instead, at wherever you currently stand, it builds a simpler stand-in problem it can solve in one shot, takes the step that solves it, and then rebuilds a fresh stand-in at the new spot.

The stand-in is built from two approximations. The curved paths are replaced by their straight-line tangents at your current point — easy to stay on. The curved cost is replaced by a bowl-shaped model that captures both the downhill direction and the local bend. Crucially, the bend used is not the bend of the cost alone but the bend of the cost adjusted by how much each path is pulling on you; that adjusted bend is what makes the step aim correctly when constraints are active. A bowl over straight tangents is the simplest constrained problem with real curvature — the quadratic program of the previous unit — and it has a one-shot solution.

Each round you solve one such quadratic program, move by its answer, and repeat. As you near the true solution the tangents hug the real paths and the bowl matches the real cost, so the rounds need fewer and fewer corrections. Near the end the method doubles its accurate digits each round, the same fast finish Newton's method gives on unconstrained problems. This is the workhorse method for general smooth constrained optimization.

Visual Beginner

Picture a curved cost over a single curved constraint path. At your current point you draw the straight tangent to the path and a bowl-shaped model of the cost. The corner of "lowest bowl point on the tangent line" is your next point — closer to where the real cost is lowest along the real path.

   real curved constraint path  ~~~~~~\
                                        \____
   x_k *----.                                ~~~~~~  (path curves away)
            |\  tangent line (straightened constraint)
            | \________________________________
            |        \
   bowl     |         * x_{k+1}  = lowest bowl point on the tangent
   model    |        /          (the QP subproblem's answer)
   of cost  |       /
            v      /
        downhill + local bend of the (Lagrangian-adjusted) cost

   one round:  straighten the paths  +  bowl-model the cost
               -> solve the quadratic program  -> step to its answer
               -> rebuild at the new point  -> repeat

ingredient of the real problem	what SQP uses instead	why
curved constraint paths	straight tangent lines at the current point	a line is an equality the QP can hold
curved cost	a bowl: downhill slope plus local bend	gives a one-shot minimizer
the bend (curvature)	bend of cost adjusted by constraint pull	aims the step right when constraints press
the whole hard problem	one quadratic program per round	solvable exactly each round

The takeaway: SQP turns a hard curved-cost, curved-constraint problem into a sequence of easy quadratic programs, each built fresh at the current point, and the sequence converges fast.

Worked example Beginner

Minimize the cost $f(x_1,x_2)=x_1+x_2$ while staying on the circle $x_1^2+x_2^2=2$. The true answer is the point on the circle farthest into the down-left direction, $(-1,-1)$, where the cost is $-2$. We take one SQP round from a starting guess and watch it move toward that point.

Step 1. Start. Begin at $x=(1,1)$, which sits on the circle since $1+1=2$. The cost there is $1+1=2$ — the worst point on the circle, the high corner.

Step 2. Straighten the constraint. The constraint is $c(x)=x_1^2+x_2^2-2=0$. Its tangent direction at $(1,1)$ comes from the slopes $2x_1=2$ and $2x_2=2$, so the straightened rule on a step $p=(p_1,p_2)$ is $2p_1+2p_2=0$, i.e. $p_1+p_2=0$. The step must move equally in opposite directions.

Step 3. Model the cost and step. The cost slope is $(1,1)$ in both directions, so on the line $p_1+p_2=0$ the cost change is $p_1+p_2=0$ — flat to first order. The bowl model's bend (here from the constraint pull) selects the step that most reduces cost while staying on the tangent; solving the small quadratic program gives the step $p=(-1,-1)$, landing at $(1,1)+(-1,-1)=(0,0)$ before a feasibility correction pulls it back onto the circle.

Step 4. Rebuild. The next round straightens the circle at the corrected point, which now lies down-left of $(1,1)$, and repeats. Each round slides farther toward $(-1,-1)$.

What this tells us. One SQP round replaced the circle by a line and the cost by a simple model, solved a one-shot problem, and moved decisively from the worst point toward the best. Repeating the round drives the guess to $(-1,-1)$ with cost $-2$, the true constrained minimum.

Check your understanding Beginner

Formal definition Intermediate+

Consider the nonlinear program (NLP)

$$\underset{x\in {\mathbb{R}}^n}{\min }f(x)\text{subject to}{c}_i(x)=0(i\in \mathcal{E}),c_i(x)\ge 0(i\in \mathcal{I}),$$

with $f,c_i$ twice continuously differentiable. The Lagrangian is $L(x,\lambda )=f(x)-{\sum }_i{\lambda }_i{c}_i(x)$, with gradient-in-$x$ block ${\nabla }_{x}L=\nabla f-A(x{)}^{\top }\lambda$ where $A(x)$ is the Jacobian whose rows are $\nabla c_i(x{)}^{\top }$, and Hessian-in-$x$ block ${\nabla }_{xx}^{2}L(x,\lambda )={\nabla }^{2}f(x)-{\sum }_i{\lambda }_i{\nabla }^2{c}_i(x)$. The first-order KKT conditions of 44.02.02 are stationarity ${\nabla }_{x}L=0$, primal feasibility, dual feasibility ${\lambda }_i\ge 0$ for $i\in \mathcal{I}$, and complementary slackness ${\lambda }_i{c}_i(x)=0$.

Definition (SQP subproblem, equality case). At an iterate $(x_k,{\lambda }_k)$ with the equality-only NLP $\min f(x)$ s.t. $c(x)=0$, the SQP step $p_k$ and the new multiplier ${\lambda }_{k+1}$ solve the quadratic program (QP) subproblem

$$\underset{p}{\min }\frac{1}{2}{p}^{\top }{\nabla }_{xx}^{2}L(x_k,{\lambda }_k)p+\nabla f(x_k{)}^{\top }p\text{subject to}A(x_k)p+c(x_k)=0,$$

whose objective is the quadratic model of the Lagrangian and whose constraints are the linearized NLP constraints. This QP is solved by the equality-constrained-QP machinery of 44.04.01: its own KKT system is the symmetric saddle-point linear system

$$\left[\begin{array}{cc}{\nabla }_{xx}^2{L}_k& -A_k^{\top }\\ A_k& 0\end{array}\right]\left[\begin{array}{c}{p}_k\\ {\lambda }_{k+1}\end{array}\right]=\left[\begin{array}{c}-\nabla f_k\\ -c_k\end{array}\right].$$

Definition (SQP for inequalities, IQP). For the full NLP the subproblem is the inequality-constrained QP

$$\underset{p}{\min }\frac{1}{2}{p}^{\top }{\nabla }_{xx}^2{L}_{k}p+\nabla f_k^{\top }p\text{s.t.}\nabla c_i(x_k{)}^{\top }p+c_i(x_k)=0(i\in \mathcal{E}),\nabla c_i(x_k{)}^{\top }p+c_i(x_k)\ge 0(i\in \mathcal{I}),$$

solved by the active-set QP method of 44.04.01; the QP's working set ${\mathcal{W}}_k$ is SQP's guess of the active set $\mathcal{A}(x^{\star })$ of the NLP, and near the solution it identifies that active set exactly. The new symbols $L$ (Lagrangian), ${\nabla }_{xx}^{2}L$ (Hessian of the Lagrangian), $A(x)$ (constraint Jacobian), and the merit functions ${\varphi }_1$, ${\varphi }_{\mathrm{AL}}$ below are recorded in _meta/NOTATION.md.

Definition (quasi-Newton Hessian, Powell's damped BFGS). When ${\nabla }_{xx}^2{L}_k$ is unavailable or indefinite, SQP maintains a positive-definite approximation $B_k\approx {\nabla }_{xx}^2{L}_k$ updated from the Lagrangian secant pair $s_k=x_{k+1}-x_k$, $y_k={\nabla }_{x}L(x_{k+1},{\lambda }_{k+1})-{\nabla }_{x}L(x_k,{\lambda }_{k+1})$. Since $s_k^{\top }{y}_k$ can be nonpositive (the Lagrangian Hessian need not be positive definite, unlike the unconstrained case of 44.03.04), Powell's damping replaces $y_k$ by ${\hat{y}}_k={\theta }_k{y}_k+(1-{\theta }_k)B_k{s}_k$ with

$${\theta }_k=\{\begin{array}{ll}1,& s_k^{\top }{y}_k\ge 0.2s_k^{\top }{B}_k{s}_k,\\ \frac{0.8s_k^{\top }{B}_k{s}_k}{s_k^{\top }{B}_k{s}_k-s_k^{\top }{y}_k},& \text{otherwise},\end{array}$$

which forces $s_k^{\top }{\hat{y}}_k\ge 0.2s_k^{\top }{B}_k{s}_k>0$, so the BFGS update with ${\hat{y}}_k$ keeps $B_{k+1}\succ 0$ by the hereditary-positivity theorem of 44.03.04.

Definition (merit functions). Globalization measures progress on the ${\ell }_1$ merit function ${\varphi }_1(x;\mu )=f(x)+\mu {\sum }_{i\in \mathcal{E}}|c_i(x)|+\mu {\sum }_{i\in \mathcal{I}}[c_i(x){]}^{-}$, where $[t{]}^{-}=\max (0,-t)$, and on the augmented-Lagrangian merit function ${\varphi }_{\mathrm{AL}}(x;\lambda ,\mu )=f(x)-{\lambda }^{\top }c(x)+\frac{\mu }{2}\Vert c(x){\Vert }^2$ in the equality case. The penalty parameter $\mu$ trades feasibility against optimality; an SQP step is acceptable when it sufficiently reduces the chosen merit function.

Counterexamples to common slips

• The QP objective Hessian is the Lagrangian's Hessian, not the objective's. Using ${\nabla }^{2}f$ in place of ${\nabla }_{xx}^{2}L={\nabla }^{2}f-{\sum }_i{\lambda }_i{\nabla }^2{c}_i$ destroys quadratic convergence whenever constraints are curved, because the missing $-{\sum }_i{\lambda }_i{\nabla }^2{c}_i$ term is exactly what the KKT-Newton linearization requires.
• A positive-definite ${\nabla }^{2}f$ does not make ${\nabla }_{xx}^{2}L$ positive definite. Curved constraints with nonzero multipliers can render the Lagrangian Hessian indefinite; SQP needs it positive definite only on the null space of the active constraint Jacobian (the second-order sufficiency condition of 44.02.02), which is why Powell damping or reduced-Hessian SQP is used rather than demanding global positivity.
• The unit SQP step need not decrease a merit function even when it improves both objective and feasibility. This is the Maratos effect: the quadratic curvature of the constraints, invisible to the linearized QP, can make ${\varphi }_1$ rise on a step that genuinely advances the iterate, blocking the unit step and the fast local rate unless a second-order correction is added.

Key theorem with proof Intermediate+

The signature result is that the SQP step is exactly the Newton step on the nonlinear KKT system. This identification is the source of SQP's local quadratic convergence and the reason the QP subproblem must use the Hessian of the Lagrangian rather than of the objective. It is the precise sense in which SQP is "Newton for constrained optimization" ^{[Nocedal & Wright §18.1]}.

Theorem (SQP is Newton's method on the KKT system; local quadratic convergence). For the equality-constrained NLP $\min f(x)$ s.t. $c(x)=0$, let F(x, \lambda) = \begin{psmallmatrix}\nabla f(x) - A(x)^\top\lambda \\ c(x)\end{psmallmatrix} be the KKT map. The SQP step $(p_k,{\lambda }_{k+1})$ defined by the QP subproblem solves the Newton system F'(x_k, \lambda_k)\begin{psmallmatrix} p_k \\ \lambda_{k+1} - \lambda_k\end{psmallmatrix} = -F(x_k, \lambda_k). If $(x^{\star },{\lambda }^{\star })$ satisfies the LICQ and the second-order sufficiency condition of 44.02.02, then $F^{\prime }(x^{\star },{\lambda }^{\star })$ is nonsingular, and the SQP iteration $(x_{k+1},{\lambda }_{k+1})=(x_k+p_k,{\lambda }_{k+1})$ converges q-quadratically to $(x^{\star },{\lambda }^{\star })$ from any sufficiently close start.

Proof. The Jacobian of $F$ is

$$F^{\prime }(x,\lambda )=\left[\begin{array}{cc}{\nabla }_{xx}^{2}L(x,\lambda )& -A(x{)}^{\top }\\ A(x)& 0\end{array}\right],$$

since differentiating $\nabla f(x)-A(x{)}^{\top }\lambda$ in $x$ gives ${\nabla }^{2}f-{\sum }_i{\lambda }_i{\nabla }^2{c}_i={\nabla }_{xx}^{2}L$ and in $\lambda$ gives $-A^{\top }$, while differentiating $c(x)$ in $x$ gives $A$. The Newton system F'(x_k, \lambda_k)\begin{psmallmatrix} p_k \\ \delta_\lambda\end{psmallmatrix} = -F(x_k, \lambda_k) with ${\delta }_{\lambda }={\lambda }_{k+1}-{\lambda }_k$ reads

$${\nabla }_{xx}^2{L}_k{p}_k-A_k^{\top }{\delta }_{\lambda }=-(\nabla f_k-A_k^{\top }{\lambda }_k),A_k{p}_k=-c_k.$$

Substituting ${\delta }_{\lambda }={\lambda }_{k+1}-{\lambda }_k$ into the first row collapses the $A_k^{\top }{\lambda }_k$ terms: ${\nabla }_{xx}^2{L}_k{p}_k-A_k^{\top }{\lambda }_{k+1}=-\nabla f_k$. The pair $(p_k,{\lambda }_{k+1})$ therefore solves

$$\left[\begin{array}{cc}{\nabla }_{xx}^2{L}_k& -A_k^{\top }\\ A_k& 0\end{array}\right]\left[\begin{array}{c}{p}_k\\ {\lambda }_{k+1}\end{array}\right]=\left[\begin{array}{c}-\nabla f_k\\ -c_k\end{array}\right],$$

which is exactly the KKT system of the QP subproblem of the Formal definition. So the SQP step equals the Newton step on $F$.

Nonsingularity of $F^{\prime }(x^{\star },{\lambda }^{\star })$: with $A^{\star }=A(x^{\star })$ of full row rank (LICQ) and ${\nabla }_{xx}^2{L}^{\star }$ positive definite on $\ker A^{\star }$ (second-order sufficiency), the inertia condition of 44.04.01 makes the saddle-point matrix nonsingular — indeed its inertia is $(n,m,0)$. Newton's method on a $C^1$ map with Lipschitz Jacobian and nonsingular Jacobian at a root converges q-quadratically locally by the standard analysis of 44.03.03: writing $z=(x,\lambda )$, $z_{k+1}-z^{\star }=z_k-z^{\star }-F^{\prime }(z_k{)}^{-1}F(z_k)$, and Taylor expansion of $F$ about $z^{\star }$ with $F(z^{\star })=0$ gives $\Vert z_{k+1}-z^{\star }\Vert \le C\Vert z_k-z^{\star }{\Vert }^2$ for $z_k$ near $z^{\star }$, where $C$ bounds $\Vert F^{\prime -1}\Vert$ times the Lipschitz constant of $F^{\prime }$. $\square$

Bridge. This theorem builds toward the inequality-constrained and quasi-Newton SQP of the Advanced results, where the same KKT-Newton step is computed with an active-set QP and a damped-BFGS Lagrangian Hessian, and it appears again in interior-point NLP, which applies Newton to a barrier-perturbed version of this very map $F$. This is exactly the constrained lift of Newton's method 44.03.03: where unconstrained Newton solves $\nabla f=0$ by linearizing the gradient, SQP solves the KKT map $F=0$ by linearizing it, and the QP subproblem is nothing but that linearization re-expressed as a minimization. The foundational reason the Hessian of the Lagrangian must appear — not the Hessian of the objective — is that $F$ contains the $-A^{\top }\lambda$ term whose $x$-derivative is precisely $-{\sum }_i{\lambda }_i{\nabla }^2{c}_i$, so the QP that reproduces Newton's step inherits the full ${\nabla }_{xx}^{2}L$. Putting these together, SQP generalises the active-set QP solve of 44.04.01 from a single fixed quadratic problem to a sequence of QPs whose data are relinearized each step, and the working set of the inner QP is dual to the active-set guess of the KKT conditions of 44.02.02: the inner QP's complementary slackness is SQP's running estimate of which nonlinear constraints are active at the solution, and convergence is the fixed point where the QP active set, the multipliers, and the linearization all agree.

Exercises Intermediate+

Advanced results Master

The KKT-Newton step, exactness, and the choice of Hessian

The equality-constrained SQP step solves the saddle-point system \begin{psmallmatrix}\nabla^2_{xx} L_k & -A_k^\top \\ A_k & 0\end{psmallmatrix}\begin{psmallmatrix} p_k \\ \lambda_{k+1}\end{psmallmatrix} = \begin{psmallmatrix}-\nabla f_k \\ -c_k\end{psmallmatrix}, and the identification of this with the Newton step on the KKT map $F$ forces the (1,1) block to be ${\nabla }_{xx}^{2}L$ and nothing else ^{[Nocedal & Wright §18.1]}. The matrix is nonsingular under LICQ ($A_k$ full row rank) and second-order sufficiency ($Z_k^{\top }{\nabla }_{xx}^2{L}_k{Z}_k\succ 0$ for $Z_k$ a basis of $\ker A_k$), the inertia condition $(n,m,0)$ of 44.04.01; the reduced-Hessian form solves $Z_k^{\top }{\nabla }_{xx}^2{L}_k{Z}_k{p}_Z=-Z_k^{\top }\nabla f_k$ for the $(n-m)$-dimensional tangential component, the reduced-Hessian SQP that needs only the projected Lagrangian curvature. Local q-quadratic convergence follows from Newton's analysis: under a Lipschitz $F^{\prime }$ and nonsingular $F^{\prime }(z^{\star })$, $\Vert z_{k+1}-z^{\star }\Vert =O(\Vert z_k-z^{\star }{\Vert }^2)$ ^{[Boggs & Tolle 1995]}. When the exact ${\nabla }_{xx}^2{L}_k$ is replaced by a quasi-Newton $B_k$, the rate drops to q-superlinear exactly when the Dennis-Moré condition holds along the steps, the constrained analogue of the unconstrained result of 44.03.04.

Quasi-Newton Lagrangian Hessians and Powell damping

The Lagrangian Hessian is generically indefinite — curved constraints with nonzero multipliers contribute $-{\sum }_i{\lambda }_i{\nabla }^2{c}_i$, which can have any inertia — so a naive BFGS update of $B_k\approx {\nabla }_{xx}^2{L}_k$ may fail the curvature condition $s_k^{\top }{y}_k>0$ that the hereditary-positivity theorem of 44.03.04 requires. Powell's damped BFGS modifies the secant pair to ${\hat{y}}_k={\theta }_k{y}_k+(1-{\theta }_k)B_k{s}_k$, guaranteeing $s_k^{\top }{\hat{y}}_k\ge 0.2s_k^{\top }{B}_k{s}_k>0$ and hence $B_{k+1}\succ 0$, at the cost of biasing $B_k$ toward positive definiteness even where the true reduced Hessian is the relevant object ^{[Nocedal & Wright §18.3]}. The cleaner alternative maintains a positive-definite approximation of the reduced Hessian $Z_k^{\top }{\nabla }_{xx}^2{L}_k{Z}_k$ only, which second-order sufficiency does guarantee to be positive definite at the solution, so no damping is needed; this is the basis of reduced-Hessian SQP solvers. The SR1 update, tolerant of indefiniteness, suits trust-region SQP where the subproblem absorbs negative curvature, paralleling its unconstrained role.

Globalization: merit functions, the Maratos effect, and filters

Local SQP converges only from near the solution; globalization forces progress from arbitrary starts. The ${\ell }_1$ merit function ${\varphi }_1(x;\mu )=f(x)+\mu \Vert c(x){\Vert }_1$ (with the negative-part penalty on inequalities) is exact: for $\mu >\Vert {\lambda }^{\star }{\Vert }_{\infty }$, a local minimizer of the NLP is a local minimizer of ${\varphi }_1$, and the SQP step is a descent direction for ${\varphi }_1$ under that threshold ^{[Nocedal & Wright §18.5]}. Nonsmoothness of $\Vert \cdot {\Vert }_1$ is the price of exactness; the smooth augmented-Lagrangian merit function ${\varphi }_{\mathrm{AL}}(x;\lambda ,\mu )=f-{\lambda }^{\top }c+\frac{\mu }{2}\Vert c{\Vert }^2$ avoids nonsmoothness but needs a multiplier estimate. The Maratos effect is the obstruction: a unit step improving both $f$ and $\Vert c\Vert$ can increase ${\varphi }_1$ because the linearized constraints miss the $O(\Vert p{\Vert }^2)$ feasibility error of the curved constraints, so the merit-function line search rejects the very step that gives quadratic convergence. The cures are the second-order correction — an extra step ${\hat{p}}_k$ with $A_k{\hat{p}}_k=-c(x_k+p_k)$ restoring feasibility to higher order — and watchdog / nonmonotone strategies that tolerate occasional merit increases. Filter methods sidestep the penalty parameter entirely: a trial point is accepted if it improves either $f$ or the constraint-violation measure $h(x)=\Vert c^{-}(x)\Vert$ relative to a filter of past $(f,h)$ pairs, treating optimization as a biobjective problem and avoiding both the $\mu$-estimation problem and much of the Maratos difficulty ^{[Fletcher & Leyffer 2002]}.

Line-search versus trust-region SQP and inconsistent linearizations

Line-search SQP computes the QP step and then a step length along it to reduce the merit function, requiring a positive-definite (or damped) Hessian so the step is a descent direction. Trust-region SQP instead bounds $\Vert p\Vert \le {\Delta }_k$ in the QP and accepts or rejects by a gain ratio, allowing indefinite ${\nabla }_{xx}^2{L}_k$ and exploiting negative curvature, but it faces inconsistent linearized constraints: the linearized feasible set $\{p:A_{k}p+c_k=0,\Vert p\Vert \le {\Delta }_k\}$ can be empty. The Byrd-Omojokun composite-step approach splits $p$ into a normal step reducing linearized infeasibility within the trust region and a tangential step reducing the model on the linearized-constraint null space; the Sℓ1QP / SLQP approach relaxes the constraints into the ${\ell }_1$ penalty so the QP is always feasible. These constructions make trust-region SQP robust on highly nonlinear or degenerate problems where line-search SQP stalls.

Synthesis. Sequential quadratic programming is exactly Newton's method 44.03.03 applied to the KKT map of 44.02.02, and the central insight of this unit is that this single identification dictates everything downstream: the QP subproblem's objective Hessian must be ${\nabla }_{xx}^{2}L$ because that is the $(1,1)$ block of the KKT Jacobian, the subproblem is solved by the active-set QP of 44.04.01 because that is the inner Newton solve, and the local rate is q-quadratic because Newton's rate is q-quadratic under a nonsingular Jacobian — nonsingular here by the inertia condition $(n,m,0)$ that LICQ and second-order sufficiency supply. The foundational reason SQP needs globalization at all is that Newton's quadratic rate is only local, so a merit function or filter must measure global progress, and this is exactly where the Maratos effect intrudes: the linearized constraints discard the $O(\Vert p{\Vert }^2)$ curvature that the merit function then charges back, cured by a second-order correction that restores feasibility to $O(\Vert p{\Vert }^3)$.

Putting these together, SQP generalises the active-set QP solve from one fixed quadratic problem to a relinearized sequence, the inner working set is dual to the running estimate of the NLP active set, and the quasi-Newton damped-BFGS Hessian generalises the unconstrained BFGS of 44.03.04 to an indefinite Lagrangian by forcing positivity on the reduced space. The bridge is the KKT system itself: it appears again in interior-point NLP, where the same map $F$ is perturbed by a barrier and solved by Newton along a central path, so SQP and interior-point methods are two linearizations of one set of optimality conditions — SQP discretizing the active set combinatorially, interior-point methods smoothing it analytically — and both rest on the saddle-point linear algebra proved nonsingular here and in 44.04.01.

Full proof set Master

Proposition 1 (SQP step equals the Newton-KKT step). For the equality NLP $\min f$ s.t. $c=0$ with KKT map $F(x,\lambda )=(\nabla f-A^{\top }\lambda ,c)$, the QP-subproblem solution $(p_k,{\lambda }_{k+1})$ solves F'(x_k,\lambda_k)\begin{psmallmatrix} p_k \\ \lambda_{k+1} - \lambda_k\end{psmallmatrix} = -F(x_k,\lambda_k).

Proof. Block-differentiate $F$: ${\partial }_x(\nabla f-A^{\top }\lambda )={\nabla }^{2}f-{\sum }_i{\lambda }_i{\nabla }^2{c}_i={\nabla }_{xx}^{2}L$, ${\partial }_{\lambda }(\nabla f-A^{\top }\lambda )=-A^{\top }$, ${\partial }_{x}c=A$, ${\partial }_{\lambda }c=0$, so F' = \begin{psmallmatrix}\nabla^2_{xx} L & -A^\top \\ A & 0\end{psmallmatrix}. The Newton system with ${\delta }_{\lambda }={\lambda }_{k+1}-{\lambda }_k$ has top row ${\nabla }_{xx}^2{L}_k{p}_k-A_k^{\top }({\lambda }_{k+1}-{\lambda }_k)=-(\nabla f_k-A_k^{\top }{\lambda }_k)$. Adding $A_k^{\top }{\lambda }_k$ to both sides and combining with the $A_k^{\top }{\lambda }_k$ on the left gives ${\nabla }_{xx}^2{L}_k{p}_k-A_k^{\top }{\lambda }_{k+1}=-\nabla f_k$; the bottom row is $A_k{p}_k=-c_k$. These two equations are the QP KKT system, whose solution is $(p_k,{\lambda }_{k+1})$. $\square$

Proposition 2 (nonsingularity of the KKT Jacobian at a regular solution). If $A^{\star }$ has full row rank (LICQ) and ${\nabla }_{xx}^2{L}^{\star }$ is positive definite on $\ker A^{\star }$ (second-order sufficiency), then $F^{\prime }(x^{\star },{\lambda }^{\star })$ is nonsingular with inertia $(n,m,0)$.

Proof. This is the inertia theorem of 44.04.01 applied to K = \begin{psmallmatrix}\nabla^2_{xx} L^\star & -A^{\star\top} \\ A^\star & 0\end{psmallmatrix} (the sign of the off-diagonal block does not affect inertia, being a symmetric congruence by $\mathrm{diag}(I,-I)$). With $Z$ a basis of $\ker A^{\star }$, $\mathrm{In}(K)=\mathrm{In}(Z^{\top }{\nabla }_{xx}^2{L}^{\star }Z)+(m,m,0)$; second-order sufficiency makes $Z^{\top }{\nabla }_{xx}^2{L}^{\star }Z\succ 0$, i.e. $\mathrm{In}=(n-m,0,0)$, so $\mathrm{In}(K)=(n,m,0)$, which has no zero eigenvalues. Hence $K=F^{\prime }$ is nonsingular. $\square$

Proposition 3 (local q-quadratic convergence of exact-Hessian SQP). Under the hypotheses of Proposition 2 with $f,c\in C^2$ and ${\nabla }_{xx}^{2}L$ Lipschitz near $(x^{\star },{\lambda }^{\star })$, the exact-Hessian SQP iteration converges q-quadratically to $(x^{\star },{\lambda }^{\star })$ from any sufficiently close start.

Proof. By Proposition 1 the iteration is Newton's method on $F$, and $F(x^{\star },{\lambda }^{\star })=0$ with $F^{\prime }(x^{\star },{\lambda }^{\star })$ nonsingular (Proposition 2). Write $z=(x,\lambda )$, $z^{\star }=(x^{\star },{\lambda }^{\star })$. The Newton update $z_{k+1}=z_k-F^{\prime }(z_k{)}^{-1}F(z_k)$ gives $z_{k+1}-z^{\star }=F^{\prime }(z_k{)}^{-1}[F^{\prime }(z_k)(z_k-z^{\star })-(F(z_k)-F(z^{\star }))]$. The bracket is the Taylor remainder, bounded by $\frac{1}{2}{L}_{F^{\prime }}\Vert z_k-z^{\star }{\Vert }^2$ with $L_{F^{\prime }}$ the Lipschitz constant of $F^{\prime }$. For $z_k$ in a neighborhood where $\Vert F^{\prime }(z_k{)}^{-1}\Vert \le 2\Vert F^{\prime }(z^{\star }{)}^{-1}\Vert =:2\beta$ (continuity of the inverse), $\Vert z_{k+1}-z^{\star }\Vert \le \beta L_{F^{\prime }}\Vert z_k-z^{\star }{\Vert }^2$. Choosing the neighborhood radius below $1/(\beta L_{F^{\prime }})$ makes the iteration a contraction in the quadratic sense, so $z_k\to z^{\star }$ q-quadratically. $\square$

Proposition 4 (Powell damping preserves positive definiteness). With $B_k\succ 0$, ${\hat{y}}_k={\theta }_k{y}_k+(1-{\theta }_k)B_k{s}_k$ and ${\theta }_k$ as defined, the BFGS update using ${\hat{y}}_k$ yields $B_{k+1}\succ 0$.

Proof. By the computation of Exercise 5, $s_k^{\top }{\hat{y}}_k\ge 0.2s_k^{\top }{B}_k{s}_k>0$ since $B_k\succ 0$ and $s_k\ne 0$. The BFGS update $B_{k+1}=B_k-\frac{B_k{s}_k{s}_k^{\top }{B}_k}{s_k^{\top }{B}_k{s}_k}+\frac{{\hat{y}}_k{\hat{y}}_k^{\top }}{{\hat{y}}_k^{\top }{s}_k}$ then satisfies the hypotheses of the hereditary-positivity theorem of 44.03.04 (current matrix positive definite, curvature product $s_k^{\top }{\hat{y}}_k>0$), so $B_{k+1}\succ 0$. Moreover $B_{k+1}{s}_k={\hat{y}}_k$, a damped secant equation interpolating the true secant pair and the prediction $B_k{s}_k$. $\square$

Proposition 5 (${\ell }_1$ exactness and descent of the SQP step). Let $(x^{\star },{\lambda }^{\star })$ be a KKT point of the equality NLP satisfying second-order sufficiency. For $\mu >\Vert {\lambda }^{\star }{\Vert }_{\infty }$, $x^{\star }$ is a strict local minimizer of ${\varphi }_1(\cdot ;\mu )=f+\mu \Vert c{\Vert }_1$, and at a feasible-or-infeasible $x_k$ the SQP step $p_k$ with ${\nabla }_{xx}^2{L}_k\succ 0$ on $\ker A_k$ has directional derivative $D{\varphi }_1(x_k;p_k)\le -p_k^{\top }{\nabla }_{xx}^2{L}_k{p}_k-(\mu -\Vert {\lambda }_{k+1}{\Vert }_{\infty })\Vert c_k{\Vert }_1<0$ unless $(p_k,c_k)=0$.

Proof. Exactness: at $x^{\star }$, $c(x^{\star })=0$ and for any feasible direction $d$ (so $A^{\star }d=0$ to first order), ${\varphi }_1(x^{\star }+td)-{\varphi }_1(x^{\star })=f(x^{\star }+td)-f(x^{\star })+\mu \Vert c(x^{\star }+td){\Vert }_1$. The KKT stationarity $\nabla f^{\star }=A^{\star \top }{\lambda }^{\star }$ and $|{\lambda }_i^{\star }|<\mu$ make the linear term in any infeasible direction dominated by the penalty $\mu \Vert c{\Vert }_1$, while second-order sufficiency makes $f$ strictly increase along feasible directions; together ${\varphi }_1$ has a strict local minimum at $x^{\star }$ (the standard exact-penalty argument). Descent: the one-sided directional derivative of $\Vert c(x){\Vert }_1$ along $p_k$ is $-\Vert c_k{\Vert }_1$ because $A_k{p}_k=-c_k$ moves each $c_i$ toward $0$ at unit rate, so $D{\varphi }_1(x_k;p_k)=\nabla f_k^{\top }{p}_k-\mu \Vert c_k{\Vert }_1$. The QP KKT row gives $\nabla f_k=-{\nabla }_{xx}^2{L}_k{p}_k+A_k^{\top }{\lambda }_{k+1}$, so $\nabla f_k^{\top }{p}_k=-p_k^{\top }{\nabla }_{xx}^2{L}_k{p}_k+{\lambda }_{k+1}^{\top }{A}_k{p}_k=-p_k^{\top }{\nabla }_{xx}^2{L}_k{p}_k-{\lambda }_{k+1}^{\top }{c}_k$. Thus $D{\varphi }_1=-p_k^{\top }{\nabla }_{xx}^2{L}_k{p}_k-{\lambda }_{k+1}^{\top }{c}_k-\mu \Vert c_k{\Vert }_1\le -p_k^{\top }{\nabla }_{xx}^2{L}_k{p}_k-(\mu -\Vert {\lambda }_{k+1}{\Vert }_{\infty })\Vert c_k{\Vert }_1$ by Hölder. With ${\nabla }_{xx}^2{L}_k\succ 0$ on $\ker A_k$ and $\mu >\Vert {\lambda }_{k+1}{\Vert }_{\infty }$, both terms are nonpositive and not simultaneously zero unless $p_k=0$ and $c_k=0$. $\square$

Connections Master

• Newton's method for optimization 44.03.03 is the direct parent: SQP is Newton's method applied to the KKT map $F(x,\lambda )=(\nabla f-A^{\top }\lambda ,c)$ rather than to $\nabla f$ alone, so the unconstrained quadratic-convergence analysis transfers verbatim once the KKT Jacobian is shown nonsingular. The modified-Newton safeguards that repair an indefinite objective Hessian reappear here as Powell damping and reduced-Hessian SQP, which secure positive definiteness on the tangent space that second-order sufficiency controls, and the whole local theory is the constrained lift of the single-equation Newton iteration.

• The KKT conditions and constraint qualifications of 44.02.02 supply both the equations SQP linearizes and the regularity hypotheses for its convergence: stationarity, feasibility, dual feasibility, and complementary slackness are the four conditions the KKT map $F$ encodes, LICQ is the full-row-rank hypothesis on $A^{\star }$ making $F^{\prime }$ nonsingular, and second-order sufficiency is the reduced-Hessian positivity that fixes the inertia at $(n,m,0)$. The inner QP's complementary slackness is SQP's combinatorial estimate of which nonlinear constraints are active, so SQP terminates at the fixed point where the QP active set and the NLP active set coincide.

• Active-set methods for quadratic programming 44.04.01 are the inner engine SQP calls at every outer iteration: each SQP subproblem is precisely the equality- or inequality-constrained QP that unit solves, the inertia condition guaranteeing a well-posed QP step is inherited as the regularity hypothesis for the SQP step, and the warm-starting advantage of dual active-set QP is what makes the SQP inner loop cheap, since successive relinearized subproblems differ only slightly. SQP is the active-set QP solve repeated over a sequence of relinearized data.

• Quasi-Newton methods 44.03.04 provide the Lagrangian-Hessian approximation: the secant pair is formed from gradients of the Lagrangian rather than the objective, the hereditary-positivity theorem of that unit is what Powell damping arranges to satisfy despite an indefinite true Hessian, and the Dennis-Moré characterization there governs the q-superlinear rate of inexact-Hessian SQP. The augmented-Lagrangian merit function ties SQP to the augmented-Lagrangian / method-of-multipliers approach (unit 44.04.02), whose penalty-plus-multiplier objective is the smooth merit function SQP can use for globalization and whose multiplier updates parallel the SQP multiplier estimates ${\lambda }_{k+1}$.

Historical & philosophical context Master

Sequential quadratic programming originated with the 1963 doctoral thesis of Robert B. Wilson at Harvard, who proposed solving a nonlinear program by a sequence of quadratic-programming subproblems built from the second-order Lagrangian model; the method was for a time called the Wilson-Han-Powell method ^{[Wilson 1963]}. The approach lay relatively dormant until the mid-1970s, when Shih-Ping Han gave the first convergence analysis and connected the method to quasi-Newton updating and the exact ${\ell }_1$ penalty function in two influential papers ^{[Han 1976]} (Mathematical Programming 11, 263-282), and Michael J. D. Powell supplied the damped-BFGS update that keeps the Lagrangian Hessian approximation positive definite and proved global convergence with the ${\ell }_1$ merit function ^{[Powell 1978]}. Powell's 1978 contribution is the reason robust SQP became practical, and the damping rule still bears his name.

The Maratos effect — the failure of the unit step to reduce a merit function near the solution — was identified by N. Maratos in his 1978 thesis ^{[Maratos 1978]}, and the second-order correction and watchdog techniques curing it were developed through the 1980s by Mayne, Polak, Chamberlain, and others. The standard surveys and software-oriented treatments are due to Paul Boggs and Jon Tolle ^{[Boggs & Tolle 1995]} and Philip Gill, Walter Murray, and Michael Saunders, whose SNOPT solver implements line-search SQP with a limited-memory damped-BFGS Lagrangian Hessian. The penalty-free filter alternative was introduced by Roger Fletcher and Sven Leyffer in 2002 ^{[Fletcher & Leyffer 2002]}, reframing globalization as a biobjective acceptance test and influencing the interior-point solver IPOPT. The unifying synthesis in Nocedal and Wright ^{[Nocedal & Wright §18]} presents SQP and interior-point methods as the two dominant families for general nonlinear programming, both linearizations of the same KKT system.

Bibliography Master

@book{nocedalwright2006sqp,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@article{boggstolle1995,
  author  = {Boggs, Paul T. and Tolle, Jon W.},
  title   = {Sequential quadratic programming},
  journal = {Acta Numerica},
  volume  = {4},
  year    = {1995},
  pages   = {1--51}
}

@phdthesis{wilson1963,
  author = {Wilson, Robert B.},
  title  = {A simplicial algorithm for concave programming},
  school = {Harvard University, Graduate School of Business Administration},
  year   = {1963}
}

@article{han1976,
  author  = {Han, Shih-Ping},
  title   = {Superlinearly convergent variable metric algorithms for general nonlinear programming problems},
  journal = {Mathematical Programming},
  volume  = {11},
  number  = {1},
  year    = {1976},
  pages   = {263--282}
}

@incollection{powell1978,
  author    = {Powell, Michael J. D.},
  title     = {A fast algorithm for nonlinearly constrained optimization calculations},
  booktitle = {Numerical Analysis (Dundee 1977)},
  series    = {Lecture Notes in Mathematics},
  volume    = {630},
  publisher = {Springer},
  year      = {1978},
  pages     = {144--157}
}

@phdthesis{maratos1978,
  author = {Maratos, Nicholas},
  title  = {Exact penalty function algorithms for finite-dimensional and control optimization problems},
  school = {Imperial College, University of London},
  year   = {1978}
}

@article{fletcherleyffer2002,
  author  = {Fletcher, Roger and Leyffer, Sven},
  title   = {Nonlinear programming without a penalty function},
  journal = {Mathematical Programming},
  volume  = {91},
  number  = {2},
  year    = {2002},
  pages   = {239--269}
}