Constraint Qualifications

For $C^1$ data near a feasible point, constraint qualifications connect the actual feasible set to its first-order model. We use row-oriented Jacobians and the canonical form $g_i(\mathbf{x})\le0$, $h_j(\mathbf{x})=0$. The KKT reference owns active/strong/weak terminology and sensitivity; Local Optimality Conditions owns convex KKT sufficiency.

The definitions, full proof arguments, and diagnostics below supplement Lecture 20. Biegler (2010), Sections 4.3.1–4.3.2, pp. 74–79, supplies the core sequence; Nocedal and Wright (2006), Sections 12.2, 12.4 and 12.6, supplies the tangent-cone formulation and proof details.

On open $D\subset\mathbb R^n$, use $f:D\to\mathbb R$, $\mathbf g:D\to\mathbb R^r$, $\mathbf h:D\to\mathbb R^m$, and $S=\{\mathbf x\in D:\mathbf g(\mathbf x)\le\mathbf0,\mathbf h(\mathbf x)=\mathbf0\}$. Inequalities are componentwise.

Feasible sequences, unit directions, and the tangent cone¶

A feasible sequence approaching $\bar{\mathbf{x}}$ has $\mathbf{x}^k\ne\bar{\mathbf{x}}$, $\mathbf{x}^k\to\bar{\mathbf{x}}$, and feasible terms for all sufficiently large $k$. If

then $\mathbf{d}$ is its unit limiting direction. A feasible sequence need not have a direction limit: it can alternate between two approach directions. The definition applies to sequences or subsequences for which the limit exists.

The tangent cone uses arbitrary positive scales:

It includes $\mathbf0$. Every nonzero tangent vector gives a unit limiting direction after normalization, and positive multiples of a unit limiting direction lie in $T_S$. Thus unit limiting directions are $T_S\cap\{\|\mathbf{d}\|=1\}$, rather than the entire cone. This distinction resolves the normalization shorthand in Biegler’s Lemma 4.13. See Nocedal and Wright, Definition 12.2, p. 316, and Lemma 12.2, pp. 323–325.

Here $S=\{x_2\ge0.2x_1^2\}$, $\mathbf{x}(t)=(t,0.6t^2)$, $t\downarrow0$. Its normalized chord is $(1,0.6t)^T/\sqrt{1+0.36t^2}\to(1,0)^T$. The direction points from the limit toward nearby feasible points. A ball travelling toward the limit moves in the opposite direction; the ball is an analogy, not an assumption about an algorithm’s iterates.

First-order necessity along the actual feasible set¶

If $f$ is differentiable and $\mathbf{x}^*$ is a local minimum on $S$, then

Proof for a unit limiting direction. Put $r_k=\|\mathbf{x}^k-\mathbf{x}^*\|>0$ and $\mathbf{d}_k=(\mathbf{x}^k-\mathbf{x}^*)/r_k\to\mathbf{d}$. Differentiability gives

Local minimality makes the left side nonnegative eventually. A negative limit would force arbitrarily nearby feasible points with a smaller objective, a contradiction. Multiplication by a nonnegative scalar extends the result to every tangent vector. Biegler, Theorem 4.8 and proof, pp. 74–75; Nocedal and Wright, Theorem 12.3, pp. 325–326.

This is necessary, not sufficient. For $\min x_2$ subject to $x_2\ge-x_1^2$, the origin has $T_S=\{d_2\ge0\}$ and $\nabla f^T\mathbf{d}=d_2\ge0$. Yet $(t,-t^2)$ is feasible and improves the objective for every nonzero $t$. The loss appears at second order (Nocedal and Wright, Example (12.44), p. 326).

Linearization and constraint indices¶

Use separate index sets: $\mathcal E=\{1,\ldots,m\}$ for equalities and $\mathcal A_I(\bar{\mathbf{x}})=\{i:g_i(\bar{\mathbf{x}})=0\}$ for active inequalities. The combined row labels are tagged pairs $(h,j)$ and $(g,i)$; equality 1 and inequality 1 are distinct rows. Stack

The linearized cone is

