Globalization for Constrained Optimization

References: Biegler (2010), Nonlinear Programming, §§5.5–5.8, pp.109–130; Nocedal and Wright (2006), Numerical Optimization, §§15.4–15.6, pp.435–446 and Theorem 17.3, p.507. Use the Biegler errata. This reference supplies the complete penalty, filter, composite-step and second-order-correction details behind Lecture 22. The SQP implementation uses these ideas in an actual algorithm.

Two quantities to improve¶

Consider $\min_{\mathbf x}f(\mathbf x)$ subject to $\mathbf h(\mathbf x)=\mathbf0$. Use the row Jacobian $\mathbf J=\nabla\mathbf h^{\mathsf T}$, the sign convention $L=f+\mathbf v^{\mathsf T}\mathbf h$, gradient $\mathbf g=\nabla f$, and Hessian $\mathbf W=\nabla_{\mathbf{xx}}^2L$. A step should reduce constraint violation and eventually improve the objective on the feasible set. Raw objective decrease alone can reward moving away from the constraints. Raw violation decrease alone can converge to a feasible nonoptimal point.

The equality QP has objective $\mathbf g^{\mathsf T}\mathbf d+\frac12\mathbf d^{\mathsf T}\mathbf W\mathbf d$ and constraint $\mathbf J\mathbf d=-\mathbf h$. Its KKT multiplier is the updated multiplier $\bar{\mathbf v}$:

Equality Newton owns the derivation, normal/tangential decomposition and multiplier increment distinction. Independent rows and positive reduced curvature make the equality QP a unique minimization problem. A merit function combines progress in one scalar; a filter keeps the two goals separate. Neither supplies a global-minimum certificate for a nonconvex NLP.

Quadratic penalties and conditioning¶

The smooth quadratic penalty is

Stationarity gives $\mathbf g+\rho_{\rm pen}\mathbf J^{\mathsf T}\mathbf h=\mathbf0$. Thus $\rho_{\rm pen}\mathbf h$ estimates the multiplier. With a nonzero limiting multiplier, the residual must remain nonzero at finite weight; the constraint is approached as the weight grows. This motivates penalty algorithms, but a weight tending to infinity is inconvenient for an acceptance function intended to permit a fast local Newton rate.

For $f=x_1+x_2$ and $h=x_1^2+x_2^2-2$, the constrained minimum is $(-1,-1)$ with $v^*=1/2$. Cauchy’s inequality gives $f\ge-\sqrt2\|\mathbf x\|$, so the quadratic-penalty minimum is on the negative diagonal $\mathbf x=(-t,-t)$, $t>1$. It solves

At that point the Hessian is $2\rho_{\rm pen}h\mathbf I+4\rho_{\rm pen}\mathbf x\mathbf x^{\mathsf T}$. Its tangential and normal eigenvalues are $2\rho_{\rm pen}h$ and $2\rho_{\rm pen}h+8\rho_{\rm pen}t^2$. The former approaches1 while the latter grows like $8\rho_{\rm pen}$. Better feasibility therefore comes with increasing anisotropy and condition number. The numerical table below computes the actual radial roots and both eigenvalues.

A general smooth residual-only penalty $f+\rho_{\rm pen}\varphi(\mathbf h)$, with $\varphi\ge0$ and $\varphi(\mathbf0)=0$, has $\nabla\varphi(\mathbf0)=\mathbf0$. At a feasible point its gradient is exactly $\nabla f$. It cannot have an unconstrained local minimum there when $\nabla f\ne\mathbf0$. This is a qualified obstruction, not a statement that smooth penalties are never exact. For $f=x^2,h=x$, the penalty $(1+\rho_{\rm pen})x^2$ is exact for every positive weight. Its constrained multiplier and objective gradient vanish.

Augmented Lagrangians and variable multipliers¶

The augmented Lagrangian is

