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

1"""Acceptance checks for a Critical Line Algorithm turning point. 

2 

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

12 

13from __future__ import annotations 

14 

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] 

19 

20from ._kkt import Segment 

21from .errors import DegenerateProblemError, FeasibilityError 

22from .operators import RCOND_FLOOR, QuadraticForm 

23 

24 

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. 

37 

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. 

42 

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. 

53 

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) 

72 

73 

74def well_conditioned(cov: QuadraticForm) -> bool: 

75 """Whether every free-block solve along the trace is numerically safe. 

76 

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

87 

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. 

91 

92 Args: 

93 cov: The covariance as a ``QuadraticForm`` backend. 

94 

95 Returns: 

96 Whether the full covariance clears the singularity floor. 

97 """ 

98 return float(cov.rcond_free(np.arange(cov.n))) >= RCOND_FLOOR 

99 

100 

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

103 

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

113 

114 

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. 

119 

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. 

127 

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. 

133 

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. 

143 

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

147 

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. 

154 

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) 

179 

180 

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. 

193 

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. 

204 

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. 

209 

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

221 

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) 

245 

246 

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. 

259 

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

268 

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. 

279 

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)