Sqp active set and augmented lagrangian methods

Use the $C^2$ nonlinear program convention of Inequality constrained programs, tangent cones, constraint qualifications, and KKT: minimize a $C^2$ objective $f:U\to \mathbb{R}$ on an open $U\subseteq {\mathbb{R}}^n$, subject to $h(x)=0$ and componentwise $g(x)\le 0$. Fix a current point $x\in U$ and a symmetric positive-definite matrix $B\in {\mathbb{R}}^{n\times n}$. The SQP quadratic subproblem is ${\min }_{p\in {\mathbb{R}}^n}\mathrm{\nabla }f(x{)}^{T}p+\frac{1}{2}{p}^{T}Bp\text{subject to}h(x)+Dh(x)p=0,g(x)+Dg(x)p\le 0.$ The variable $p$ is the proposed displacement. Its feasible set is the polyhedron defined by the displayed affine constraints. A constraint index $i$ is active at $p$ when $g_i(x)+D{g}_i(x)p=0$. For equality multiplier $\nu$ and inequality multipliers $\lambda \ge 0$, a KKT tuple for the subproblem satisfies primal feasibility, $Bp+\mathrm{\nabla }f(x)+Dh(x{)}^T\nu +Dg(x{)}^T\lambda =0,{\lambda }_i(g_i(x)+D{g}_i(x)p)=0(1\le i\le m)\mathrm{.}$ Rows of $Dh(x)$ and active rows of $Dg(x)$ are stacked in that order in the subproblem KKT matrix $\left[\begin{array}{cc}B& A^T\\ A& 0\end{array}\right]$.

All inequality signs and multiplier signs here agree with the source program: $g_i\le 0$ and ${\lambda }_i\ge 0$.

Use the $C^2$ program, dimensions, gradient conventions, and Lagrangian $L(x,\nu ,\lambda )=f(x)+{\nu }^{T}h(x)+{\lambda }^{T}g(x)$ of Inequality constrained programs, tangent cones, constraint qualifications, and KKT. Let $\rho >0$, $\nu \in {\mathbb{R}}^p$, and $\lambda \in {\mathbb{R}}_{+}^m$. The equality augmented Lagrangian is ${\mathcal{L}}_{\rho }^E(x,\nu )=f(x)+{\nu }^{T}h(x)+\frac{\rho }{2}\mathrm{\parallel }h(x){\mathrm{\parallel }}_2^2\mathrm{.}$ For inequalities, with $[z{]}_i^{+}=\max \{z_i,0\}$, the projected (Powell–Hestenes–Rockafellar) augmented Lagrangian is ${\mathcal{L}}_{\rho }(x,\nu ,\lambda )=f(x)+{\nu }^{T}h(x)+\frac{\rho }{2}\mathrm{\parallel }h(x){\mathrm{\parallel }}_2^2+\frac{\mathrm{\parallel }[\lambda +\rho g(x){]}_{+}{\mathrm{\parallel }}_2^2-\mathrm{\parallel }\lambda {\mathrm{\parallel }}_2^2}{2\rho }\mathrm{.}$ After an inner candidate $x^{+}$ is produced, the multiplier update is ${\nu }^{+}=\nu +\rho h(x^{+}),{\lambda }^{+}=[\lambda +\rho g(x^{+}){]}_{+}\mathrm{.}$ The bracket is componentwise. A declared inner stationarity residual is $\mathrm{\parallel }{\mathrm{\nabla }}_x{\mathcal{L}}_{\rho }(x^{+},\nu ,\lambda ){\mathrm{\parallel }}_2$; an inner procedure must report the residual it achieved or an explicit failure status.

The equality and inequality formulas are distinct branches. For an inequality with ${\lambda }_i+\rho g_i(x)>0$, its summand equals ${\lambda }_i{g}_i(x)+\rho g_i(x{)}^2\mathrm{/}2$; when ${\lambda }_i+\rho g_i(x)\le 0$, its summand is constant in $x$.

