A constraint the count stops seeing

Gould’s theorem, which a minimum the Hessian cannot see turned into a second-order test, has a hypothesis that every measurement of the loop has so far kept: the constraint A has full row rank. Under it the saddle-point matrix K has the inertia of the reduced Hessian plus m eigenvalues of each sign, one pair for each constraint, and the count read off a factorisation of K says whether a point is a constrained minimum.

Real constraints lose that hypothesis gradually. Two linearised constraints of a nonlinear problem become nearly parallel as the iterates approach a point where they are tangent; a network’s conservation laws acquire a nearly redundant row when a component’s conductance goes to zero; an equality constraint and a bound that is active at the same place point the same way. In each case A keeps full rank in exact arithmetic and one of its singular values heads towards zero.

The shift that stops at the first right count measured the loop that raises a shift on H until the count is right, on constraints whose conditioning was spread evenly across their singular values, and closed on the case the published loop treats differently. This essay makes one singular value small and leaves the rest alone, so the question has a single knob: at what σ does the count stop seeing the constraint, what does it see instead, and what does each repair do about it.

The pair that belongs to the weak constraint #

Write A in its singular value decomposition, UΣVᵀ, and put the unknowns in the basis of V. Each constraint direction $v_i$ now appears in K beside one multiplier, coupled by $\sigma_i$, and the last of them carries a 2 × 2 block that looks like

where h is the curvature of H along the constraint’s weak direction $v_4$. The product of the two eigenvalues is −$\sigma^2$, so they have opposite signs at every σ > 0: the pair contributes one positive and one negative eigenvalue however weak the constraint is. That is the theorem, restated for one constraint. The sizes are what matter numerically. One eigenvalue is about h and the other is about −$\sigma^2$/h, and the second is the one that carries the constraint’s contribution to the count.

On the construction used here — ten unknowns, four constraints with singular values 1, 0.9, 0.8 and σ, a reduced Hessian with eigenvalues from 0.5 to 5, and H written directly in V’s basis — the smallest eigenvalue of K at σ = 10⁻⁴ is $\sigma^2$/|h| to within a part in a thousand at h = −1, −100 and −0.01. It is 10⁻⁸ at h = −1. At σ = 10⁻⁸ it would be 10⁻¹⁶.

So the count is reading a sign whose magnitude falls like the square of the constraint’s weakness. A matrix whose entries are of order one can resolve an eigenvalue down to about u, and $\sigma^2$/|h| reaches u at $\sigma \approx \sqrt{u|h|}$, which is 10⁻⁸ at h = −1.

Where it stops, measured #

The first figure makes that estimate a measurement. For each h and each of eight draws, σ is swept down from 1 in quarter decades, and each route’s count is compared with the problem’s own inertia, (10, 4, 0) — every draw is a genuine constrained minimum. The σ at which a route is first wrong is the largest σ at which it can no longer be trusted.

The Bunch–Kaufman LDLᵀ count is first wrong, in the median over draws, at σ = 1.8·10⁻¹¹ for h = −10⁻⁴, 1.8·10⁻¹⁰ for h = −0.01, 1.4·10⁻⁹ for h = −1 and 1.8·10⁻⁸ for h = −100. The fitted slope against |h| is 0.49 — ten times higher for every hundred times the curvature, the square root the pair predicts. The constant is smaller than the rough estimate: $\sigma^2$/|h| at those values is about 2·10⁻¹⁸ to 3·10⁻¹⁸, a few hundredths of u, so the elimination keeps the sign of the small eigenvalue a little past where a naive reading of the matrix’s rounding says it should lose it. An elimination with no interchanges is first wrong slightly higher, at 3.2·10⁻¹¹ to 3.2·10⁻⁸, on the same slope.

The count through an orthonormal null-space basis is not wrong anywhere on the grid for three of the four curvatures, and at h = −100 only at 5.6·10⁻¹⁶. That route forms Z from a QR of $A^{\mathsf{T}}$, and a QR resolves the direction $v_4$ as long as σ is above the rounding of A itself; it never forms the pair at all.

And the constraint is still there. A rank decision at the conventional tolerance — singular values below max(m, n)·u·‖A‖, here 1.1·10⁻¹⁵ — keeps all four constraints down to σ = 1.1·10⁻¹⁵. Rank is a decision argued that a floating-point matrix does not have a rank until someone chooses a threshold; this is a second, unchosen threshold, set by the curvature of H rather than by anybody, and it sits four to seven decades above the chosen one.

What the count sees instead #

A wrong count is not noise. Below its threshold the count reports one of two things, and which one depends on the sign of h.

With h = −1 the weak direction curves downwards. If the fourth constraint were removed, that direction would be free, and the problem’s reduced Hessian would have a negative eigenvalue: the point would be a saddle of the problem with three constraints. Below σ = 10⁻⁸ that is exactly what the count starts reporting, (9, 5, 0) rather than (10, 4, 0), on some draws and not others: three of eight at σ = 10⁻⁸·⁵, four of eight at 10⁻¹², six of eight at 10⁻¹⁶, with the rest reporting the minimum and an occasional count that is neither.

