Coverage for src/cvxcla/_checks.py: 100%
18 statements
« prev ^ index » next coverage.py v7.16.2, created at 2026-09-29 05:24 +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
18from .operators import QuadraticForm
19from .operators._core import _RCOND_FLOOR
22def check_feasible(
23 weights: NDArray[np.float64],
24 lower: NDArray[np.float64],
25 upper: NDArray[np.float64],
26 a: NDArray[np.float64],
27 b: NDArray[np.float64],
28 g: NDArray[np.float64],
29 h: NDArray[np.float64],
30 leverage: float | None,
31 tol: float,
32) -> None:
33 """Refuse weights that violate any constraint of the problem.
35 The box, ``G w <= h`` and leverage checks use ``tol``; the equality
36 ``A w = b`` is checked to a fixed ``1e-7`` absolute tolerance. An empty
37 ``g`` makes the inequality check vacuously true, so it never fires when there
38 are no inequality rows; ``leverage=None`` skips the gross-exposure check.
40 Args:
41 weights: The candidate weight vector.
42 lower: Per-asset lower bounds.
43 upper: Per-asset upper bounds.
44 a: Equality-constraint matrix ``A`` of ``A w = b``.
45 b: Equality-constraint right-hand side ``b``.
46 g: Inequality-constraint matrix ``G`` of ``G w <= h`` (``(p, n)``).
47 h: Inequality-constraint right-hand side ``h`` (length ``p``).
48 leverage: The gross-exposure cap ``||w||_1 <= leverage``, or ``None``.
49 tol: Tolerance for the box, inequality and leverage checks.
51 Raises:
52 ValueError: Naming the first violated constraint.
53 """
54 # (constraint holds?, message if it does not).
55 checks: tuple[tuple[bool, str], ...] = (
56 (bool(np.all(weights >= (lower - tol))), "Weights below lower bounds"), # pragma: no mutate
57 (bool(np.all(weights <= (upper + tol))), "Weights above upper bounds"), # pragma: no mutate
58 (bool(np.allclose(a @ weights, b, atol=1e-7)), "Weights violate the equality constraint A w = b"),
59 (bool(np.all(g @ weights <= h + tol)), "Weights violate the inequality constraint G w <= h"),
60 (
61 leverage is None or bool(np.abs(weights).sum() <= leverage + tol),
62 "Weights violate the leverage constraint ||w||_1 <= leverage",
63 ),
64 )
65 for ok, message in checks:
66 if not ok:
67 raise ValueError(message)
70def well_conditioned(cov: QuadraticForm) -> bool:
71 """Whether every free-block solve along the trace is numerically safe.
73 By Cauchy's interlacing theorem every principal submatrix of the symmetric
74 PSD covariance is at least as well conditioned as the whole matrix --
75 deleting rows/columns cannot decrease the smallest eigenvalue nor increase
76 the largest -- so the reciprocal condition number of any free block is
77 ``>=`` that of the full covariance. Hence if the full covariance clears the
78 singularity floor, no free block encountered along the trace can be
79 singular, and :func:`guard_degeneracy` is provably never triggered. The
80 caller then skips it, paying one conditioning test up front instead of one
81 at every turning point (the latter is a full eigendecomposition of the free
82 block, as costly as the KKT solve, so it otherwise dominates the trace).
84 When the full covariance is itself near-singular (for example a sample
85 covariance from fewer observations than assets) this is ``False`` and the
86 per-step guard runs unchanged, preserving the degeneracy diagnosis exactly.
88 Args:
89 cov: The covariance as a ``QuadraticForm`` backend.
91 Returns:
92 Whether the full covariance clears the singularity floor.
93 """
94 return float(cov.rcond_free(np.arange(cov.n))) >= _RCOND_FLOOR
97def guard_degeneracy(cov: QuadraticForm, lamb: float, free: NDArray[np.bool_]) -> None:
98 """Refuse the turning point when the free-asset block is numerically singular.
100 We distinguish two regimes by the conditioning of the free-asset block.
101 While that block stays numerically full rank its solve is reliable and any
102 box violation is round-off, which :func:`cvxcla._projection.project_feasible`
103 clears. Once the free set grows past the covariance rank the block is
104 numerically singular and its solve is unreliable; whatever weights it produces
105 (feasible or not) cannot be trusted, so we refuse and raise an actionable
106 diagnosis instead of silently returning a possibly-suboptimal frontier.
108 The discriminator is the free block's reciprocal condition number, read
109 from its symmetric eigenvalues. Unlike the magnitude of the box violation,
110 which is the residual of a singular solve and therefore varies with the
111 BLAS/LAPACK build, the conditioning is deterministic and portable, so the
112 completed-vs-declined boundary is the same on every platform.
114 The caller skips this check entirely when the full covariance is well
115 conditioned: by interlacing no free block can then be singular, so the check
116 is provably redundant (see :func:`well_conditioned`).
118 Args:
119 cov: The covariance as a ``QuadraticForm`` backend.
120 lamb: Lambda value of the candidate turning point, used in the message.
121 free: Boolean mask of the free assets at the candidate.
123 Raises:
124 ValueError: With a degeneracy-specific message when the free-asset
125 block is numerically singular (an unreliable solve); otherwise
126 returns without effect.
127 """
128 rcond = cov.rcond_free(np.flatnonzero(free))
129 if rcond < _RCOND_FLOOR:
130 n_free = int(np.count_nonzero(free))
131 msg = (
132 f"Critical Line Algorithm hit a degeneracy at lambda={lamb:.4g} "
133 f"(free-set size {n_free}): the free-asset covariance block is "
134 f"numerically singular (reciprocal condition number {rcond:.2g}), "
135 "so its solve is unreliable and the turning point cannot be "
136 "trusted. The trace was stopped rather than risk silently "
137 "returning a suboptimal frontier. This happens when the free set "
138 "grows past the covariance rank (for example a sample covariance "
139 "from far fewer days than assets). Use a well-conditioned, "
140 "full-rank estimate (ample history), or a FactorCovariance backend "
141 "(diagonal-plus-low-rank), which is positive definite by construction."
142 )
143 raise ValueError(msg)