Coverage for src/cvxcla/operators/_core.py: 100%

38 statements  

« prev     ^ index     » next       coverage.py v7.17.3, created at 2026-11-17 13:36 +0000

1"""Operator protocol alias and the parametric-path helpers built on cvx-linalg. 

2 

3The parametric active-set path tracer reaches its Hessian through the cvx-linalg 

4symmetric-operator protocol (``matvec`` / ``block_matvec`` / ``solve_free`` / 

5``rcond_free``). :data:`QuadraticForm` is that contract; :data:`CovarianceOperator` 

6is a backward-compatible alias for the portfolio (covariance) setting. The 

7concrete backends live in :mod:`cvx.linalg`; :mod:`cvxcla.operators.builders` 

8assembles them from CLA / LASSO inputs. 

9 

10The generic linear algebra -- the bordered KKT (Schur complement) solve and the 

11affine projection -- also lives in :mod:`cvx.linalg`. What remains here is the 

12thin homotopy-specific glue: adapting the loop's boolean masks to the operators' 

13integer-index API, and packing the constant / ``lambda``-slope pair of a 

14parametric segment into the shared multi-RHS solve. 

15""" 

16 

17from __future__ import annotations 

18 

19import numpy as np 

20from cvx.linalg import SymmetricOperator 

21from cvx.linalg import bordered_solve as _bordered_solve 

22from numpy.typing import NDArray 

23from scipy.linalg import solve_triangular # type: ignore[import-untyped] 

24 

25# The Hessian contract for a parametric active-set path. In the CLA it is the 

26# covariance ``Sigma``; in a LASSO / LARS path it is the Gram matrix ``X.T @ X``. 

27QuadraticForm = SymmetricOperator 

28CovarianceOperator = SymmetricOperator 

29 

30# The singularity threshold for ``rcond_free``. A genuinely rank-deficient free 

31# block has a reciprocal condition number at round-off level (~1e-16); a 

32# well-posed or merely near-degenerate block sits many orders above it (>= ~1e-4 

33# across the degeneracy sweep in experiments/degeneracy_boundary.py). The 1e-12 

34# cut sits in the wide gap between the two and is the conventional 

35# numerical-singularity scale. 

36RCOND_FLOOR = 1e-12 # pragma: no mutate 

37 

38 

39def cross(operator: SymmetricOperator, free: NDArray[np.bool_], x: NDArray[np.float64]) -> NDArray[np.float64]: 

40 """Free-to-blocked cross product ``H[free][:, ~free] @ x[~free]`` from a boolean mask. 

41 

42 Taken as one full product on ``x`` with its free entries zeroed, 

43 ``(H @ x_B)[free]``, which equals the cross block since the zeroed entries 

44 contribute nothing. A dense backend then runs a single contiguous matvec 

45 instead of first copying the ``(free, ~free)`` block out by fancy indexing, 

46 which dominated this product along the trace. 

47 

48 Args: 

49 operator: The symmetric operator (Hessian) backend. 

50 free: Boolean mask of shape ``(n,)`` selecting the free coordinates. 

51 x: Full-length vector of shape ``(n,)``; only ``x[~free]`` enters the product. 

52 

53 Returns: 

54 Vector of shape ``(n_free,)``. 

55 """ 

56 result: NDArray[np.float64] = operator.matvec(np.where(free, 0.0, x))[free] 

57 return result 

58 

59 

60def bordered_solve( 

61 quad: SymmetricOperator, 

62 free: NDArray[np.bool_], 

63 c_free: NDArray[np.float64], 

64 rhs_const: NDArray[np.float64], 

65 rhs_slope: NDArray[np.float64], 

66 d_const: NDArray[np.float64], 

67 d_slope: NDArray[np.float64], 

68 dense: bool = False, 

69) -> tuple[ 

70 NDArray[np.float64], 

71 NDArray[np.float64], 

72 NDArray[np.float64], 

73 NDArray[np.float64], 

74]: 