It does not settle as σ keeps falling. The sign of an eigenvalue of size 10⁻²⁰ in a matrix whose rounding is 10⁻¹⁶ is decided by the rounding, and the rounding is different on every draw and at every σ. So the count has not switched from one verdict to the other. It has stopped being a function of the problem.

With h = +1 the dropped problem has the same verdict as the full one — the free direction curves upwards — so no wrong count can masquerade as a verdict. What the count reports instead, on three to six of eight draws, is a count with too few negative eigenvalues — eleven positive and three negative, more positive eigenvalues than there are unknowns, or a zero pivot. No second-order question has that answer. A code that checks the count for exactly (n, m, 0) sees “wrong” and nothing more specific.

So the same loss of resolution produces, depending on a curvature the solver has no reason to look at, either a plausible false verdict or an impossible one. The first is the dangerous case, and it is the one with h < 0 — negative curvature along a direction a nearly redundant constraint is holding in place, which is precisely the situation in which the constraint matters.

No shift of H brings it back #

The loop that stops at the first right count responds to a wrong count in one way: it adds δ to every diagonal entry of H. Here that is the wrong repair, and the measurement says how wrong.

Down to σ = 10⁻⁷ the loop shifts nothing, because the count is right. Below 10⁻⁸ it shifts 22 of 88 draws, by as much as 5.12 at σ = 10⁻⁹, 2,620 at 10⁻¹⁰, 0.64 at 10⁻¹¹ and 10⁻¹², and 5.12 again at 10⁻¹⁴. Every one of those shifts is a Newton step on a problem convexified by something between 10⁻⁴ and several thousand, on a problem whose reduced Hessian has smallest eigenvalue 0.5.

The mechanism is in the pair. Adding δ to H changes the block to [[h + δ, σ], [σ, 0]]. For δ < |h| the small eigenvalue is still $\sigma^2$/|h + δ|, still unresolvable, still a coin toss. For δ > |h| the weak direction now curves upwards and the dropped problem’s verdict becomes “minimum” — but the small eigenvalue is −$\sigma^2$/(h + δ), still unresolvable, so the count can still read wrong the other way. There is no shift at which $\sigma^2$ is resolved, because $\sigma^2$ is not a property of H. The loop stops when a reading happens to come out right, and the shift it has reached by then is decided by how many readings that took.

At h = −100 the loop shifts 27 of 88 draws, and the largest shift is 5.12: no draw’s loop reached a shift anywhere near |h| = 100, because each stopped on a reading that came out right first. The shift reported is not about the curvature in either case.

A perturbation that decides #

The second repair codes use for dependent constraints acts on the other block. Subtract a small $\delta_c$ from the constraint block’s diagonal — K’s zero block becomes $-\delta_c I$ — and the pair becomes

With h < 0, the determinant is positive when $\sigma^2$ < $|h|\,\delta_c$ and negative when $\sigma^2$ > $|h|\,\delta_c$. A negative determinant is one eigenvalue of each sign, the full verdict; a positive determinant with a negative trace is two negative eigenvalues, the dropped verdict. And none of the three quantities in that comparison is small unless σ is: $|h|\,\delta_c$ at $\delta_c$ = 10⁻⁸ and h = −1 is 10⁻⁸, which any factorisation resolves.

Every draw reads the full verdict above σ = $\sqrt{|h|\,\delta_c}$ = 10⁻⁴ and every draw reads the dropped verdict below it. At the threshold itself, 10⁻⁴, the eight draws split five to three. There is no scatter anywhere else on the grid of thirty-three values of σ.

At h = −100 and $\delta_c$ = 10⁻¹² the threshold is 10⁻⁵, and the verdicts switch there on every draw: eight full at 10⁻⁴·⁵, four full, three dropped and one neither at 10⁻⁵, eight dropped from 10⁻⁵·⁵ down. At h = −100 and $\delta_c$ = 10⁻⁸ the threshold is 10⁻³ and the switch is there too.

That is a genuine repair of the thing rounding was doing — the count is a function of the problem again — and it is worth being precise about what it repairs. It does not make the count see the constraint. It moves the place where the constraint stops being seen from $\sigma \approx 10^{-9}\sqrt{|h|}$, set by rounding, to σ = $\sqrt{|h|\,\delta_c}$, set by $\delta_c$, and it makes that place exact. With $\delta_c$ = 10⁻⁸ the count declares the constraint dependent five decades earlier than rounding did, on every draw, including draws whose unperturbed count was right. The perturbation that does the work found the constraint-block perturbation deciding legality and growth for every ordering of a quasi-definite matrix; here the same perturbation is deciding rank, and its decision depends on the curvature along the direction it is deciding about.

Where a weak constraint comes from #

The construction chooses σ directly, and it is fair to ask whether problems hand it over in this form. They do, and the commonest source is one these essays have already met with the dependence exact rather than near.

