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
« 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.
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.
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"""
17from __future__ import annotations
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]
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
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
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.
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.
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.
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
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.
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).
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.
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]
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``.
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.
138 Args:
139 a: Equality-constraint matrix (``m x n``).
140 b: Equality-constraint right-hand side (length ``m``).
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)