Let $A\in {\mathbb{R}}^{r\times n}$ have full row rank, where $0\le r\le n$, and let $H\in {\mathbb{R}}^{n\times n}$ be symmetric and positive definite on $\ker A$: $z^{T}Hz>0$ whenever $0\mathrm{\ne }z\in \ker A$. Then $K=\left[\begin{array}{cc}H& A^T\\ A& 0\end{array}\right]$ is nonsingular. Here the zero-row case $r=0$ is allowed.

Use the nonlinear program and SQP subproblem conventions of The linearized quadratic subproblem in sequential quadratic programming. For $\rho >0$, define the nondifferentiable L1 merit function ${\psi }_{\rho }(x)=f(x)+\rho (\mathrm{\parallel }h(x){\mathrm{\parallel }}_1+\mathrm{\parallel }[g(x){]}_{+}{\mathrm{\parallel }}_1)\mathrm{.}$ For a subproblem step $p$ at $x$, its linearized predicted decrease is $D_{\rho }(x,p)=-[\mathrm{\nabla }f(x{)}^{T}p+\rho (\mathrm{\parallel }h(x)+Dh(x)p{\mathrm{\parallel }}_1-\mathrm{\parallel }h(x){\mathrm{\parallel }}_1+\mathrm{\parallel }[g(x)+Dg(x)p{]}_{+}{\mathrm{\parallel }}_1-\mathrm{\parallel }[g(x){]}_{+}{\mathrm{\parallel }}_1)]\mathrm{.}$ A trial fraction $t\in (0,1]$ satisfies the Armijo test with coefficient $\sigma \in (0,1)$ when ${\psi }_{\rho }(x+tp)\le {\psi }_{\rho }(x)-\sigma t{D}_{\rho }(x,p)\mathrm{.}$ The definition alone does not assert $D_{\rho }(x,p)>0$, existence of an accepted fraction, or convergence of a sequence of accepted SQP steps.

Fix a $C^2$ program as in Equality and inequality augmented Lagrangians and multiplier updates, a penalty $\rho >0$, finite positive integer outer cap $K$, finite positive integer per-call inner cap $M$, tolerances ${ϵ}_k\ge 0$, and KKT tolerance $\tau \ge 0$. A supplied finite-budget inner procedure receives $(x_k,{\nu }_k,{\lambda }_k,\rho ,{ϵ}_k,M)$, performs at most $M$ inner iterations, and returns one of: success(x_k^+,\widehat\epsilon_k) with $x_k^{+}\in U$ and ${\widehat{ϵ}}_k=\mathrm{\parallel }{\mathrm{\nabla }}_x{\mathcal{L}}_{\rho }(x_k^{+},{\nu }_k,{\lambda }_k){\mathrm{\parallel }}_2\le {ϵ}_k$; budget-exhausted(x_{\rm last},\widehat\epsilon_{\rm last}) with $x_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\in U$ and ${\widehat{ϵ}}_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}=\mathrm{\parallel }{\mathrm{\nabla }}_x{\mathcal{L}}_{\rho }(x_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}},{\nu }_k,{\lambda }_k){\mathrm{\parallel }}_2$; or failure(data) when it cannot continue or report a residual. Each inner iteration and report computation is finite, and the procedure returns by its cap.

Initialize $x_0\in U$, ${\nu }_0\in {\mathbb{R}}^p$, and ${\lambda }_0\in {\mathbb{R}}_{+}^m$. For $k=0,\dots ,K-1$:

1. Call the inner procedure with cap $M$. On budget-exhausted(x_{\rm last},\widehat\epsilon_{\rm last}), return inner-budget-exhausted with current $(x_k,{\nu }_k,{\lambda }_k)$, that point, and residual. On failure(data), return inner-failure with the data. If a purported success reports a residual exceeding ${ϵ}_k$, return inner-failure with the reported data. Otherwise store its reported inner residual ${\widehat{ϵ}}_k$.
2. Set ${\nu }_{k+1}={\nu }_k+\rho h(x_k^{+}),{\lambda }_{k+1}=[{\lambda }_k+\rho g(x_k^{+}){]}_{+}\mathrm{.}$
3. Set $r_k=r_{\mathrm{K}\mathrm{K}\mathrm{T}}(x_k^{+},{\nu }_{k+1},{\lambda }_{k+1})$. If $r_k\le \tau$, return kkt-tolerance-reached with $x_k^{+}$, $({\nu }_{k+1},{\lambda }_{k+1})$, $r_k$, and ${\widehat{ϵ}}_k$; otherwise set $x_{k+1}=x_k^{+}$ and continue.