A network’s conservation laws are the rows of its node–arc incidence matrix, one per node, and the rows sum to zero: flow into every node balances, so the balance at the last node is implied by all the others. The vertex nobody solves for measured the three ways of removing that exact dependence, and every code removes it by grounding a node or an equivalent. What grounding cannot remove is a dependence that is nearly exact. When a part of the network is attached to the rest by arcs whose weight is small — a component nearly isolated, a pipe nearly closed — the conservation law for that part is nearly implied by the others, and the incidence matrix weighted by the arcs acquires a singular value that goes to zero with the small weight. The tree the resistances choose found that spreading resistances over six decades is an ordinary network; a singular value of 10⁻⁹ is three more decades.

The second source is degeneracy at a solution. When more constraints are active at a point than the geometry needs — two of them nearly parallel, or an equality and a bound touching at the same place — the Jacobian of the active constraints is nearly rank-deficient exactly at the point being certified. An interior-point method meets this at the end of its solve, where a condition number sent to infinity found it already separating its diagonal by many orders, and the end of the solve is where a second-order verdict is read.

In both cases the curvature along the weak direction is whatever the objective happens to have there, and nothing in the problem’s statement makes it positive.

What a code would need to read #

The threshold $\sqrt{|h|\,\delta_c}$ has two factors and a code chooses only one of them. The curvature h along a constraint’s weak direction is not something an optimiser computes: finding it needs the constraint’s smallest singular vector and one product with H. A code that chooses $\delta_c$ without it is choosing the dependence threshold only up to a factor of $\sqrt{|h|}$, which on these problems is a factor of a hundred between h = −10⁻⁴ and h = −1.

It also means that the constraint-block perturbation and the Hessian shift are not interchangeable repairs for a wrong count, although both are responses to the same symptom. A wrong count caused by indefinite curvature in the null space is repaired by shifting H, and the shift loop’s own measurement says how badly. A wrong count caused by a nearly dependent constraint is not repaired by shifting H at any size, and is replaced by an exact decision when $\delta_c$ is applied. The symptom — the integer is not (n, m, 0) — is the same in both, and a solver that sees only the integer has no way to tell which it is looking at.

The null-space route can. Its count is right to rounding on every draw here, because it forms Z by a QR that resolves σ down to u·‖A‖. Two ways to remove a constraint measured the price of that route in fill and conditioning; this is a place where it earns it, at the cost of one QR of $A^{\mathsf{T}}$ performed only when the count has gone wrong.

When the weak direction is coupled #

The construction so far writes H with no coupling between the weak direction and the null space, which isolates the pair. Couple them — off-diagonal entries of size 0.3 in V’s basis — and the curvature that enters the pair is no longer h but the Schur complement h − $c^{\mathsf{T}}$(ZᵀHZ)⁻¹c, which does not go to zero with h.

With coupling, the first failure moves up at every curvature — 5.6·10⁻¹⁰, 7.8·10⁻¹⁰, 2.1·10⁻⁹ and 3.2·10⁻⁸ at h = −10⁻⁴, −0.01, −1 and −100 — and the fitted slope falls to 0.28. At small |h| the coupling term dominates the effective curvature and the threshold stops depending on h; at large |h| the curvature dominates and the $\sqrt{|h|}$ law returns. The picture is the same picture with the curvature replaced by the one the pair actually sees, and the null-space count is unaffected.

What this rests on, and what it leaves #

One shape, 10 × 4, one weak constraint, and a Hessian constructed in the constraint’s own singular basis so that h and its coupling are chosen directly. Eight draws per point. The rank tolerance quoted is the conventional max(m, n)·u·‖A‖ and is not itself measured.

The claim is about the count, not about the solve. A Newton step computed from K near σ = 10⁻⁹ has its own accuracy question — the multiplier of a nearly dependent constraint is poorly determined by the data, whatever the factorisation does — and that is not measured here.

The claim that fails #

The claim is that a count and a rank test drop a dependent constraint at the same place: the count reads the matrix, the rank test reads the constraint, and a constraint that has numerical rank is one the matrix still carries. Fed curvature −1 along the weak direction and required to show the count’s first failure below 10⁻¹⁴, it fails at 1.4·10⁻⁹. The null-space count kept beside it, right to rounding, is what makes the failure the count’s rather than the problem’s.

Still open: the step, the loop that knows, and several weak constraints #

The accuracy of the step itself. A factorisation of K that has lost the sign of $\sigma^2$/|h| has lost more than a sign: the pivot it divided by is wrong in every digit. How the Newton step’s error in the weak direction and in its multiplier grows as σ falls, and whether it grows before or after the count fails, decides whether a code that trusts its step but not its count is any safer.

A loop that tells the two causes apart. When the count is wrong, one QR of $A^{\mathsf{T}}$ both reveals σ and gives the count through Z. A loop that performs it once on a wrong count, and shifts H only when the null-space count is also wrong, would never apply the Hessian shift measured above. What that costs on the problems where the shift was the right repair is the other half of the measurement.

Several nearly dependent constraints. Two weak constraints give two pairs, each with its own $\sigma^2$/|$h_i$|, and a coupling between their weak directions mixes the two curvatures. Whether the count fails at the weaker of the two thresholds, or at a threshold set by the coupled 2 × 2 curvature, is the same question a wrap with two near-zeros asked of a correction, asked of a count.