At a feasible KKT point with the fixed true multiplier, its gradient vanishes and its Hessian is $\mathbf W+\rho_{\rm pen}\mathbf J^{\mathsf T}\mathbf J$. Under LICQ and SOSC, this matrix is positive definite for sufficiently large finite weight. To see why, use orthonormal bases $\mathbf Y,\mathbf Z$ for the normal and tangent spaces. The tangent block $\mathbf Z^{\mathsf T}\mathbf W\mathbf Z$ is positive definite. The normal block receives $\rho_{\rm pen}\mathbf Y^{\mathsf T}\mathbf J^{\mathsf T}\mathbf J\mathbf Y$, positive definite under full row rank. Its Schur complement after eliminating the tangent block is positive definite once this growing normal term dominates the bounded original block and coupling. Thus the fixed-multiplier augmented function has a strict local minimum at the constrained solution. Biegler p.110 states this with LICQ and SOSC.

The true multiplier is unknown; practical augmented-Lagrangian algorithms alternate primal solves and multiplier updates rather than minimize jointly in $\mathbf x,\mathbf v$. A nonzero constraint residual makes the multiplier term linear and unbounded below in some multiplier direction, so joint unconstrained minimization is the wrong problem.

Where $\mathbf J$ has full row rank, a smooth least-squares multiplier estimate is

Substituting this into a multiplier-dependent merit function gives a Fletcher-type differentiable construction, rather than a residual-only penalty. Its smoothness requires rank locally and its derivatives include derivatives of the multiplier estimate. Dropping those terms changes the construction. This approach is distinct from simply freezing the multiplier in an augmented Lagrangian. See Biegler Eq.5.58 p.110 and Nocedal–Wright p.436. Nonsmooth exact penalties avoid these derivative costs.

Exact nonsmooth penalties: statement, proof and boundary case¶

Define

Exactness here means that a constrained local minimizer is also a local minimizer of this unconstrained merit function for a finite penalty weight. It does not mean that every stationary point is feasible or that every minimum anywhere solves the NLP.

With $C^2$ data, a feasible KKT pair $(\mathbf x^*,\mathbf v^*)$, LICQ and SOSC, every $\rho_{\rm pen}>\|\mathbf v^*\|_q$ makes $\mathbf x^*$ a strict local minimum of $\phi_p$. The dual norm appears through Hölder’s inequality. Strictness needs the curvature assumption: $f=0,h=x_2$ satisfies LICQ and KKT with zero multiplier, but $\rho_{\rm pen}|x_2|$ is flat along the entire feasible $x_1$ axis. Nocedal–Wright Theorem 17.3 p.507 explicitly distinguishes its local-minimum conclusion from the additional SOSC conclusion. Do not infer strictness from a multiplier threshold alone.

Here is a complete contradiction proof of the SOSC statement. Suppose distinct $\mathbf x^k\to\mathbf x^*$ satisfy $\phi_p(\mathbf x^k)\le\phi_p(\mathbf x^*)$. Write $r_k=\|\mathbf x^k-\mathbf x^*\|_2$ and $\mathbf p_k=(\mathbf x^k-\mathbf x^*)/r_k$. Fix the true multiplier in $L$. Stationarity and Taylor’s theorem give

Put $\delta=\rho_{\rm pen}-\|\mathbf v^*\|_q>0$. Hölder gives

Bounded curvature and the assumed nonpositive left side imply $\|\mathbf h(\mathbf x^k)\|_p=O(r_k^2)$. Extract a convergent subsequence of unit directions, $\mathbf p_k\to\mathbf p$. The first-order constraint expansion divided by $r_k$ yields $\mathbf J\mathbf p=\mathbf0$ and $\|\mathbf p\|_2=1$. Divide the merit inequality by $r_k^2$ and discard its nonnegative residual term. In the limit it asserts $0\ge\frac12\mathbf p^{\mathsf T}\mathbf W\mathbf p$, contradicting SOSC. For the empty tangent space, the unit tangent conclusion itself is impossible. This proves strict local exactness.

For the circle example and $p=1$, write $\mathbf x=c(-1,-1)$:

