Module mpcc 

Policy for solving a model with declared complementarity pairs: which lowerings of pounce_nlp::mpcc::MpccTnlp to try, in what order, and what counts as an answer.

Workstream B of dev-notes/research/calipso-contact-plan.md. Like crate::second_opinion, this module holds the policy and runs no solves; the driver that runs them is pounce_restoration::mpcc_driver, so every entry point shares one implementation.

Why a ladder and not one route

Measured on benchmarks/calipso/ (seven complementarity models, POUNCE and Ipopt), no single lowering wins: the exact product is fast and solves most models from most starts but fails where a pair is biactive at the answer; the Scholtes continuation with full warm starts and an exact finish was the only route physical on 5/5 starts on bunny-hop and the drifting car, at several times the iterations; the ℓ₁ penalty was the only route that solved the quadruped on every seed. So the driver tries them in STAGES order: the continuation and the exact product both run and the better certified answer wins (compared); the penalty runs only if neither answers.

Why the continuation goes first

Measured on the Gate 0 corpus (benchmarks/mpcc/declared.py, 60 feasible cells: every case, both scaling legs, every start). Exact first: 60 solved, 0 below f*, but only 48 at f* — the exact product converges fast (median 19 iterations) to S-stationary local minima that are not the optimum (regular_strict 4 for 1, the selectors 0.75 for 0.25). Continuation first: 60 solved, 60 at f*, 0 below, median 60 iterations — against 57 at f* for scholtes_then_ncp, the route Gate 0 chose as supported. The relaxation at τ = 1 sees the whole feasible set before it commits to a branch; the exact product commits from the start. The cost is about 3× the iterations where the exact product would have found the optimum anyway. The exact product stays as the second stage, for models whose relaxation path fails.

What an answer is

A converged status is not enough: a lowered solve “succeeds” on its own reformulation, and the reformulation’s tolerance is not the model’s. A stage is accepted only if it converged, every product G·H is within constr_viol_tol — the bar the model’s own rows are held to — and certify finds the point stationary (answers). The last test is not redundant: through the Python callbacks, qpec_small’s exact-product stage exits “acceptable” with every product at 0 at a point 9e-4 short of the answer, which is not stationary (residual 1.7e-3 against 2e-6), and the continuation reaches the answer.

Structs

BCheck

check_b_stationarity’s verdict and what it took.

Certificate

What certify measured. Everything the verdict rests on is here.

CertificateInput

The point and model data certify reads. All indices 0-based, the Jacobian as (row, col, value) triplets of the inner model’s rows.

Enums

BVerdict

What check_b_stationarity found.

HeldSide

Which side of a pair is held at zero along a branch.

MpccStage

The stages, in the order the driver tries them.

Reported

Which point the driver reported, and on what grounds.

StationarityClass

The stationarity class a point was shown to satisfy; see certify.

Strategy

Which formulations a solve runs, from complementarity_strategy. The penalty runs under every strategy, as the fallback when nothing answers.

Constants

CORNER_SLACK_FACTOR

The multiple of a relaxed point’s first-order slack value (relaxation_slack) that same_answer_allowance grants. Σ λ_k·p_k is the objective the products’ slack buys to first order; where a pair is biactive the objective moves as sqrt(τ), not τ, and the first-order estimate is then half the true gap (MacMPEC scholtes4: the τ = 1e-8 point sits at -2e-4 = -2·sqrt(τ) against the exact f* = 0, with λ = 1/sqrt(τ), so λ·τ = 1e-4). Ten leaves a margin of five over that.

DENSE_ENTRIES

Up to this many entries the stationarity system is factored densely (a thin SVD, rank by LAPACK’s threshold); above it, by the interior-point method’s own sparse LDLᵀ of the least-squares augmented system ([sparse_least_squares]). The dense SVD’s cost grows as n·k²: on a 650-pair chain model (n = 1950) the solve took 4.8 s with the dense certificate and 0.51 s with the sparse one, and at 1100 pairs 31 s against 0.93 s, same class and answer. Below 2.5·10⁵ entries the SVD costs little and keeps the path the certificate was validated on against stationarity.py (the Gate 0 corpus, bunny-hop, ball-in-cup); the CALIPSO rocket (n = 856) is past it and certifies S on the sparse path exactly as it did densely. The unit tests hold the two paths to the same class on every point they check.

