Coverage for src/nncg/_equality.py: 100%
33 statements
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-13 11:20 +0000
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-13 11:20 +0000
1"""Equality-augmented reduction: the Schur-complement saddle solve on a free set.
3Factored out of :meth:`nncg.solver.ActiveSetSolver.solve_eq` so the outer loop
4keeps only its orchestration. On a free set the saddle system for ``B x = c`` is
5solved by eliminating the multiplier ``lambda`` in R^p through the p-by-p Schur
6complement ``S = B_F A_F^{-1} B_F^T``: the ``p + 1`` right-hand sides share the
7operator ``A_F`` and are each one inner solve, then ``S lambda = c - B_F v0``
8fixes the multipliers in closed form.
10Also home to the equality-specific input check (:func:`_require_eq_shapes`) and
11the feasibility certificate (:func:`_eq_feasible`) that ``solve_eq`` adds on top
12of the KKT exit: a rank-deficient, inconsistent ``B`` can pass the KKT test
13while ``B x != c``, and must not be reported as converged.
14"""
16from __future__ import annotations
18from typing import TYPE_CHECKING
20import numpy as np
21from cvx.linalg import Matrix, SymmetricOperator, Vector, cholesky_solve
22from numpy.typing import NDArray
24if TYPE_CHECKING:
25 from .solver import InnerSolver
28def _saddle_solve(
29 inner: InnerSolver,
30 a: SymmetricOperator,
31 b: Vector,
32 b_eq: Matrix,
33 c_eq: Vector,
34 idx: NDArray[np.int_],
35 x0: Vector | None,
36) -> tuple[Vector, Vector, int]:
37 """Solve the equality-augmented saddle system on the free set ``idx``.
39 Runs ``p + 1`` inner solves through the shared free-block operator ``A_F``
40 (the ``v0`` column warm-started at ``x0``, the ``v1`` columns cold), forms the
41 SPD Schur complement ``S = B_F A_F^{-1} B_F^T`` and recovers the multipliers
42 from ``S lambda = c - B_F v0`` before back-substituting ``x_F = v0 + v1 lambda``.
43 When ``B_F`` is rank-deficient ``S`` is singular and the multipliers fall back
44 to the least-squares solution; the caller's feasibility check then decides
45 whether ``B x = c`` actually holds.
47 Args:
48 inner: The inner solver driving each free-block solve.
49 a: The SPD operator ``A``.
50 b: The linear term ``b``.
51 b_eq: Equality matrix ``B`` of shape ``(p, n)``, full row rank on ``idx``.
52 c_eq: Equality right-hand side ``c`` of shape ``(p,)``.
53 idx: Integer positions of the free set ``F``.
54 x0: Warm inner guess for the ``v0`` column restricted to ``idx``, or ``None``.
56 Returns:
57 ``(x_F, lam, inner_iters)``: the free-block solution, the equality
58 multipliers, and the total inner iteration count across all columns.
59 """
60 p = b_eq.shape[0]
61 b_f = b_eq[:, idx]
62 v0, k0 = inner.solve(a, idx, b[idx], x0)
63 v1 = np.zeros((idx.size, p))
64 k_cols = 0
65 for j in range(p):
66 v1[:, j], kj = inner.solve(a, idx, b_f[j], None)
67 k_cols += kj
68 schur = b_f @ v1 # p-by-p Schur complement, SPD when B_F has full row rank
69 rhs = c_eq - b_f @ v0
70 try:
71 lam = cholesky_solve(schur, rhs)
72 except np.linalg.LinAlgError:
73 # Rank-deficient B_F: take the least-squares multipliers and leave the
74 # verdict on B x = c to _eq_feasible rather than crashing the solve.
75 lam = np.asarray(np.linalg.lstsq(schur, rhs, rcond=None)[0], dtype=np.float64)
76 xf = v0 + v1 @ lam # x_F = A_F^{-1}(b_F + B_F^T lambda)
77 return xf, lam, k0 + k_cols
80def _require_eq_shapes(b_eq: Matrix, c_eq: Vector, n: int) -> None:
81 """Validate that ``B`` has shape ``(p, n)`` and ``c`` has shape ``(p,)``.
83 Args:
84 b_eq: Equality matrix ``B``.
85 c_eq: Equality right-hand side ``c``.
86 n: Problem dimension ``len(b)``.
88 Raises:
89 ValueError: When ``b_eq`` is not two-dimensional with ``n`` columns, or
90 ``c_eq`` is not one-dimensional with one entry per row of ``b_eq``.
91 """
92 b_shape, c_shape = np.shape(b_eq), np.shape(c_eq)
93 if len(b_shape) != 2 or b_shape[1] != n:
94 msg = f"b_eq must have shape (p, {n}), got {b_shape}"
95 raise ValueError(msg)
96 if c_shape != (b_shape[0],):
97 msg = f"c_eq must have shape ({b_shape[0]},) to match b_eq {b_shape}, got {c_shape}"
98 raise ValueError(msg)
101def _eq_feasible(b_eq: Matrix, c_eq: Vector, x: Vector, tol: float) -> bool:
102 """Return whether ``x`` satisfies ``B x = c`` to the relative tolerance ``tol``.
104 With ``B_F`` of full row rank the Schur-complement solve makes ``B x = c``
105 hold to rounding, so this only fails when the rank precondition is violated
106 and ``c`` lies outside the range of ``B_F`` — the case the KKT test alone
107 would certify.
109 Args:
110 b_eq: Equality matrix ``B`` of shape ``(p, n)``.
111 c_eq: Equality right-hand side ``c`` of shape ``(p,)``.
112 x: The candidate solution.
113 tol: Tolerance on ``max|B x - c|``, relative to ``max(1, max|c|)``.
115 Returns:
116 True when the equality residual is within tolerance.
117 """
118 scale = max(1.0, float(np.max(np.abs(c_eq), initial=0.0)))
119 return float(np.max(np.abs(b_eq @ x - c_eq), initial=0.0)) <= tol * scale