The radial illustration is supported by the all-direction Cauchy bound above. The strict theorem uses $\rho_{\rm pen}>1/2$ as a sufficient bound. In this particular example, equality is also exact and strictly minimizing. At $\rho_{\rm pen}=1/2$, $\phi_1(c)+2=(c-1)^2$ for $c\ge1$, and $(1-c)(c+3)$ for $0\le c<1$. Both are positive off1; Cauchy equality selects the negative diagonal. A zero right derivative is first-order flatness, not a flat set of minima. For smaller weights, moving radially outward reduces the merit function.

Infeasible stationarity: what it does and does not show¶

A stationary point of every penalty weight need not be a least-infeasible point. At $x=0$, $h=x^2-1$ and $f=0$, the smooth local branch $\phi_1=\rho_{\rm pen}(1-x^2)$ has derivative zero for every positive weight, but is a strict local maximum of violation. Feasible points $x=\pm1$ exist. The quadratic penalty also has zero gradient at0. Thus stationarity cannot establish local violation minimality, global infeasibility, or an excessive number of constraints.

Even a genuine positive-residual local minimum of a restoration objective only describes that local search region; feasibility may exist elsewhere. Investigate derivative correctness, scaling, starts and the constraint structure. Full row rank guarantees that a nonzero residual can be reduced in the linear model by a right-inverse step, so an infeasible stationary violation point also warns that the regularity needed by such a model may be absent. This is diagnostic evidence, not a global proof.

One-sided directional derivatives¶

Use the forward derivative

For the $\ell_1$ residual, $C^1$ data imply

A kink may arise when an individual residual component is zero, even if the whole residual vector is nonzero. Composition can remove a kink, as in $|x^2|=x^2$.

For an exact linearized-feasibility step $\mathbf J\mathbf d=-\mathbf h$,

Indeed $\mathbf h(\mathbf x+\alpha\mathbf d)=(1-\alpha)\mathbf h+o(\alpha)$, and the reverse and ordinary triangle inequalities bound the norm error by $o(\alpha)$. With $C^2$ data, the remainder is $O(\alpha^2)$. At feasibility, $\mathbf J\mathbf d=\mathbf{0}$ and the residual contribution is zero. If the tangent objective slope is nonnegative, increasing the penalty weight cannot repair it: revise the direction/curvature model. A regularized equality row or truncated normal step may not satisfy $\mathbf J\mathbf d=-\mathbf h$; evaluate the actual derivative or actual model reduction instead.

Choosing the weight: full positive curvature versus reduced curvature¶

QP stationarity gives

When $\mathbf W\succ0$, Hölder and $\rho_{\rm pen}>\|\bar{\mathbf v}\|_q$ give strict merit descent except at the zero residual/zero step. This is Biegler p.117’s full positive-definite case. The updated QP multiplier is not generally interchangeable with the first-order multiplier estimate.

Only reduced positivity is needed for a unique equality QP, but then the full quadratic form can be negative. A concrete counterexample uses

The QP returns $\mathbf d=(-1,0)$ and $\bar v=100$, while the reduced curvature is1. Choosing $\rho_{\rm pen}=|\bar v|+1=101$ gives $D\phi=300-101=199>0$. It is therefore not a valid general reduced-space descent rule.

For a normal step $\mathbf n=\mathbf Y\mathbf p_Y$ with $\mathbf J\mathbf n=-\mathbf h$, tangent basis $\mathbf Z$, positive $\mathbf H_R=\mathbf Z^{\mathsf T}\mathbf W\mathbf Z$, reduced gradient $\mathbf g_R=\mathbf Z^{\mathsf T}\nabla f$ and coupling $\mathbf w=\mathbf Z^{\mathsf T}\mathbf W\mathbf n$, the QP tangent is $\mathbf q=-\mathbf H_R^{-1}(\mathbf g_R+\mathbf w)$. Then