EXACT_BUDGET_FACTOR

The exact-product stage’s iteration budget once the continuation has already answered with a tight S point: EXACT_BUDGET_FACTOR times the iterations the continuation spent, never below EXACT_BUDGET_FLOOR.

EXACT_BUDGET_FLOOR

See EXACT_BUDGET_FACTOR.

EXACT_STAGE_TAU

The exact stage’s relaxation: one solve of G·H <= EXACT_STAGE_TAU from the model’s own start, then an exact finish. Measured against the cold exact product G·H = 0 on the 28 MacMPEC models where the exact stage costs most or matters most: 1879 iterations against 25712, 26 converged against 20, 23 at or better than the published value against 19. 1e-8 does worse (3311 iterations, 20 at): a thinner interior, back towards the degenerate system.

FINISH_BUDGET_FLOOR

The continuation’s finish budget: the exact-product solve warm-started at the end of the schedule. Never below this, nor below the iterations the schedule itself spent. Every finish that converged to Solve_Succeeded on MacMPEC took at most 411 iterations; the ones that ran past 500 all crawled to Solved_To_Acceptable_Level (up to 3188) at a point the schedule’s own answer already satisfies to τ = 1e-8, which the driver falls back to when the finish does not converge.

MAX_DENSE_ENTRIES

Above this many entries in the n × k stationarity matrix, a system whose multipliers are not unique is not searched and reports StationarityClass::NotSearched (which answers accepts, so the ladder is unchanged). The set search factors the matrix densely; at n ≈ 10⁴ with k ≈ n + m that is about 1 GB and 10¹² flops per call, a size contact-implicit trajectory models reach. 4·10⁶ entries (32 MB) keeps the call well under a second. A system with unique multipliers — the common case, MPCC-LICQ — is certified at any size, sparsely (see DENSE_ENTRIES).

MAX_ENUMERATED_BIACTIVE

Up to this many biactive pairs every one of the 2^b branches is checked; above it, one heuristic branch.

MAX_SEARCHED_COLUMNS

Above this many sign-constrained columns, a rank-deficient system is not searched (each NNLS step is an SVD of the passive columns).

RUNG_RETRY_FLOOR

The budget of a continuation rung retried after its warm-started solve failed: twice what the previous rung took, at least this.

SAFE_DEFAULTS

Defaults every stage runs under unless the caller set the option themselves. bound_relax_factor’s default of 1e-8 relaxes every bound and row before the solve, which on a complementarity pair means accepting G >= -1e-8, and at a cone tip or a pair’s corner turns into a violation of its square root: on benchmarks/calipso/ every reported success that violated the model was a run under that default. honor_original_bounds moves the answer back inside the bounds the model stated.

SAME_ANSWER_REL_TOL

How far, relative to max(|f_a|, |f_b|), two minimized objectives may differ and still be “the same answer” in the driver’s two tests below, on top of what the relaxations’ slack accounts for (same_answer_allowance). Far below the gaps between genuinely different branches (MacMPEC water-net: 953 against 964, 1.1%).

SCHOLTES_SCHEDULE

The relaxation schedule, as in benchmarks/mpcc/routes.py: it starts at 1 so a relaxation whose crossover lies in [0.25, 1] is seen, and ends four orders below the default constr_viol_tol.

STAGES

TOUCHED_OPTIONS

Every option any stage writes; the driver snapshots these before the first stage and restores them after the last.

Functions

accepts

Is a stage’s answer an answer to the model, not just to the lowering?

answers

Does a certified class make a converged, physical point the answer, ending the ladder? S, the goal; and NotSearched, which claims nothing either way and only arises on models large enough that more stages are costly. A W point is not: it admits a descent direction along some branch, and a later stage can reach an S point below it (kept_if_nothing_better). A point that is not stationary at all is a stall, and the driver moves on.

answers_agree

Do two answers agree, within same_answer_allowance? slack is the sum of the two points’ relaxation_slacks and gap of their complementarity_gaps. The exact stage’s cold G·H = 0 solve is skipped when the continuation’s answer and the exact stage’s relaxed path agree: two different routes landing on one point is evidence the cheap paths found the branch, and the cold solve – degenerate, often max_iter-bound, the largest single cost on MacMPEC – exists for the models where they do not (water-net, dempe). A slack or gap that is not finite never agrees, so the cold solve runs.