Containment proof. For $\mathbf{w}\in T_S$, write $\mathbf{z}^k=\bar{\mathbf{x}}+t_k\mathbf{w}+o(t_k)$. Expand an equality about the feasible point and divide by $t_k>0$: $0=h_j(\mathbf{z}^k)/t_k=\nabla h_j^T\mathbf{w}+o(1)$. For an active inequality, $0\ge g_i(\mathbf{z}^k)/t_k=\nabla g_i^T\mathbf{w}+o(1)$. Taking limits proves $T_S\subseteq L_S$. Inactive inequalities stay negative nearby by continuity and impose no first-order restriction. The remainder is $o(t_k)$, not $o(t_k^2)$.

Linearized feasibility alone does not assert that $\bar{\mathbf{x}}+t\mathbf{d}$ is feasible for a nonlinear constraint. A curved correction can be necessary.

Affine constraints: exact first-order geometry¶

For $\mathbf B\mathbf{x}\le\mathbf b$, $\mathbf C\mathbf{x}=\mathbf c$, take $\mathbf d$ with $\mathbf C\mathbf d=0$ and $\mathbf B_i\mathbf d\le0$ for every active row. The straight path $\bar{\mathbf{x}}+t\mathbf d$ satisfies the equalities and active inequalities exactly. Each inactive row has positive slack $b_i-\mathbf B_i\bar{\mathbf{x}}$; choose $t>0$ small enough to preserve all finitely many slacks. Hence $L_S=T_S$, even if the constraint rows are dependent.

At a local minimum, no $\mathbf d$ solves $\nabla f^T\mathbf d<0$, $\mathbf C\mathbf d=0$, $\mathbf B_{\mathcal A_I}\mathbf d\le0$. The theorem of alternatives gives

Set inactive multipliers to zero to obtain the complete KKT conditions. This is Biegler’s Theorem 4.11, pp. 75–76; Nocedal and Wright’s Lemma 12.7, pp. 338–339. Independence is not required for this affine-constraint argument. With a convex objective the existing convex KKT certificate proves global sufficiency; it does not require LICQ.

A cusp where KKT fails¶

Both constraints imply $-x_1^3\le x_2\le x_1^3$, so $x_1\ge0$; at $x_1=0$ they force $x_2=0$. The origin is the unique global solution. This is Biegler’s (4.44), Figure 4.8, p. 77.

Explain the geometry. The overlap of both hatches is feasible. Why is the origin optimal even though the objective gradient is nonzero? The constraints restrict $x_1$ to be nonnegative and permit only $x_2=0$ when $x_1=0$.

Full KKT case analysis¶

With $L=x_1+u_1(x_2-x_1^3)+u_2(-x_1^3-x_2)$, stationarity is

The remaining conditions are $g_1,g_2\le0$, $u_1,u_2\ge0$, $u_1g_1=u_2g_2=0$. At the origin the first stationarity component is 1 for every finite multiplier vector.

1. Neither multiplier positive: $u_1=u_2=0$ gives gradient $(1,0)^T$, so stationarity fails. Zero multipliers do not remove the constraints or make this feasible problem unbounded.

2. Only $u_1>0$: the second stationarity row forces $u_1=0$, a contradiction.

3. Only $u_2>0$: the second row forces $u_2=0$, again a contradiction.

4. Both positive: the second row gives $u_1=u_2=u$; the first gives $x_1^2=1/(6u)$. Complementarity requires both constraints active, which forces $x_1=x_2=0$, contradicting the first row. The algebraic relation has both square-root signs; feasibility selects $x_1\ge0$, but no finite feasible KKT point results.

An approximate stationarity path illustrates the difficulty: for $t>0$, choose $(x_1,x_2)=(t,0)$, $u_1=u_2=1/(6t^2)$. Stationarity holds and the point is feasible, but both inequalities are slack and $u_i g_i=-t/6\ne0$. As $t\downarrow0$, complementarity residuals vanish while multipliers diverge. This is not a family of exact KKT points. The original scan’s $3u$ denominator is replaced by the verified $6u$ relation.

Actual and linearized directions at the cusp¶

At the origin the active row Jacobian is