For $\mathbf h\ne\mathbf{0}$, taking the weight above $\nabla f^{\mathsf T}(\mathbf n-\mathbf Z\mathbf H_R^{-1}\mathbf w)/\|\mathbf h\|_p$ plus a positive margin yields descent. This is the full coupling-aware Biegler 5.71 p.116 expression, with the missing gradient in5.70 restored by the errata. When coupling is zero, the book permits a bound using its first-order multiplier from Eq.5.21. Check which multiplier the implementation has computed. Directly checking the slope also avoids silently extending the full-PD rule.

A common monotone update $\rho_k=\max(\rho_{k-1},a_k+\epsilon)$ can remain bounded yet change at every iteration: take $a_k=1-1/(k+1)$. A bounded monotone sequence need not become constant. If the proof needs finitely many changes, enforce a minimum jump: when a required bound exceeds the current weight, set $\rho_k=\max(\rho_{k-1}+\delta,a_k+\epsilon)$ with fixed $\delta>0$. A bounded required bound then permits only finitely many changes. Flexible decrease rules require their own acceptance/convergence safeguards; the monotone proof does not automatically apply.

Filters: entries, rejected region, and sufficient progress¶

Let a stored list contain pairs $(\vartheta_j,f_j)$, where $\vartheta=\|\mathbf h\|_1$ is a violation value, not the course’s convex-combination weight. A trial passes this axis-margin filter if, for every stored pair,

The list and its rejected region are different sets. The rejected region is the union of the upper-right rectangles

A trial passes when its pair lies outside $\mathcal R$, not merely when it differs from the finitely many stored pairs. This strict-outside convention puts boundary points in the rejected set. Some algorithm statements use non-strict progress tests and a corresponding boundary convention; implement one convention consistently. Fletcher et al. (2002), Eq. 2.5, uses the stored violation in the objective margin; Eq. 2.6 is a distinct slanted-margin rule using trial violation. Do not combine their diagrams and tests inadvertently.

Take stored pairs $(.5,4),(1,3),(2,2),(3,1)$, $\gamma_\vartheta=.1$, $\gamma_f=.2$, and current pair $(1.7,1.7)$. TrialA$(.4,4.2)$ passes the filter but increases $f+\vartheta$; trialB$(2.2,1.05)$ passes both; trialC$(2.8,.5)$ decreases $f+\vartheta$ and passes the current-pair margin, but fails the last stored pair: $2.8>2.7$ and $.5>.4$. History prevents accepting it. Scalar merit and filter acceptance can differ in both directions.

Switching, restoration and a line-search outline¶

Historical acceptance and progress relative to the current point are both needed. Near feasibility, a pure violation-or-objective test can accept feasible nonoptimal stagnation. A switching test selects objective-type steps when $\nabla f^{\mathsf T}\mathbf d<0$ and

For those steps, require objective Armijo $f(\mathbf x+\alpha\mathbf d)\le f(\mathbf x)+\eta_f\alpha\nabla f^{\mathsf T}\mathbf d$ along with historical acceptance. Otherwise require sufficient improvement relative to the current pair. Non-objective-type accepted steps add the old point’s margin region to the filter. The implementation must state all constants, its maximum violation region, boundary conventions and restoration trigger; the basic dominance picture alone is not the algorithm. Biegler Algorithm 5.4 pp.120–121 gives an equality line-search version. Wächter–Biegler (2006), §2.3, adds a near-feasibility test and uses the barrier objective for its interior-point version; they are distinct formulations.

For a merit line search: evaluate derivatives, form an appropriate equality step, verify its derivative and update the weight, then backtrack from $\alpha=1$ until

Both sides use the same current weight. If near-solution rejection has the Maratos signature, first try the second-order correction below. If that corrected trial fails, discard the correction and continue backtracking. The SQP notebook supplies the actual active-set/QP/BFGS implementation rather than a second duplicate algorithm here.

A filter line search restores feasibility when backtracking cannot find an acceptable step. Restoration seeks a sufficiently feasible point acceptable to the filter, then returns to the optimization phase. It need not find a globally minimum violation point.