If all $K$ outer iterations finish without that test passing, return outer-budget-exhausted with $x_K$, $({\nu }_K,{\lambda }_K)$, the last KKT residual $r_{K-1}$, and inner residual ${\widehat{ϵ}}_{K-1}$. The routine claims neither convergence nor that the inner procedure succeeds within its cap.

Domain preservation, finite-cap termination and reported-residual guarantees are proved in The augmented-Lagrangian multiplier procedure preserves its domain and returns within its caps ↗.

On the admitted inputs of Finite-budget augmented-Lagrangian multiplier method, with finite positive integer caps $K,M$, and with its supplied inner procedure satisfying its stated finite-iteration/report contract, the procedure terminates with one of inner-budget-exhausted, inner-failure, kkt-tolerance-reached, or outer-budget-exhausted. It performs at most $KM$ inner iterations and at most $K$ outer KKT residual tests. Every multiplier iterate satisfies ${\lambda }_k\ge 0$, and every point used for a multiplier update or KKT test lies in the program domain $U$.

A kkt-tolerance-reached return reports a KKT residual at most $\tau$ at the returned primal point and updated multipliers, together with the achieved inner residual at most its declared ${ϵ}_k$. An outer-budget-exhausted return includes the last reported inner and KKT residuals. An inner-budget-exhausted return retains the current outer state and the inner procedure's last point and residual; an inner-failure return preserves its declared failure data. None of these conclusions asserts that a tolerance will be reached, that an inner call will succeed within its cap, or that the finite procedure converges.

Let $q(p)=c^{T}p+\frac{1}{2}{p}^{T}Bp$ on ${\mathbb{R}}^n$, where $B=B^T$ is positive definite. Let the feasible set be the nonempty polyhedron $C=\{p:Ap=b,G_{i}p+d_i\le 0(1\le i\le m)\},$ where the equality rows of $A$ are linearly independent (zero rows are allowed). Then $q$ has a unique minimizer $p_{\ast }$. There are equality multipliers $\nu$ and inequality multipliers ${\lambda }_i\ge 0$ such that $B{p}_{\ast }+c+A^T\nu +{\sum }_i{\lambda }_i{G}_i^T=0,{\lambda }_i(G_i{p}_{\ast }+d_i)=0.$ They can be chosen so that the equality rows and the active inequality rows with ${\lambda }_i>0$ are linearly independent. This KKT tuple certifies the global minimizer.

Input an SQP subproblem from The linearized quadratic subproblem in sequential quadratic programming, using exact real arithmetic. Let $q$ and $m$ be the numbers of equality and inequality constraints. Put $A^{\mathrm{e}\mathrm{q}}=Dh(x)$, $b^{\mathrm{e}\mathrm{q}}=-h(x)$, $G=Dg(x)$, $d=g(x)$, and $c=\mathrm{\nabla }f(x)$, so $G_i=D{g}_i(x)$ and $d_i=g_i(x)$ for $1\le i\le m$. First reduce the linearized equality system $A^{\mathrm{e}\mathrm{q}}p=b^{\mathrm{e}\mathrm{q}}$: test consistency, and, if consistent, retain the lexicographically first maximal independent set $E\subseteq \{1,\dots ,q\}$ of equality row indices with their right-hand sides. If it is inconsistent, return QP-infeasible. Within each retained row set, use increasing original indices; an empty row set contributes no rows or right-hand-side entries.

For each subset $J\subseteq \{1,\dots ,m\}$ in increasing bit-mask order:

1. Stack the equality rows $(A^{\mathrm{e}\mathrm{q}}{)}_E$ and the inequality rows $G_J$, in that order. If these rows are dependent, skip $J$.
2. Treat the selected inequalities as equalities $G_{i}p=-d_i$ and solve $\left[\begin{array}{cc}B& A_J^T\\ A_J& 0\end{array}\right]\left(\genfrac{}{}{0px}{}{p}{\eta }\right)=\left(\genfrac{}{}{0px}{}{-c}{b_J}\right),$ where $A_J=\left(\genfrac{}{}{0px}{}{(A^{\mathrm{e}\mathrm{q}}{)}_E}{G_J}\right)$ and $b_J=\left(\genfrac{}{}{0px}{}{(b^{\mathrm{e}\mathrm{q}}{)}_E}{-d_J}\right)$. Thus the equality entries of $b_J$ are $-h_a(x)$ for $a\in E$, followed by $-g_i(x)$ for $i\in J$, in the declared row order. The multiplier vector $\eta$ is stored in this same order. The KKT matrix is nonsingular by The SQP KKT matrix is nonsingular under positive reduced curvature.
3. Discard the candidate if any linearized inequality is violated or any selected inequality multiplier is negative. Otherwise store $(p,\eta ,J)$.

If no candidate is stored, return QP-infeasible. Otherwise return the stored candidate with least quadratic objective, breaking an exact tie by the least subset bit mask, as solution(p, nu, lambda, E, J). Here $\nu$ is the full equality-multiplier vector, initialized to zero and filled from the equality components of $\eta$ at indices $E$; $\lambda$ is the full inequality-multiplier vector, initialized to zero and filled from the selected components at indices $J$. A finite-precision implementation that cannot complete a rank test or solve must return numerical-failure; this definition's exact-arithmetic branch has no such failure. It requires no feasible initial step and specifies no pivoting rule for an iterative working set solver.

Input a strictly convex quadratic program $q(z)=\frac{1}{2}{z}^{T}Bz+c^{T}z,Az=b,G_{i}z+d_i\le 0(1\le i\le m),$ with $B=B^T\succ 0$, a feasible starting point $z_0$, a working set $W_0$ of active inequality indices whose rows together with the equality rows are independent, and a finite iteration cap $N\ge 1$. Fix ties by least index. For each iteration $k=0,\dots ,N-1$:

1. Solve the equality-constrained direction problem ${\min }_u(B{z}_k+c{)}^{T}u+\frac{1}{2}{u}^{T}Bu\text{subject to}Au=0,G_{i}u=0(i\in W_k)\mathrm{.}$ Its KKT matrix is nonsingular by The SQP KKT matrix is nonsingular under positive reduced curvature. If the linear solve fails, return numerical-failure.
2. If $u=0$, inspect the inequality multipliers ${\mu }_i$ for $i\in W_k$. If every ${\mu }_i\ge 0$, return solution(z_k, multipliers, W_k). Otherwise delete the least-index $j\in W_k$ with ${\mu }_j<0$ and continue at the same feasible point with the reduced working set.
3. If $u\mathrm{\ne }0$, for every $i\mathrm{\notin }{W}_k$ with $G_{i}u>0$ compute ${\alpha }_i=-\frac{G_i{z}_k+d_i}{G_{i}u},{\alpha }_k=\min (1,{\min }_{i\mathrm{\notin }{W}_k,G_{i}u>0}{\alpha }_i),$ using ${\alpha }_k=1$ when there is no such index. If ${\alpha }_k=0$, return degenerate-block. Otherwise set $z_{k+1}=z_k+{\alpha }_{k}u$. If ${\alpha }_k<1$, add the least-index blocker attaining ${\alpha }_k$ to $W_k$; if adding it makes the rows dependent, return dependent-blocker. If ${\alpha }_k=1$, the new point minimizes $q$ on the current working-set face, even if an unselected inequality becomes active at the endpoint. Set all those unselected multipliers to zero, and return if the current inequality multipliers are nonnegative; otherwise delete the least-index negative-multiplier constraint before continuing.

If the cap is reached first, return iteration-budget-exhausted with the last feasible iterate and multipliers. Every returned non-solution status is inconclusive about optimality. The algorithm does not silently add a zero-length blocking step.