Its inequalities impose $d_2\le0$ and $-d_2\le0$, hence $L_S=\{(d_1,0):d_1\in\mathbb R\}$. In contrast, $|x_2|\le x_1^3$ and $x_1\ge0$ imply every normalized nonzero feasible chord tends to $(1,0)^T$: $|x_2|/x_1\le x_1^2\to0$. Therefore $T_S=\{(d_1,0):d_1\ge0\}$.

Biegler calls $(1,0)^T$ $\mathbf d_1$ and $(-1,0)^T$ $\mathbf d_2$. The left-pointing $\mathbf d_2$ has $\nabla f^T\mathbf d_2=-1$ but cannot be realized by a feasible sequence. Two handwritten sketches reverse these names; the algebra and geometry fix the labels. A constraint qualification eliminates this extra first-order direction.

LICQ and feasible curved corrections¶

LICQ holds at a feasible point when all equality gradients and all active inequality gradients are jointly independent: $\operatorname{rank}\mathbf J_{\mathcal A}=m+|\mathcal A_I|$. It is a property of the constraint representation at a point, not a requirement that the point already be optimal. Equalities, weakly active inequalities, and active bounds all count. If there are more active rows than variables, LICQ cannot hold. Biegler, Definition 4.12 at the foot of p. 77; Nocedal and Wright, Definition 12.4, p. 320.

The cusp has two antiparallel nonzero rows, rank 1 rather than 2, so LICQ fails. Nonzero individual gradients are not enough.

Reverse inclusion under LICQ. Let $c_{\mathcal A}(\mathbf z)$ stack all equalities and active inequalities in the tagged row order, and let $Z\in\mathbb R^{n\times(n-m-|\mathcal A_I|)}$ have basis columns for $\ker \mathbf J_{\mathcal A}$. For any $\mathbf d\in L_S$, consider

At $(\bar{\mathbf x},0)$ its derivative with respect to $\mathbf z$ is $[\mathbf J_{\mathcal A};\mathbf Z^T]$, a square nonsingular matrix: a vector in its null space belongs to $\ker \mathbf J_{\mathcal A}=\operatorname{range}\mathbf Z$ and is orthogonal to that space, hence is zero. The C1 implicit function theorem requires a C1 residual map, a zero residual at the base point and an invertible derivative with respect to the unknowns; these follow from the stated neighborhood data, feasibility and the displayed null-space argument. It yields a $C^1$ path $\mathbf z(t)$, and differentiation at zero gives $\mathbf z'(0)=\mathbf d$. Thus $\mathbf z(t)=\bar{\mathbf x}+t\mathbf d+o(t)$.

The construction gives exactly $h_j(\mathbf z(t))=t\nabla h_j^T\mathbf d=0$ and $g_i(\mathbf z(t))=t\nabla g_i^T\mathbf d\le0$ for active inequalities; continuity preserves the inactive inequalities for small positive $t$. These exact identities come from solving $R=0$, not merely truncating a Taylor expansion. Consequently $L_S=T_S$. This adapts Nocedal and Wright, Lemma 12.2, pp. 323–325, to $g\le0$ and row Jacobians; Biegler, Lemma 4.13, p. 78, requires the errata’s $h_j$ subscript.

For the circle equality $h=(x_1-1)^2+x_2^2-1=0$ at $(0,0)$, $\mathbf d=(0,1)^T$ is tangent. The straight step $(0,t)$ has $h=t^2>0$. The corrected path $(1-\sqrt{1-t^2},t)$ is feasible and differs from the straight step by $(t^2/2+O(t^4),0)$. LICQ promises a nearby feasible path, not feasibility of the straight step.

From no feasible descent to KKT¶

At a $C^1$ local minimum with LICQ, $T_S=L_S$, so no direction satisfies

The finite-dimensional linear alternative says that absence of a direction satisfying that system is equivalent to existence of a nonnegative active inequality multiplier and unrestricted equality multiplier balancing the objective gradient. Thus it gives $\mathbf u_{\mathcal A_I}\ge0$, unrestricted $\mathbf v$, with $\nabla f+\mathbf J_{g,\mathcal A_I}^T\mathbf u_{\mathcal A_I}+\mathbf J_h^T\mathbf v=0$. Inactive multipliers are zero, yielding dual feasibility and complementarity. Feasibility is already a hypothesis. This proves KKT necessity (Biegler, Theorem 4.14, p. 78; Nocedal and Wright, Theorem 12.1, p. 321, and proof pp. 323–329).