For interpreting actual Ipopt output, the printed objective is the original objective and printed inf_pr is the original-model violation; acceptance can use the barrier objective and internal scaled/slack residual. Both printed quantities can rise during a valid step. A local-infeasibility status describes a local violation minimum; another start can reach feasibility. A nearly feasible restoration failure can involve degeneracy, scaling or derivative errors and is not a diagnosis of one cause. See the official Ipopt output and status documentation. Interior-point details belong with the barrier-method material.

What a global-convergence argument proves¶

Here is the precise telescoping mechanism, not an unconditional algorithm guarantee. Suppose after some index the weight is fixed, accepted step lengths satisfy $\alpha_k\ge\underline\alpha>0$, the merit function is bounded below, and

where $\mathbf P=\mathbf I-\mathbf J^{\mathsf T}(\mathbf J\mathbf J^{\mathsf T})^{-1}\mathbf J$ is the orthogonal tangent projector. Armijo yields $\phi_k-\phi_{k+1}\ge\eta\underline\alpha cR_k$. Summing gives $\sum_kR_k<\infty$, hence $R_k\to0$. Compact iterates supply cluster points. Full row rank at each such point makes $\mathbf P$ continuous nearby, so every cluster point is feasible and has zero tangent gradient; the least-squares multiplier gives KKT stationarity.

A standard step/backtracking analysis must separately establish uniform derivative bounds, a uniformly well-conditioned right inverse, uniformly positive and bounded reduced curvature, bounded coupling/bases, a suitable penalty rule and a uniform step-length bound. Pointwise positivity and pointwise rank alone are not uniform constants. Biegler Assumptions I and Theorem 5.10 pp.118–119 motivate this analysis, but the displayed residual/telescoping argument does not by itself prove convergence of the entire sequence to one point. It also does not prove second-order optimality or a global minimum. For example, points $(\sin\log(k+1),0)$ with $f=0,h=x_2$ all have zero residual but do not converge; this illustrates the logical gap and is not asserted to be the trajectory of a particular algorithm.

Filter conclusions depend on the exact algorithm and restoration assumptions. Biegler Theorems 5.11/5.13 state feasibility convergence and a liminf stationarity conclusion, assuming no unsuccessful restoration termination. A liminf conclusion is weaker than stationarity of every cluster point. Fletcher et al. (2002), Theorem 7, gives alternatives involving finite KKT termination, restoration failure, or a feasible cluster point that is KKT or fails MFCQ. Do not promote any of these into an unqualified whole-sequence or global-optimum promise.

Trust-region feasibility and minimum-distance normal steps¶

The equality QP with $\|\mathbf d\|_2\le\Delta$ can be infeasible even when the original constraints are feasible. With full-row-rank $\mathbf J$, the minimum-norm normal step is

Every solution of $\mathbf J\mathbf d=-\mathbf h$ is $\mathbf n_{\min}+\mathbf Z\mathbf q$, with an orthogonal null basis. Orthogonality gives $\|\mathbf d\|_2^2=\|\mathbf n_{\min}\|_2^2+\|\mathbf q\|_2^2$. Thus the linearized equality intersects the ball exactly when $\|\mathbf n_{\min}\|_2\le\Delta$. An arbitrary right-inverse coordinate step may be longer and cannot establish infeasibility. For $\mathbf J=[1,1],h=1$, the minimum step $(-.5,-.5)$ has length.7071; the coordinate step$(-1,0)$ has length1. A radius.8 is feasible despite excluding the coordinate step.

Composite steps, prediction and acceptance¶

Byrd–Omojokun first solves a normal problem

Under full row rank this is strictly convex in normal coordinates. It reduces linearized violation but need not reach zero: the smaller ball may prevent that. An inexact normal solve should satisfy a specified fraction-of-Cauchy decrease, rather than be accepted solely because it is inside the ball.

Then solve the tangent problem with $\mathbf d=\mathbf n+\mathbf Z\mathbf q$:

The coupling term is retained. Exact positive reduced curvature is not mandatory for a globally solved bounded trust subproblem; negative curvature can be handled by the trust-region solver. Positive-definite approximations can be useful globalization choices, but they do not preserve an indefinite full Hessian’s normal curvature. They are perfectly legitimate when the true full Hessian is itself positive definite.

For the $\ell_2$ merit model,

Let $v_N=\|\mathbf h\|_2-\|\mathbf h+\mathbf J\mathbf n\|_2$ and $q_T=-(\mathbf Z^{\mathsf T}\nabla f+\mathbf Z^{\mathsf T}\mathbf W\mathbf n)^{\mathsf T}\mathbf q-\frac12\mathbf q^{\mathsf T}\mathbf H_R\mathbf q$. Then

If $v_N>0$, increase the weight as necessary so $\mathrm{pred}>0$, e.g. to make the non-tangential contribution at least $\zeta\rho_{\rm pen}v_N$ for chosen$\zeta\in(0,1)$:

The full book 5.98 bound includes $-q_T$ as well when targeting the total prediction; state which inequality is enforced. If $v_N=0$, do not divide by it: tangent decrease or a restoration/stationarity branch must handle the case. If approximated full normal curvature is omitted from the model, consistently omit it from the bound and prediction; do not mix exact and approximate formulas.

For positive prediction, accept when $\mathrm{ared}/\mathrm{pred}$ exceeds a small threshold; shrink on poor agreement and enlarge on strong agreement when the step reaches the boundary. A high ratio does not justify unbounded radius growth independently of the chosen algorithm safeguards. Stop only when both primal and stationarity residuals satisfy their tolerances; a small step alone is not convergence. Biegler Algorithm 5.5 pp.125–126 gives the detailed scheme; its convergence theorem needs its stated regularity and step-quality assumptions.

An explicit truncated example uses $h=x_1+2$, $f=-x_1-x_2+\frac12x_1^2+x_2^2$, start$(0,0)$, $\Delta=1,\xi=.8$. The full linearized equality is distance2 away. The normal step is$(-.8,0)$, leaving violation1.2. The tangent optimum is$(0,.5)$, so $\mathbf d=(-.8,.5)$ has length.9434. At weight2, current merit is4 and trial merit is3.27; prediction and actual reduction are both.73 and the ratio is1. The accepted composite step makes progress without making the linearized constraints exactly feasible.

A filter trust-region method instead uses restoration to find a filter-acceptable iterate whose linearized constraints intersect the current ball, then solves the equality trust QP and applies historical/current-pair and objective-model tests. This is distinct from always computing a truncated composite step. Biegler Algorithm 5.6 pp.126–127 gives one formulation; its model-reduction notation should be evaluated at step0 and the trial step, with a consistent positive predicted reduction.

Constrained quasi-Newton information¶

The constrained secant pair uses a single fixed updated multiplier for both gradients:

Changing the multiplier between the two terms adds constraint-gradient/multiplier variation that is not the intended fixed-multiplier curvature measurement. Damped BFGS enforces its curvature test before updating a positive-definite approximation. The complete unconstrained update derivation belongs to Quasi-Newton Methods, and the actual constrained update is in SQP. A full positive-definite approximation imposes more than positive reduced curvature; reduced-space updates can preserve the weaker local requirement. This is a modeling/linear-algebra choice, not a theorem that full BFGS always fails.

The Maratos effect and a second-order correction¶

Powell’s example is $h=x_1^2+x_2^2-1$, $f=2h-x_1$, $\mathbf x^*=(1,0)$, $v^*=-3/2$, and $\mathbf W(\mathbf x^*,v^*)=\mathbf I$. At a feasible point $\mathbf x^k=(\cos t,\sin t)$, use that identity Hessian in the equality QP. The solve returns