Let $c_A:U\to {\mathbb{R}}^r$ collect the equality constraints and a specified set of active inequality constraints, in that order. Given $x,x+p\in U$, assume $A=D{c}_A(x)$ has full row rank and the SQP step satisfies $c_A(x)+Ap=0$. For $r>0$, compute $w=-A^T(A{A}^T{)}^{-1}{c}_A(x+p)$ and return $p+w$ as the corrected displacement. If the rank test fails, the inverse or evaluation fails, return correction-failure. If $r=0$, return $p$ with $w=0$. This is a correction for the specified active constraints; it does not certify feasibility of inactive constraints.

The full-row-rank inverse formula is supplied by If $A$ has full row rank, then $A^{+}=A^{\ast }(A{A}^{\ast }{)}^{-1}$, and the minimum-norm characterization by For every right-hand side $b$, $A^{+}b$ is the unique least-squares solution of minimum Euclidean norm, with right-hand side $-c_A(x+p)$. The zero-row branch returns the zero correction. Residual-order estimates under smoothness and uniform rank hypotheses are separate properties.

Let $c_A(x)=(h(x),g_I(x))$ stack all equalities and the identified active inequalities, and let $\mu =(\nu ,{\lambda }_I)$. For a current pair $(x,\mu )$, form $F_A(x,\mu )=\left(\genfrac{}{}{0px}{}{{\mathrm{\nabla }}_{x}L(x,\nu ,{\lambda }_I,0_{I^c})}{c_A(x)}\right),J_A(x,\mu )=\left[\begin{array}{cc}{\mathrm{\nabla }}_{xx}^{2}L(x,\nu ,{\lambda }_I,0_{I^c})& D{c}_A(x{)}^T\\ D{c}_A(x)& 0\end{array}\right]\mathrm{.}$ If $J_A$ is nonsingular, solve $J_A\left(\genfrac{}{}{0px}{}{p}{\delta \mu }\right)=-F_A(x,\mu )$ and return the full Newton pair $(x+p,\mu +\delta \mu )$. A failed rank test or solve returns kkt-solve-failure. The active set is supplied to this step; this algorithm has no line search and makes no global convergence claim.

Let $c_A(x)$ stack the equality and identified active constraints, and let $A=D{c}_A(x)$ have full row rank. Set $P=I-A^T(A{A}^T{)}^{-1}A$ when $A$ has positive row count and $P=I$ when it has zero rows. Given the exact Lagrangian Hessian $H$ and a symmetric positive-definite full-memory BFGS matrix $B$, define $H_{\mathrm{r}\mathrm{e}\mathrm{d}}=H+P(B-H)P\mathrm{.}$ Solve the active KKT system with $H_{\mathrm{r}\mathrm{e}\mathrm{d}}$ in its upper-left block and right-hand side $-F_A(x,\mu )$ as in Full-step exact-Hessian SQP after active-set identification. If the rows are dependent or the solve fails, return kkt-solve-failure.

For a curvature pair $(s,y)$ with $s^{T}y>0$, the optional next-model update is $B^{+}=B-\frac{(Bs)(Bs{)}^T}{s^{T}Bs}+\frac{y{y}^T}{s^{T}y};$ if $s^{T}y\le 0$, skip the update and retain $B$. The curvature pair is defined as in Bfgs curvature pairs and Hessian/inverse updates.

At $x\in U$, choose a positive-definite SQP model matrix and solve the exact quadratic subproblem by Exact exhaustive active-set solve for the SQP quadratic subproblem. If it reports infeasibility or failure, return that status. On a solution return, retain its step $p$, full QP multiplier vectors $({\nu }^{QP},{\lambda }^{QP})$, retained equality basis $E$, and selected inequality support $J$. The stacked rows $D{h}_E(x)$ and $D{g}_J(x)$ are independent, and the selected rows satisfy $h_E(x)+D{h}_E(x)p=0$ and $g_J(x)+D{g}_J(x)p=0$. Given parameters ${\rho }_0>0$, $\gamma >1$, $\beta \in (0,1)$, $\sigma \in (0,1)$ and finite integer caps $R,J_{\max }\ge 1$, keep the resulting step $p$ fixed, initialize flags $P_{\mathrm{p}\mathrm{o}\mathrm{s}}=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}$ and $P_{\mathrm{d}\mathrm{o}\mathrm{m}}=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}$, and perform attempts $r=0,\dots ,R-1$ with ${\rho }_r={\rho }_0{\gamma }^r$:

1. Compute $D_r=D_{{\rho }_r}(x,p)$ from L1 exact-penalty merit and predicted decrease for SQP. If $D_r\le 0$, go to the next penalty. Otherwise set $P_{\mathrm{p}\mathrm{o}\mathrm{s}}=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$.
2. If $x+p\in U$, apply Minimum-norm second-order correction for identified active constraints to the auxiliary program with equality map $h_E$ and the same $f,g,U,B$, selecting inequalities $J$; thus its complete active map is $c_A=(h_E,g_J)$. The original QP step $p$ also solves this auxiliary program's QP, since the consistent equality-row reduction preserves the linearized feasible set. This call makes no residual-order claim for omitted nonlinear equality rows; every merit evaluation below still uses the full original $h,g$. If it returns a corrected displacement $d$ and $x+d\in U$, set $P_{\mathrm{d}\mathrm{o}\mathrm{m}}=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$ and test ${\psi }_{{\rho }_r}(x+d)\le {\psi }_{{\rho }_r}(x)-\sigma D_r$. If it passes, return accepted-soc with $x+d$, $p$, $({\nu }^{QP},{\lambda }^{QP})$, $E$, and $J$. If $x+p\mathrm{\notin }U$, skip the correction call.
3. For $j=0,\dots ,J_{\max }-1$, set $t_j={\beta }^j$. Whenever $x+t_{j}p\in U$, set $P_{\mathrm{d}\mathrm{o}\mathrm{m}}=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$ and test ${\psi }_{{\rho }_r}(x+t_{j}p)\le {\psi }_{{\rho }_r}(x)-\sigma t_j{D}_r\mathrm{.}$ On the first passing test, return accepted with $x+t_{j}p$, $t_j$, $p$, $({\nu }^{QP},{\lambda }^{QP})$, $E$, and $J$.

After all attempts, if $P_{\mathrm{p}\mathrm{o}\mathrm{s}}$ is false, return nonpositive-predicted-decrease-budget. If $P_{\mathrm{p}\mathrm{o}\mathrm{s}}$ is true but $P_{\mathrm{d}\mathrm{o}\mathrm{m}}$ is false, return domain-exit: no SOC or ordinary trial could be evaluated in $U$. Otherwise return line-search-budget-exhausted. These finite tests do not guarantee acceptance or convergence.

For the SQP subproblem of The linearized quadratic subproblem in sequential quadratic programming with $B$ symmetric positive definite, the exact algorithm of Exact exhaustive active-set solve for the SQP quadratic subproblem terminates after finitely many subset tests. It returns QP-infeasible exactly when the subproblem's polyhedron is empty; otherwise it returns the unique global minimizer, full equality and inequality multiplier vectors, and the retained equality basis $E$ and inequality support $J$ of its KKT certificate.

Consider a feasible SQP quadratic subproblem with $B\succ 0$, $m$ inequality rows, and $r$ independent equality rows. Run Feasible active-set QP solve with blocking constraints and a finite cap with an independent initial working set and cap $N\ge (n+2)2^m$. Assume exact subproblem solves, every nonzero working-set direction has a strictly positive maximal feasible step, and a blocker is selected by the algorithm's least-index tie rule. Then the algorithm returns the unique global minimizer and a KKT certificate in at most $N$ iterations. If a zero blocking step, dependent blocker, failed solve, or smaller user cap occurs, the algorithm returns its stated inconclusive status and no optimality claim follows.

The positive-step hypothesis is the nondegeneracy condition that prevents zero-length working-set cycling. The proof also shows that a working set already minimized with negative multipliers cannot recur after progress.