Conversely, a KKT vector implies $\nabla f^T\mathbf d=-\mathbf u_{\mathcal A_I}^TJ_{g,\mathcal A_I}\mathbf d\ge0$ for every $\mathbf d\in L_S$. This algebra needs no CQ. It is still a first-order necessary test, not general sufficiency. The separate convex certificate is at the Local Optimality reference.

Multiplier uniqueness and its limits¶

At a fixed KKT point, stack active multipliers in the same order as $\mathbf J_{\mathcal A}$, with equality components unrestricted and inequality components nonnegative. If $\boldsymbol\lambda^a$ and $\boldsymbol\lambda^b$ both satisfy stationarity, then

Full row rank makes $\mathbf J_{\mathcal A}^T$ injective, so the difference is zero. Equivalently, multiply by $\mathbf J_{\mathcal A}$: the row Gram matrix $\mathbf J_{\mathcal A}\mathbf J_{\mathcal A}^T$ is positive definite. This is the row-oriented version of Biegler’s Theorem 4.15 proof, p. 79; his column-oriented Gram matrix has the factors in the opposite order.

Failure of LICQ does not force multiple KKT multipliers. For $\min0$ subject to $-x\le0$, $-2x\le0$, at $x=0$ stationarity and nonnegativity require $u_1+2u_2=0$, hence $(u_1,u_2)=(0,0)$ uniquely despite dependent rows. Without LICQ the unconstrained linear stationarity system has a null direction, but the multiplier sign restrictions may remove all nonzero displacements.

For redundant equalities the situation differs: if $\mathbf J_h^T\boldsymbol\nu=0$, equality multipliers can move freely as $\mathbf v+t\boldsymbol\nu$ without sign restrictions. The active equality KKT matrix has null vector $(\mathbf0,\boldsymbol\nu)^T$, whatever the Hessian.

Uniqueness alone does not establish a differentiable solution branch or a shadow price. The sensitivity reference states the branch, sign, and second-order conditions and gives examples of nonsmooth values.

MFCQ, geometry, and bounded multipliers¶

MFCQ holds when $\mathbf J_h$ has full row rank and $\exists\mathbf d\in\mathbb R^n:\ \mathbf J_h\mathbf d=\mathbf0$ and $\nabla g_i(\bar{\mathbf x})^T\mathbf d<0$ for every $i\in\mathcal A_I$. With no active inequalities the strict condition is vacuous; equality independence still matters. This tests a feasible point, not just a solution. Biegler, Definition 4.16, p. 79; Nocedal and Wright, Definition 12.6, p. 339.

LICQ implies MFCQ: full row rank allows solving $\mathbf J_{\mathcal A}\mathbf d=(\mathbf0,-\mathbf1)^T$. The equality part is zero and every active inequality decreases strictly.

Strictly weaker: take $h=x_2=0$, $g_1=-x_1\le0$, $g_2=-2x_1\le0$ at the origin. The three active rows have rank 2, so LICQ fails; $\mathbf d=(1,0)^T$ satisfies MFCQ. For $f=x_1$, stationarity gives $v=0$, $u_1+2u_2=1$, $u_1,u_2\ge0$. The multiplier set is the closed line segment from $(1,0)$ to $(0,1/2)$: bounded, nonunique.

At the cusp, MFCQ would require $d_2<0$ and $-d_2<0$, which is impossible. No finite KKT multiplier exists there.

Why MFCQ bounds a nonempty KKT multiplier set. If a sequence of KKT multipliers were unbounded, omit its identically zero inactive components, normalize it by its diverging norm, and take a convergent subsequence on the compact unit sphere in $\mathbb R^{m+|\mathcal A_I|}$. Dividing stationarity by that norm gives

Dot with the MFCQ direction. Each active inequality derivative is strictly negative, so a zero sum forces $\widehat{\mathbf u}=\mathbf0$. Equality independence then forces $\widehat{\mathbf v}=\mathbf0$, contradicting unit norm. The fixed-point KKT multiplier set is closed, so it is compact if nonempty. MFCQ also ensures KKT existence at a $C^1$ local minimum.