Put $c=\cos t,s=\sin t$. Then $\mathbf x^k+\mathbf d-\mathbf x^*=(1-c)(c,s)^{\mathsf T}$, so the full trial’s error is exactly half the old error squared. Nevertheless, $h(\mathbf x^k+\mathbf d)=s^2$ and $f(\mathbf x^k+\mathbf d)-f(\mathbf x^k)=s^2$. For $s\ne0$, every positive-weight $\ell_1$ merit increases by $(1+\rho_{\rm pen})s^2$, and the current-pair filter margin also rejects it. This occurs arbitrarily near the minimum. Do not say it occurs at every nonzero angle: at $t=\pi$ or multiples of$2\pi$, the sine-based strict inequalities fail.

Evaluate the constraint at the full trial and compute a minimum-normal increment

For the circle, $\mathbf r=-\frac12s^2(c,s)^{\mathsf T}$, the corrected error is $\frac12(1-c)^2$, and the corrected residual is exactly $s^4/4$. Thus the error is the old error to the fourth power divided by8. Biegler’s norm equality after 5.111 p.129 has an incorrect coefficient; this is the corrected exact expression. For a fixed finite weight, Armijo constant $0<\eta<1/2$, and sufficiently small nonzero $t$, the corrected trial satisfies sufficient decrease and restores full steps. In fact $D\phi_1=-s^2$ and $\phi_1(\mathbf x_{\rm SOC})-\phi_1(\mathbf x^k)=-s^2(1-c/2)+(2+\rho_{\rm pen})s^4/4$; dividing by $-s^2$ gives a limiting decrease ratio of $1/2$. Mere merit decrease at an arbitrary angle is not enough to assert Armijo acceptance: at$t=1$, weight2 and Armijo constant.1, this particular correction decreases merit but fails that Armijo test.

This shared illustration and archive are generated by the actual SQP notebook’s model and KKT solver, at$t=.4$, weight2 and Armijo constant.1. Its algorithm experiments also compare trajectories with and without the correction.

A second variant reoptimizes a replacement step:

Test $\mathbf x^k+\hat{\mathbf d}$. Its increment is $\hat{\mathbf d}-\mathbf d$, never the replacement itself. For linear constraints the second QP equals the first and returns$\hat{\mathbf d}=\mathbf d$, demonstrating why adding both would double the step. Taylor expansion gives $\bar{\mathbf h}=\mathbf h_k+\frac12\mathbf h''_k[\mathbf d,\mathbf d]+O(\|\mathbf d\|^3)$ under the required extra smoothness; $C^2$ alone gives an $o(\|\mathbf d\|^2)$ remainder. One extra constraint evaluation supplies the quadratic residual information without evaluating its Hessians.

Replacement-QP and minimum-normal correction are different algorithms in general. Their increments satisfy the same linear correction constraint, but the QP also reoptimizes the tangent component. For $\mathbf J=[1,0]$, $\mathbf W=\left[\begin{smallmatrix}2&1\\1&2\end{smallmatrix}\right]$, $\nabla f=(-1,-2)$ and $h=x_1+\frac12x_2^2$ at the origin, the original step is$(0,1)$. The minimum-normal correction yields full step$(-.5,1)$, while the replacement QP yields$(-.5,1.25)$. Their tangent components differ because of Hessian coupling. They coincide in the identity-Hessian circle example. Either convention is valid when consistently defined and properly safeguarded; equality in one toy is not a universal equivalence theorem.

Optional supplement: nonmonotone watchdog cycles¶

A second-order correction changes the trial point to compensate for constraint curvature. A watchdog instead permits a limited period of merit increase while taking the algorithm’s ordinary directions. It saves an anchor and returns to it if subsequent steps do not earn sufficient progress. Thus it changes acceptance history rather than adding a normal correction. This supplementary topic is outside the fourteen-page classroom sequence.

For the one-relaxed-step variant in Nocedal–Wright Algorithm 15.3, p.445, hold the penalty weight fixed throughout a cycle and choose $0<\eta<1/2$. Let $\mathbf x_0$ be the saved anchor, $\mathbf d_0$ its descent direction, $D_0=D\phi(\mathbf x_0;\mathbf d_0)<0$ and $\phi_i=\phi(\mathbf x_i)$.