75 """Solve the bordered KKT system for a parametric segment's constant and slope parts. 

76 

77 A thin adapter over :func:`cvx.linalg.bordered_solve`: it converts the loop's 

78 boolean *free* mask to integer indices and packs the constant and ``lambda``-slope 

79 right-hand sides as the two columns of one multi-RHS solve, so ``H_FF`` and the 

80 Schur complement are factorised once. Returns 

81 ``(x_const, x_slope, nu_const, nu_slope)`` (multipliers empty when there are no 

82 constraint rows). 

83 

84 The constraint rows are first replaced by an orthonormal basis of their span, 

85 ``C^T = Q R``, so the system solved is ``[[H_FF, Q], [Q^T, 0]]`` with target 

86 ``R^{-T} d`` and the multipliers are recovered as ``R^{-1} nu'``. Both describe 

87 the same solution, but the Schur complement ``C H_FF^{-1} C^T`` has condition 

88 number up to ``cond(H_FF) cond(C)^2``, so nearly dependent rows (several caps 

89 almost parallel on the free set) lose accuracy twice over, while 

90 ``Q^T H_FF^{-1} Q`` is no worse conditioned than ``H_FF`` itself. The weights 

91 are then accurate to about ``cond(C)`` times the round-off, the sensitivity of 

92 the constraint data, and the two factors are exactly what the free-block and 

93 active-row guards bound. With more rows than free coordinates the rows cannot 

94 be independent; the plain solve is used and reports the singular system. A 

95 single row is its own orthogonal basis, so it too takes the plain solve. 

96 

97 With ``dense`` the bordered matrix is formed from the free block and solved as a 

98 whole. That is the route when ``H_FF`` is singular but the system is not: ``H_FF`` 

99 then only needs to be positive definite on the null space of ``C``, which the 

100 elimination through ``H_FF^{-1}`` cannot use (more free coordinates than the rank of 

101 a Gram matrix, held by constraint rows). 

102 """ 

103 rhs = np.column_stack([rhs_const, rhs_slope]) 

104 d = np.column_stack([d_const, d_slope]) 

105 mc, n_free = c_free.shape 

106 if n_free == 0: 

107 # Nothing to solve: every coordinate is blocked. Reached only with no 

108 # constraint rows, where the segment is the vertex itself. 

109 return np.zeros(0), np.zeros(0), np.zeros(mc), np.zeros(mc) 

110 if dense: 

111 index = np.flatnonzero(free) 

112 block = np.asarray(quad.block_matvec(index, index, np.eye(n_free)), dtype=np.float64) 

113 kkt = np.block([[block, c_free.T], [c_free, np.zeros((mc, mc))]]) 

114 solution = np.linalg.solve(kkt, np.vstack([rhs, d])) 

115 x, nu = solution[:n_free], solution[n_free:] 

116 elif mc <= 1 or mc > n_free: 

117 x, nu = _bordered_solve(quad, np.flatnonzero(free), c_free, rhs, d) 

118 else: 

119 q, r = np.linalg.qr(c_free.T) 

120 x, nu_q = _bordered_solve(quad, np.flatnonzero(free), q.T, rhs, solve_triangular(r.T, d, lower=True)) 

121 nu = solve_triangular(r, nu_q) 

122 return x[:, 0], x[:, 1], nu[:, 0], nu[:, 1] 

123 

124 

125def orthonormal_rows(a: NDArray[np.float64], b: NDArray[np.float64]) -> tuple[NDArray[np.float64], NDArray[np.float64]]: 

126 """Rewrite ``A w = b`` with orthonormal rows spanning the same space, ``Q^T w = R^{-T} b``. 

127 

128 The affine set is unchanged, but nearly dependent rows stop hurting. Two nearly 

129 parallel rows (``1^T w = 1`` and ``(1 + eps v)^T w = 1`` encode ``v^T w = 0`` at 

130 scale ``eps``) give a linear program with an absolute feasibility tolerance that 

131 enforces the hidden row only to ``tol / eps``, and a projection whose Gram matrix 

132 ``C C^T`` has condition number ``cond(C)^2``; in the orthonormal form every 

133 direction of the span is enforced to the same tolerance and the Gram matrix is 

134 the identity. ``CLA`` drops redundant rows before tracing, so ``R`` is 

135 invertible there; rows that are dependent to round-off are passed through 

136 unchanged, for the caller to judge. 

137 

138 Args: 

139 a: Equality-constraint matrix (``m x n``). 

140 b: Equality-constraint right-hand side (length ``m``). 

141 

142 Returns: 

143 ``(Q^T, R^{-T} b)``; the input itself when there are no rows or they are 

144 dependent. 

145 """ 

146 if a.shape[0] == 0 or a.shape[0] > a.shape[1]: 

147 return a, b 

148 q, r = np.linalg.qr(a.T) 

149 diag = np.abs(np.diag(r)) 

150 if diag.min() <= a.shape[1] * np.finfo(np.float64).eps * diag.max(): # pragma: no mutate 

151 return a, b 

152 return q.T, solve_triangular(r.T, b, lower=True)