Conversely, failure of MFCQ yields a nonzero homogeneous multiplier $(\widehat{\mathbf u}\ge\mathbf0,\widehat{\mathbf v})$ with $\mathbf J_{g,\mathcal A_I}^T\widehat{\mathbf u}+\mathbf J_h^T\widehat{\mathbf v}=\mathbf0$: equality dependence gives one immediately; otherwise the strict-direction theorem of alternatives gives one. Add its nonnegative ray to any existing KKT vector to obtain an unbounded multiplier set. Thus at a fixed KKT point with a nonempty multiplier set, MFCQ is equivalent to boundedness. The nonempty condition matters: $\min x$ subject to $x^2\le0$ has sole feasible point 0, fails MFCQ, and has no KKT vector; the empty set is bounded in the set-theoretic sense. See Nocedal and Wright, p. 339, with this scope made explicit.

What each qualification guarantees¶

For $C^1$ data at a local minimum:

These are sufficient hypotheses; their failure is not proof that KKT fails. Example: $\min x^2$ subject to $x^2\le0$ has a KKT vector at zero although LICQ and MFCQ fail. Its multiplier set is $[0,\infty)$.

MFCQ gives $T_S=L_S$: for any $\mathbf d\in L_S$, add $\delta\mathbf w$ with a strict MFCQ direction $\mathbf w$. All active inequalities then decrease strictly. Full row rank of $\mathbf J_h$ gives, by the implicit function theorem, an equality-feasible path $\bar{\mathbf x}+t(\mathbf d+\delta\mathbf w)+o(t)$; strict inequality derivatives make it feasible for small $t>0$. Thus $\mathbf d+\delta\mathbf w\in T_S$. Let $\delta\downarrow0$ and use closedness of the tangent cone to get $\mathbf d\in T_S$.

Peterson (1973), SIAM Review 15, pp. 639–654, DOI, Table 1 pp. 643–644 and Figure 4 p. 645, maps a broader CQ hierarchy. Table 1 puts MFCQ on p. 643 and LICQ on the continuation p. 644. His principal formulation uses inequalities and a general set $X$; do not encode equalities as two opposite inequalities when translating MFCQ. His arrows point toward weaker conditions. The equality-aware definitions here follow the textbooks.

Example revisited: solve with Pyomo¶

The following original experiment intentionally approaches the degenerate cusp with Ipopt. Keep its iterates and reported termination distinct from an exact KKT certificate: there is no finite multiplier vector at the true solution. Solver versions and tolerances can change the numerical output.

Discussion. Inspect the iteration count, final primal residuals, point, and imported duals. Why is the point only approximately zero? Compare the growth of multiplier magnitudes with $1/(6t^2)$, rather than treating the solver’s output as a finite limiting KKT vector.

The raw Pyomo dual suffix uses the solver interface’s constraint orientation. It is not automatically the nonnegative $u_i$ of the canonical $g_i\le0$ form. For this pair of upper/lower constraints, check the mapping against stationarity before interpreting the signs; the worked suffix checks illustrate this procedure. A large negative imported value does not by itself violate canonical dual feasibility.

For diagnosing larger models, continue to NLP Diagnostics with Degeneracy Hunter: full row-dependence theory, QR/MILP workflow, scaling and case-study context accompany the executable diagnostic example.

Check the original model, rather than only the termination banner¶

The current default run reports an optimal termination at a slightly negative $x_1$. Exact cusp feasibility requires $x_1\ge0$. Re-evaluate the original inequalities and multiplier products below. Both imported suffixes convert as $u_i=-\texttt{m.dual[m.gi]}$ for this model; the stationarity residual checks that mapping.

Ipopt’s options reference describes bound relaxation and its limits. In an inequality formulation with slack variables, the internal feasibility and complementarity report can differ from evaluation of the original inequality. The numerical output here establishes that difference directly: small primal violation multiplied by a very large multiplier need not produce a small original-model complementarity residual. Keep the original experiment unchanged; an optimal solver status is not a proof of exact feasibility or KKT satisfaction at the cusp.