1. Form the full trial $\mathbf x_1=\mathbf x_0+\mathbf d_0$. If $\phi_1\le\phi_0+\eta D_0$, finish the cycle there. Otherwise keep this point temporarily as a relaxed step, retaining the saved anchor and direction.

2. Compute an ordinary descent direction $\mathbf d_1$ at the relaxed point and backtrack to $\mathbf x_2=\mathbf x_1+\alpha_1\mathbf d_1$, requiring $\phi_2\le\phi_1+\eta\alpha_1D\phi(\mathbf x_1;\mathbf d_1)$.

3. Resolve the cycle with the following branches:

   • If $\phi_1\le\phi_0$ or $\phi_2\le\phi_0+\eta D_0$, keep $\mathbf x_2$ and finish the cycle.

   • If neither holds and $\phi_2>\phi_0$, roll back to the saved anchor and backtrack along the saved direction. Set $\mathbf x_3=\mathbf x_0+\alpha_0\mathbf d_0$ with $\phi_3\le\phi_0+\eta\alpha_0D_0$, then finish the cycle.

   • Otherwise $\phi_2\le\phi_0$, but the earlier tests did not establish the required recovery. Take one further ordinary descent step from $\mathbf x_2$, with its own Armijo line search, and finish the cycle at $\mathbf x_3$.

The saved anchor, primal/dual state, direction and weight must remain recoverable until the cycle succeeds; accepted trial state should not overwrite the only rollback copy. In this variant at most three new indices separate the distinguished cycle endpoints. More permissive multi-relaxed-step schemes need their own limits and recovery tests; they are not obtained by simply suppressing Armijo indefinitely.

For an acceptance trace with $\phi_0=0,D_0=-1,\eta=.1$, a relaxed full trial $\phi_1=.2$ fails the anchor bound -.1. If the next direction has derivative-1 and step length.5, its own Armijo bound is.15. A second merit-.12 passes that local bound and recovers the anchor’s required decrease, so the two-step cycle succeeds. A different trace with $\phi_1=.4$, second-direction derivative-1, step length1 and $\phi_2=.25$ satisfies its local bound.3 yet remains above the anchor: it must roll back. Local decrease from the relaxed point is not the same as recovery relative to the saved anchor.

A convergence proof analyzes the distinguished cycle endpoints and the underlying direction/line-search assumptions. It does not demand that every intermediate merit value decrease. Local full-step and rate results also require the usual regularity and curvature hypotheses; a finite relaxation window alone proves neither convergence nor a global minimum. Compared with correction, watchdog cycles can avoid the extra correction-specific constraint evaluation, but rollback and extra ordinary steps can still cost evaluations. See Nocedal–Wright §§15.5–15.6, pp.440–446, especially Algorithm15.3; the existing SQP notebook implements second-order correction, not this optional watchdog variant.

Inequality extensions and implementation scope¶

For the convention $g_i\le0$, an $\ell_1$ violation measure is $\sum_j|h_j|+\sum_i\max(g_i,0)$. Equality multipliers are unrestricted and inequality multipliers nonnegative; exactness thresholds include their corresponding magnitudes. Directional derivatives for a zero inequality residual use$\max(\nabla g_i^{\mathsf T}\mathbf d,0)$ rather than the absolute value used for an equality. Active inequalities, critical-cone curvature, QP feasibility and elastic relaxation need their own assumptions. The equality formulas do not transfer unchanged merely by renaming the residual. Local Optimality, Constraint Qualifications, Second Order Optimality Conditions and the SQP implementation provide the canonical details.

Additional references¶

• Fletcher, Leyffer and Toint (2002), “On the global convergence of a filter-SQP algorithm,” SIAM Journal on Optimization13(1), pp.44–59. Equations 2.5/2.6 distinguish margin choices; Theorem 7 states the convergence alternatives. DOI.

• Wächter and Biegler (2006), “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” Mathematical Programming106, pp.25–57. Section2.3 specifies the barrier filter, switching and restoration. DOI.