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

1"""Equality-augmented reduction: the Schur-complement saddle solve on a free set. 

2 

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. 

9 

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""" 

15 

16from __future__ import annotations 

17 

18from typing import TYPE_CHECKING 

19 

20import numpy as np 

21from cvx.linalg import Matrix, SymmetricOperator, Vector, cholesky_solve 

22from numpy.typing import NDArray 

23 

24if TYPE_CHECKING: 

25 from .solver import InnerSolver 

26 

27 

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``. 

38 

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. 

46 

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``. 

55 

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 

78 

79 

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,)``. 

82 

83 Args: 

84 b_eq: Equality matrix ``B``. 

85 c_eq: Equality right-hand side ``c``. 

86 n: Problem dimension ``len(b)``. 

87 

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) 

99 

100 

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``. 

103 

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. 

108 

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|)``. 

114 

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