Coverage for src/cvxcla/_checks.py: 100%
61 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"""Acceptance checks for a Critical Line Algorithm turning point.
3Before a candidate turning point is stored it must pass two independent tests:
4the free-asset covariance block must be numerically non-singular, so the solve
5that produced the candidate can be trusted (:func:`guard_degeneracy`), and the
6weights must satisfy every constraint of the problem to tolerance
7(:func:`check_feasible`). :func:`well_conditioned` decides once, up front,
8whether the first test can ever fire. Both are pure functions of the problem data and the
9candidate, so they live here rather than on the ``CLA`` class; ``CLA._emit`` and
10``CLA._append`` call them at every turning point.
11"""
13from __future__ import annotations
15import numpy as np
16from numpy.typing import NDArray
17from scipy.linalg import null_space # type: ignore[import-untyped]
18from scipy.optimize import linprog # type: ignore[import-untyped]
20from ._kkt import Segment
21from .errors import DegenerateProblemError, FeasibilityError
22from .operators import RCOND_FLOOR, QuadraticForm
25def check_feasible(
26 weights: NDArray[np.float64],
27 lower: NDArray[np.float64],
28 upper: NDArray[np.float64],
29 a: NDArray[np.float64],
30 b: NDArray[np.float64],
31 g: NDArray[np.float64],
32 h: NDArray[np.float64],
33 leverage: float | None,
34 tol: float,
35) -> None:
36 """Refuse weights that violate any constraint of the problem.
38 The box, ``G w <= h`` and leverage checks use ``tol``; the equality
39 ``A w = b`` is checked to a fixed ``1e-7`` absolute tolerance. An empty
40 ``g`` makes the inequality check vacuously true, so it never fires when there
41 are no inequality rows; ``leverage=None`` skips the gross-exposure check.
43 Args:
44 weights: The candidate weight vector.
45 lower: Per-asset lower bounds.
46 upper: Per-asset upper bounds.
47 a: Equality-constraint matrix ``A`` of ``A w = b``.
48 b: Equality-constraint right-hand side ``b``.
49 g: Inequality-constraint matrix ``G`` of ``G w <= h`` (``(p, n)``).
50 h: Inequality-constraint right-hand side ``h`` (length ``p``).
51 leverage: The gross-exposure cap ``||w||_1 <= leverage``, or ``None``.
52 tol: Tolerance for the box, inequality and leverage checks.
54 Raises:
55 FeasibilityError: Naming the first violated constraint. A turning point
56 that fails here after projection signals a numerical failure.
57 """
58 # (constraint holds?, message if it does not).
59 checks: tuple[tuple[bool, str], ...] = (
60 (bool(np.all(weights >= (lower - tol))), "Weights below lower bounds"), # pragma: no mutate
61 (bool(np.all(weights <= (upper + tol))), "Weights above upper bounds"), # pragma: no mutate
62 (bool(np.allclose(a @ weights, b, atol=1e-7)), "Weights violate the equality constraint A w = b"),
63 (bool(np.all(g @ weights <= h + tol)), "Weights violate the inequality constraint G w <= h"),
64 (
65 leverage is None or bool(np.abs(weights).sum() <= leverage + tol),
66 "Weights violate the leverage constraint ||w||_1 <= leverage",
67 ),
68 )
69 for ok, message in checks:
70 if not ok:
71 raise FeasibilityError(message)
74def well_conditioned(cov: QuadraticForm) -> bool:
75 """Whether every free-block solve along the trace is numerically safe.
77 By Cauchy's interlacing theorem every principal submatrix of the symmetric
78 PSD covariance is at least as well conditioned as the whole matrix --
79 deleting rows/columns cannot decrease the smallest eigenvalue nor increase
80 the largest -- so the reciprocal condition number of any free block is
81 ``>=`` that of the full covariance. Hence if the full covariance clears the
82 singularity floor, no free block encountered along the trace can be
83 singular, and :func:`guard_degeneracy` is provably never triggered. The
84 caller then skips it, paying one conditioning test up front instead of one
85 at every turning point (the latter is a full eigendecomposition of the free
86 block, as costly as the KKT solve, so it otherwise dominates the trace).
88 When the full covariance is itself near-singular (for example a sample
89 covariance from fewer observations than assets) this is ``False`` and the
90 per-step guard runs unchanged, preserving the degeneracy diagnosis exactly.
92 Args:
93 cov: The covariance as a ``QuadraticForm`` backend.
95 Returns:
96 Whether the full covariance clears the singularity floor.
97 """
98 return float(cov.rcond_free(np.arange(cov.n))) >= RCOND_FLOOR
101def _reduced_rcond(cov: QuadraticForm, index: NDArray[np.intp], c_free: NDArray[np.float64]) -> float:
102 """Reciprocal condition number of the free block on the null space of ``c_free``.
104 A null space of dimension zero (as many independent rows as free assets) fixes the
105 free weights by the rows alone, so the block plays no part and the result is ``1``.
106 """
107 basis = null_space(c_free)
108 if basis.shape[1] == 0:
109 return 1.0
110 block = np.asarray(cov.block_matvec(index, index, basis), dtype=np.float64)
111 eigenvalues = np.abs(np.linalg.eigvalsh(basis.T @ block))
112 return float(eigenvalues.min() / max(float(eigenvalues.max()), 1e-300))
115def guard_degeneracy(
116 cov: QuadraticForm, lamb: float, free: NDArray[np.bool_], rows: NDArray[np.float64] | None = None
117) -> None:
118 """Refuse the turning point when its reduced KKT system is numerically singular.
120 We distinguish two regimes by the conditioning of the free-asset block.
121 While that block stays numerically full rank its solve is reliable and any
122 box violation is round-off, which :func:`cvxcla._projection.project_feasible`
123 clears. Once the free set grows past the covariance rank the block is
124 numerically singular and its solve is unreliable; whatever weights it produces
125 (feasible or not) cannot be trusted, so we refuse and raise an actionable
126 diagnosis instead of silently returning a possibly-suboptimal frontier.
128 The discriminator is the free block's reciprocal condition number, read
129 from its symmetric eigenvalues. Unlike the magnitude of the box violation,
130 which is the residual of a singular solve and therefore varies with the
131 BLAS/LAPACK build, the conditioning is deterministic and portable, so the
132 completed-vs-declined boundary is the same on every platform.
134 A singular free block does not by itself make the turning point singular: the
135 active constraint rows ``C`` hold the free assets on their null space, and the
136 KKT system is uniquely solvable when the free block is positive definite there.
137 So a free block below the floor is tested again on that null space, ``Z^T
138 Sigma_FF Z`` with ``C_F Z = 0``, and the point is refused only when that is
139 singular too (see :func:`cvxcla.operators.bordered_solve`, whose ``dense`` route
140 solves such a segment). A LASSO with more predictors than observations reaches
141 this: its free set outgrows the rank of the Gram matrix before the fit
142 interpolates, and the constraint rows hold it.
144 The caller skips this check entirely when the full covariance is well
145 conditioned: by interlacing no free block can then be singular, so the check
146 is provably redundant (see :func:`well_conditioned`).
148 Args:
149 cov: The covariance as a ``QuadraticForm`` backend.
150 lamb: Lambda value of the candidate turning point, used in the message.
151 free: Boolean mask of the free assets at the candidate.
152 rows: The active constraint rows ``[A ; G_active]`` (``(k, n)``), or ``None``
153 to test the free block alone.
155 Raises:
156 DegenerateProblemError: With a degeneracy-specific message when the
157 reduced system is numerically singular (an unreliable solve);
158 otherwise returns without effect.
159 """
160 index = np.flatnonzero(free)
161 rcond = float(cov.rcond_free(index))
162 if rcond < RCOND_FLOOR and rows is not None and rows.shape[0]:
163 rcond = _reduced_rcond(cov, index, rows[:, index])
164 if rcond < RCOND_FLOOR:
165 n_free = int(np.count_nonzero(free))
166 msg = (
167 f"Critical Line Algorithm hit a degeneracy at lambda={lamb:.4g} "
168 f"(free-set size {n_free}): the free-asset covariance block is "
169 f"numerically singular (reciprocal condition number {rcond:.2g}), "
170 "so its solve is unreliable and the turning point cannot be "
171 "trusted. The trace was stopped rather than risk silently "
172 "returning a suboptimal frontier. This happens when the free set "
173 "grows past the covariance rank (for example a sample covariance "
174 "from far fewer days than assets). Use a well-conditioned, "
175 "full-rank estimate (ample history), or a FactorCovariance backend "
176 "(diagonal-plus-low-rank), which is positive definite by construction."
177 )
178 raise DegenerateProblemError(msg)
181def check_held_bounds(
182 segment: Segment,
183 lamb: float,
184 event: int,
185 rows: NDArray[np.float64],
186 lower: NDArray[np.float64],
187 upper: NDArray[np.float64],
188 tol: float,
189 mu_scale: float,
190 cov_scale: float,
191) -> None:
192 """Refuse a segment that ends at a point off the efficient frontier.
194 On a segment the multiplier of a blocked asset is ``gamma + lambda * delta``:
195 non-negative on a lower bound and non-positive on an upper one wherever the
196 segment is optimal. A sign change inside the segment is an event and would have
197 ended it sooner, so the sign is checked where the segment ends, at ``lamb``. The
198 event scan cannot report a sign that is wrong on the whole segment. That happens
199 when the maximum-return vertex is degenerate and its resolution picks a partition
200 from the returns alone: the bounds that tie in the returns have ``delta = 0``, so
201 they fire no event, and their ``gamma`` (set by ``q - Sigma w``) can have the wrong
202 sign. The trace would then run on a partition that is not optimal anywhere and
203 return a wrong path without error.
205 A wrong sign is not proof by itself: when a free asset sits on a bound the point
206 is primal degenerate, its multipliers are not unique, and another choice may
207 certify it. So a flagged point is confirmed by :func:`_certified`, which looks for
208 any multipliers of the active rows that make the point optimal.
210 Args:
211 segment: The segment that ends at ``lamb``.
212 lamb: The finite ``lambda`` at which the segment ends.
213 event: The asset whose event ends the segment (its multiplier is zero there),
214 or ``-1`` when no asset event ends it.
215 rows: The active constraint rows ``[A ; G_active]`` of the segment.
216 lower: Per-asset lower bounds.
217 upper: Per-asset upper bounds.
218 tol: Tolerance for classifying a weight as sitting on a bound.
219 mu_scale: The scale of the returns, which sets the scale of ``delta``.
220 cov_scale: The scale of ``Sigma w`` and ``q``, which sets the scale of ``gamma``.
222 Raises:
223 DegenerateProblemError: If the point at ``lamb`` is not optimal.
224 """
225 multiplier = segment.gamma + lamb * segment.delta
226 scale = max(cov_scale, lamb * mu_scale, float(np.max(np.abs(segment.gamma), initial=0.0)))
227 floor = float(np.sqrt(np.finfo(np.float64).eps)) * scale
228 wrong = (segment.at_lower & (multiplier < -floor)) | (segment.at_upper & (multiplier > floor))
229 if event >= 0:
230 wrong[event] = False
231 if not np.any(wrong):
232 return
233 weights = segment.r_alpha + lamb * segment.r_beta
234 eta = (segment.eta_alpha + lamb * segment.eta_beta)[segment.active_ineq]
235 if _certified(multiplier, eta, weights, segment.free_in, rows, lower, upper, tol, floor):
236 return
237 msg = (
238 f"The segment ending at lambda={lamb:.4g} held {int(np.count_nonzero(wrong))} asset(s) on a "
239 "bound it should have left, so it is not on the efficient frontier, and no choice of the "
240 "active rows' multipliers certifies the point. This comes from a degenerate turning point "
241 "whose bounds tie, where the segment's multipliers are not unique. Perturb the returns or "
242 "the constraints so the turning point is non-degenerate."
243 )
244 raise DegenerateProblemError(msg)
247def _certified(
248 multiplier: NDArray[np.float64],
249 eta: NDArray[np.float64],
250 weights: NDArray[np.float64],
251 free: NDArray[np.bool_],
252 rows: NDArray[np.float64],
253 lower: NDArray[np.float64],
254 upper: NDArray[np.float64],
255 tol: float,
256 floor: float,
257) -> bool:
258 """Whether some multipliers of the active rows make the point optimal.
260 The segment's multipliers ``y`` leave a blocked asset the multiplier ``m`` (zero
261 on the free assets). Shifting them by ``dy`` changes every asset's multiplier by
262 ``C^T dy`` and the inequality multipliers by ``dy`` on their rows. The point is
263 optimal if some shift leaves the free assets that are strictly inside their box
264 at zero, every asset on a lower bound non-negative and every asset on an upper
265 bound non-positive -- free assets that sit on a bound included, which is what
266 the segment's own multipliers do not allow -- and the active inequality
267 multipliers non-negative. That is a linear feasibility problem in ``dy``.
269 Args:
270 multiplier: The asset multipliers at the point (zero on the free assets).
271 eta: The active inequality multipliers at the point.
272 weights: The point.
273 free: Mask of the free assets.
274 rows: The active constraint rows ``C = [A ; G_active]`` (equalities first).
275 lower: Per-asset lower bounds.
276 upper: Per-asset upper bounds.
277 tol: Tolerance for classifying a weight as sitting on a bound.
278 floor: Tolerance on the multipliers.
280 Returns:
281 ``True`` when the point is optimal.
282 """
283 on_lower = weights <= lower + tol
284 on_upper = weights >= upper - tol
285 m = np.where(free, 0.0, multiplier)
286 interior = free & ~on_lower & ~on_upper
287 # m + C^T dy >= -floor on a lower bound, <= floor on an upper one, |.| <= floor inside.
288 up = on_lower | interior
289 down = on_upper | interior
290 k = rows.shape[0]
291 p = eta.shape[0]
292 a_ub = np.vstack([-rows.T[up], rows.T[down], -np.eye(k)[k - p :]])
293 b_ub = np.concatenate([m[up] + floor, floor - m[down], eta + floor])
294 if k == 0:
295 # No active rows, so no multipliers to shift: the point is optimal as it stands
296 # or not at all. linprog refuses a problem without variables.
297 return bool(np.all(b_ub >= 0))
298 result = linprog(np.zeros(k), A_ub=a_ub, b_ub=b_ub, bounds=[(None, None)] * k, method="highs")
299 return bool(result.status == 0)