branch_bounds

The branch NLP’s bounds for held (one per pair): the held side pinned at zero, and, on a mixed pair held at a bound, the free row given the sign the pair requires there. For pounce_nlp::mpcc::MpccTnlp::set_branch.

budgeted_max_iter

The max_iter a budgeted solve runs under: budget, but never above the caller’s own max_iter.

certify

Which stationarity class x satisfies, as benchmarks/calipso/ stationarity.py decides it — same columns, same thresholds — so the two can be held to each other on the same points.

check_b_stationarity

Whether x is B-stationary: no direction d feasible for the linearized constraints along any branch of the biactive pairs has ∇f·d < 0.

compared

Are a stage’s S answers compared with the other compared stage’s, the lower objective winning, rather than ending the ladder? The continuation and the exact product: on a nonconvex model each reaches local minima the other avoids, and neither order wins on both corpora we have. Gate 0 (60 feasible cells) at f*: continuation first 60, exact first 48. CALIPSO bunny-hop (5 seeds) at the best known objective: exact first 5, continuation first 2 — the continuation settles on S-stationary trajectories at 1111–1169 against 462.6. Running both and keeping the lower objective gets every one of those, for the iterations of both. The penalty runs only when neither answers.

complementarity_gap

The objective error a converged point carries from stopping at a tolerance rather than at the optimum: its complementarity gap in the model’s own units,

converged

Statuses a stage can converge with.

describe_outcome

One line for the console: what answered, and what the answer is.

exact_stage_budget

The exact-product stage’s iteration budget: None (run in full) unless the continuation has already answered with a tight S point, in which case EXACT_BUDGET_FACTOR times the continuation_iterations it spent, at least EXACT_BUDGET_FLOOR.

finish_budget

The continuation finish’s iteration budget: what the schedule spent, at least FINISH_BUDGET_FLOOR.

finish_drifted

Did an exact finish drift off the relaxed answer it started from? True when the finish’s minimized objective is worse than the relaxed point’s by more than same_answer_allowance, with relaxed_slack the relaxed point’s relaxation_slack and no complementarity_gap term. A finish solves the degenerate exact product and can wander: MacMPEC pack-comp1p-32’s continuation reaches 0.65304 at τ = 1e-8 (products 5e-9) and its finish then crawls through restoration to 0.783, which used to replace it; the relaxed point is kept instead. On scholtes4 the finish’s 3e-11 is the exact answer and the relaxed -2e-4 is slack (λ·τ = 1e-4, allowance 1e-3), and the finish is kept – at any scaling of the objective. A slack that is not finite keeps the finish: there is nothing to measure the drift against.

kept_if_nothing_better

Is a converged, physical point that does not answers still worth reporting if no later stage certifies? W is: it is the honest answer where no S point exists nearby (ralph1’s origin). Measured on the CALIPSO corpus’s complementarity model, stopping at the first W point returned objective 85 where the continuation reaches the S optimum at 17.

relaxation_slack

The objective a relaxed point’s products buy, to first order: Σ |λ_k|· max(p_k, 0) over the product rows, λ_k the row’s multiplier and p_k its product G_k·H_k. Relaxing row k from 0 to p_k lowers the minimized objective by λ_k·p_k to first order, so this is how much worse an exact finish that removes the slack may look without having moved.

same_answer_allowance

How far two minimized objectives may differ and still be one answer: SAME_ANSWER_REL_TOL·max(|f_a|, |f_b|) + CORNER_SLACK_FACTOR·slack + gap, slack the relaxation_slack of the points compared (their sum when both are relaxed) and gap the sum of their complementarity_gaps. Every term scales with the objective, so neither test that uses it changes its verdict when f is multiplied by a constant (gh#1128: an absolute 1e-4 floor near zero, and an allowance proportional to max(1, |f|) rather than to the multipliers, both did). The gap is the floor near f = 0: what the two solves’ own tolerance leaves.

warm_start_assignments

The options a warm-started continuation stage sets, as pounce.WarmStart.options() does: the seeds are honoured, the barrier starts where the last stage stopped instead of re-walking from 0.1, and the pushes are tightened so a point at a bound stays there. Each is an upstream Ipopt option. The driver restores every one of them to the caller’s set-ness afterwards.