Coverage for src/cvxcla/cla.py: 100%

304 statements  

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

1"""Markowitz implementation of the Critical Line Algorithm. 

2 

3This module provides the CLA class, which implements the Critical Line Algorithm 

4as described by Harry Markowitz and colleagues. The algorithm computes the entire 

5efficient frontier by finding all turning points, which are the points where the 

6set of assets at their bounds changes. 

7""" 

8 

9import logging 

10from dataclasses import dataclass, field, replace 

11from functools import cached_property 

12from typing import cast 

13 

14import numpy as np 

15from cvx.linalg import DenseOperator 

16from numpy.typing import NDArray 

17 

18from ._builders import ProblemBuilder 

19from ._checks import check_feasible, check_held_bounds, guard_degeneracy, well_conditioned 

20from ._events import roundoff_events_at_zero, segment_events 

21from ._kkt import Segment, critical_segment 

22from ._leverage import LeverageLift, SignedLift, mask_leg_events, tighten_at_minimum_gross 

23from ._projection import project_feasible 

24from .errors import InfeasibleProblemError 

25from .first import classify_vertex, first_turning_point, reject_degenerate_vertex, vertex_partition 

26from .operators import DenseCovariance, QuadraticForm 

27from .pathtracer import InequalityConstrained, trace 

28from .types import Frontier, FrontierPoint, TurningPoint 

29 

30# Multiplier intercepts within this many ulps per dimension of the terms that form them are zero. 

31_GAMMA_NOISE_ULPS = 100 

32 

33 

34def _independent_equalities( 

35 a: NDArray[np.float64], b: NDArray[np.float64] 

36) -> tuple[NDArray[np.float64], NDArray[np.float64]]: 

37 """Drop the rows of ``A w = b`` that are linear combinations of earlier rows. 

38 

39 A redundant row leaves the feasible set unchanged but makes every Schur 

40 complement of the reduced KKT system singular. Rows are taken in order and kept 

41 while they raise the rank; each dropped row must then agree with the kept ones on 

42 the right-hand side, or the system is inconsistent. 

43 

44 Args: 

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

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

47 

48 Returns: 

49 The independent rows ``(a, b)``; the input itself when none is redundant. 

50 

51 Raises: 

52 InfeasibleProblemError: If a dependent row contradicts the rows it depends on. 

53 """ 

54 kept: list[int] = [] 

55 for i in range(a.shape[0]): 

56 if int(np.linalg.matrix_rank(a[[*kept, i]])) > len(kept): 

57 kept.append(i) 

58 if len(kept) == a.shape[0]: 

59 return a, b 

60 dropped = [i for i in range(a.shape[0]) if i not in kept] 

61 coef = np.linalg.lstsq(a[kept].T, a[dropped].T, rcond=None)[0] 

62 scale = 1.0 + float(np.max(np.abs(b), initial=0.0)) 

63 if np.max(np.abs(coef.T @ b[kept] - b[dropped])) > 1e-9 * scale: # pragma: no mutate 

64 msg = "The equality constraints are inconsistent: a dependent row of A w = b contradicts the others" 

65 raise InfeasibleProblemError(msg) 

66 return a[kept], b[kept] 

67 

68 

69def _owned(value: NDArray[np.float64]) -> NDArray[np.float64]: 

70 """Return a read-only float copy of ``value``, owned by the problem. 

71 

72 The frontier is traced in the constructor, so an input changed afterwards would 

73 leave the stored turning points out of step with the arrays the object exposes 

74 (``frontier`` evaluates returns and variances from them). Copying decouples the 

75 object from the caller's arrays, and the read-only flag keeps its own copy fixed. 

76 

77 Args: 

78 value: An array-like input (``mean``, a bound, a constraint, a dense covariance). 

79 

80 Returns: 

81 A new, non-writeable ``float64`` array with the same shape and values. 

82 """ 

83 owned = np.array(value, dtype=np.float64, copy=True) 

84 owned.setflags(write=False) 

85 return owned 

86 

87 

88def _own_inputs(cla: "CLA") -> None: 

89 """Replace every array input of ``cla`` by a read-only copy (see :func:`_owned`). 

90 

91 A ``QuadraticForm`` backend is passed through unchanged: it may hold structured 

92 or large data, and keeping it fixed is the backend's responsibility. 

93 

94 Args: 

95 cla: The problem being constructed. 

96 """ 

97 for name in ("mean", "lower_bounds", "upper_bounds", "a", "b"): 

98 object.__setattr__(cla, name, _owned(getattr(cla, name))) # frozen dataclass 

99 for name in ("g", "h", "q"): 

100 if getattr(cla, name) is not None: 

101 object.__setattr__(cla, name, _owned(getattr(cla, name))) 

102 if not isinstance(cla.covariance, QuadraticForm): 

103 object.__setattr__(cla, "covariance", _owned(cla.covariance)) 

104 

105 

106def _check_finite_inputs(cla: "CLA") -> None: 

107 """Refuse non-finite data before anything is traced. 

108 

109 ``mean``, ``a``, ``b``, ``g``, ``h`` and ``q`` must be finite, and the bounds must not be 

110 NaN; an infinite bound is allowed (an unbounded box, which the linear program of 

111 the first vertex handles). A dense covariance is checked when it is wrapped (see 

112 :func:`cvxcla.operators.dense_covariance`); a user-supplied backend is responsible 

113 for its own data. Without this check a NaN in ``mean`` traced a meaningless 

114 frontier without complaint and an infinite covariance entry failed deep inside 

115 the first solve. 

116 

117 Args: 

118 cla: The problem being constructed. 

119 

120 Raises: 

121 ValueError: Naming the first offending input. 

122 """ 

123 inputs = [ 

124 ("mean", cla.mean), 

125 ("a", cla.a), 

126 ("b", cla.b), 

127 ("g", cla.g_matrix), 

128 ("h", cla.h_vector), 

129 ("q", cla.q_vector), 

130 ] 

131 for name, value in inputs: 

132 if not np.all(np.isfinite(np.asarray(value, dtype=np.float64))): 

133 msg = f"{name} must be finite (no NaN or infinite entries)" 

134 raise ValueError(msg) 

135 for name, value in [("lower_bounds", cla.lower_bounds), ("upper_bounds", cla.upper_bounds)]: 

136 if np.any(np.isnan(np.asarray(value, dtype=np.float64))): 

137 msg = f"{name} must not contain NaN (infinite bounds are allowed)" 

138 raise ValueError(msg) 

139 

140 

141def _check_shapes(cla: "CLA") -> None: 

142 """Refuse mis-shaped inequality and benchmark data. 

143 

144 Args: 

145 cla: The problem being constructed. 

146 

147 Raises: 

148 ValueError: If ``g`` does not have ``n`` columns, ``h`` does not match the rows 

149 of ``g``, or ``q`` does not have ``n`` entries. 

150 """ 

151 n = cla.dimension 

152 if cla.g_matrix.shape[1] != n: 

153 msg = f"g must have {n} columns, got shape {cla.g_matrix.shape}" 

154 raise ValueError(msg) 

155 if cla.h_vector.shape[0] != cla.g_matrix.shape[0]: 

156 msg = f"h must have {cla.g_matrix.shape[0]} entries, got {cla.h_vector.shape[0]}" 

157 raise ValueError(msg) 

158 if cla.q_vector.shape != (n,): 

159 msg = f"q must have {n} entries, got shape {cla.q_vector.shape}" 

160 raise ValueError(msg) 

161 

162 

163def _check_options(cla: "CLA") -> None: 

164 """Refuse an invalid ``stop`` or ``leverage``, or the two combined. 

165 

166 Args: 

167 cla: The problem being constructed. 

168 

169 Raises: 

170 ValueError: If ``stop`` is not an asset index, ``leverage`` is not a positive 

171 finite number, or ``stop`` is combined with ``leverage``. 

172 """ 

173 n = cla.dimension 

174 if cla.stop is not None and not 0 <= cla.stop < n: 

175 msg = f"stop must be an asset index in [0, {n}), got {cla.stop}" 

176 raise ValueError(msg) 

177 if cla.leverage is None: 

178 return 

179 if not (np.isfinite(cla.leverage) and cla.leverage > 0): 

180 msg = f"leverage must be a positive finite number, got {cla.leverage}" 

181 raise ValueError(msg) 

182 if cla.stop is not None: 

183 msg = "stop is not supported together with leverage" 

184 raise ValueError(msg) 

185 

186 

187class _FaceShift(QuadraticForm): 

188 """The form ``base + c u u^T``, which agrees with ``base`` on ``u^T w = const`` up to a constant. 

189 

190 On a face of constant return the shift adds curvature along every direction that changes 

191 the return, so a free block that is singular only along such a direction (both legs of a 

192 split coefficient, ``e_j+ + e_j-``, under a constant ``-1`` return) is not singular here. 

193 Products go through ``base``; a free-block solve forms the free block, which is small. 

194 

195 Attributes: 

196 base: The unshifted form. 

197 u: The direction of the shift (the returns). 

198 c: Its weight. 

199 """ 

200 

201 def __init__(self, base: QuadraticForm, u: NDArray[np.float64], c: float) -> None: 

202 """Wrap ``base`` with the shift ``c u u^T``.""" 

203 self.base = base 

204 self.u = u 

205 self.c = c 

206 

207 @property 

208 def n(self) -> int: 

209 """Dimension of the form.""" 

210 return int(self.base.n) 

211 

212 def matvec(self, x: NDArray[np.float64]) -> NDArray[np.float64]: 

213 """Return ``(base + c u u^T) x``.""" 

214 return self.block_matvec(np.arange(self.n), np.arange(self.n), x) 

215 

216 def block_matvec(self, rows: object, cols: object, v: NDArray[np.float64]) -> NDArray[np.float64]: 

217 """Return the ``(rows, cols)`` block of the shifted form applied to ``v``.""" 

218 rows = np.asarray(rows, dtype=np.intp) 

219 cols = np.asarray(cols, dtype=np.intp) 

220 v = np.asarray(v, dtype=np.float64) 

221 shift = np.multiply.outer(self.c * self.u[rows], self.u[cols] @ v) 

222 return np.asarray(self.base.block_matvec(rows, cols, v), dtype=np.float64) + shift 

223 

224 def _block(self, free: object) -> DenseOperator: 

225 """The free block as a dense form.""" 

226 index = np.asarray(free, dtype=np.intp) 

227 return DenseOperator(self.block_matvec(index, index, np.eye(index.size))) 

228 

229 def solve_free(self, free: object, rhs: NDArray[np.float64]) -> NDArray[np.float64]: 

230 """Solve on the free block.""" 

231 index = np.asarray(free, dtype=np.intp) 

232 return np.asarray(self._block(index).solve_free(np.arange(index.size), rhs), dtype=np.float64) 

233 

234 def rcond_free(self, free: object) -> float: 

235 """Reciprocal condition number of the free block.""" 

236 index = np.asarray(free, dtype=np.intp) 

237 return float(self._block(index).rcond_free(np.arange(index.size))) 

238 

239 

240@dataclass(frozen=True) 

241class CLA(InequalityConstrained): 

242 """Critical Line Algorithm implementation based on Markowitz's approach. 

243 

244 This class implements the Critical Line Algorithm as described by Harry Markowitz 

245 and colleagues. It computes the entire efficient frontier by finding all turning 

246 points, which are the points where the set of assets at their bounds changes. 

247 

248 The algorithm starts with the first turning point (the portfolio with the highest 

249 expected return) and then iteratively computes the next turning point with a lower 

250 expected return until it reaches the minimum variance portfolio. 

251 

252 Attributes: 

253 mean: Vector of expected returns for each asset. 

254 covariance: Covariance matrix of asset returns, either as a plain 

255 ``numpy`` array or as a ``CovarianceOperator`` backend 

256 (see ``cvxcla.operators``). 

257 lower_bounds: Vector of lower bounds for asset weights. 

258 upper_bounds: Vector of upper bounds for asset weights. 

259 a: Equality-constraint matrix ``A`` of ``A w = b`` (``m x n``). The 

260 canonical case is the single all-ones budget row (``sum(w) = b``), 

261 but an arbitrary equality system is supported: weighted single rows 

262 and ``m > 1`` rows (e.g. budget plus sector- or factor-neutrality). 

263 The all-ones budget (any right-hand side, including ``0`` for 

264 dollar-neutral) uses the greedy first vertex of 

265 :func:`cvxcla.first.init_algo`; a general ``A`` uses the 

266 linear-programming first vertex of 

267 :func:`cvxcla.first.first_vertex_lp`. 

268 b: Equality-constraint right-hand side ``b`` (length ``m``); ``[1]`` for 

269 the fully-invested budget, ``[0]`` for dollar-neutral, and so on. 

270 g: Optional inequality-constraint matrix ``G`` of ``G w <= h`` 

271 (``p x n``), e.g. a group- or sector-exposure cap. ``None`` (the 

272 default) means no inequality rows, recovering the equality-only 

273 problem exactly. A ``>=`` constraint is expressed by negating both 

274 ``g`` and ``h``. Each *active* row (held at equality ``g_i w = h_i``) 

275 enters the reduced KKT system as an extra equality row, so the 

276 covariance is still touched only through the ``QuadraticForm`` 

277 interface; box bounds remain a separate per-variable active set. 

278 h: Optional inequality-constraint right-hand side ``h`` (length ``p``). 

279 turning_points: List of turning points on the efficient frontier. 

280 tol: Tolerance for numerical calculations. 

281 logger: Logger instance for logging information and errors. 

282 leverage: Optional cap ``c`` on the gross exposure, ``||w||_1 <= c``. 

283 ``None`` (the default) means no cap. The 1-norm is traced exactly by 

284 splitting every asset whose box straddles zero into a long and a short 

285 leg (see :mod:`cvxcla._leverage`); the turning points are reported in 

286 the original asset weights, and ``active_ineq`` covers the rows of 

287 ``g`` only. 

288 stop: Optional asset index ``j``. The trace ends at the turning point where 

289 asset ``j`` leaves its bound, which is recorded (and is the last one); 

290 no ``lambda = 0`` endpoint follows. That event wins a tie with any other 

291 event at the same ``lambda``. With a zero-variance, zero-return cash 

292 asset in a fully invested problem, cash leaving zero is where the budget 

293 goes slack, and the free block below it can be singular. ``None`` (the 

294 default) traces to ``lambda = 0``. Not supported together with 

295 ``leverage``. 

296 q: Optional linear benchmark term (length ``n``). The traced problem is 

297 then ``min w^T Sigma w / 2 - (q + lam mean)^T w`` subject to the same 

298 constraints, from ``lambda = inf`` to ``0``. With ``q = Sigma w_bar`` the 

299 objective is, up to a constant, the tracking variance against a 

300 benchmark portfolio ``w_bar`` less ``lam mean^T w`` (the active-risk 

301 frontier); unlike a manual shift to ``w - w_bar`` it needs no solve with 

302 ``Sigma`` and works when ``q`` is outside its range. The turning points 

303 are reported in ``w``. ``q`` does not change the maximum-return vertex, 

304 only the path below it. ``None`` (the default) means ``q = 0``. 

305 

306 The array inputs (and a dense ``covariance``) are copied into read-only 

307 ``float64`` arrays when the object is built, so changing the caller's arrays 

308 afterwards does not affect it. A ``QuadraticForm`` backend is used as given. 

309 

310 """ 

311 

312 mean: NDArray[np.float64] 

313 covariance: NDArray[np.float64] | QuadraticForm 

314 lower_bounds: NDArray[np.float64] 

315 upper_bounds: NDArray[np.float64] 

316 a: NDArray[np.float64] 

317 b: NDArray[np.float64] 

318 g: NDArray[np.float64] | None = None 

319 h: NDArray[np.float64] | None = None 

320 turning_points: list[TurningPoint] = field(default_factory=list) 

321 tol: float = 1e-5 # pragma: no mutate 

322 logger: logging.Logger = field(default_factory=lambda: logging.getLogger(__name__)) 

323 leverage: float | None = None 

324 stop: int | None = None 

325 q: NDArray[np.float64] | None = None 

326 

327 @classmethod 

328 def problem( 

329 cls, mean: NDArray[np.float64], covariance: NDArray[np.float64] | QuadraticForm 

330 ) -> "ProblemBuilder[CLA]": 

331 """Start a fluent :class:`cvxcla._builders.ProblemBuilder` for this problem. 

332 

333 A readability convenience over the explicit constructor: chain 

334 ``.long_only()``/``.budget()``/``.equality()``/``.inequality()`` and finish 

335 with ``.trace()``. The builder maps one-to-one onto the constructor 

336 arguments and adds no modelling power. 

337 

338 ``cls`` is handed to the builder as the class it should construct, which is 

339 what lets the builder live in a leaf module that never imports this one. 

340 

341 Args: 

342 mean: Vector of expected returns of length ``n``. 

343 covariance: Covariance matrix or ``QuadraticForm`` backend. 

344 

345 Returns: 

346 A ``ProblemBuilder`` ready to accept constraints, whose ``.trace()`` 

347 returns a solved ``CLA``. 

348 """ 

349 return ProblemBuilder(mean, covariance, solver=cls) 

350 

351 @cached_property 

352 def covariance_operator(self) -> QuadraticForm: 

353 """Return the covariance as a ``QuadraticForm`` backend. 

354 

355 A plain ``numpy`` covariance matrix is wrapped in ``DenseCovariance``; 

356 an object already implementing the protocol is passed through. This is 

357 the single point where the input form is normalised. 

358 """ 

359 if isinstance(self.covariance, QuadraticForm): 

360 return self.covariance 

361 return DenseCovariance(self.covariance) 

362 

363 @property 

364 def dimension(self) -> int: 

365 """Number of assets ``n`` (the problem dimension for the path tracer).""" 

366 return len(self.mean) 

367 

368 @cached_property 

369 def _free_blocks_well_conditioned(self) -> bool: 

370 """Whether every free-block solve is numerically safe (see :func:`cvxcla._checks.well_conditioned`). 

371 

372 Decided once, up front: when ``True`` the per-turning-point guard in 

373 :meth:`_emit` is provably redundant and skipped. 

374 """ 

375 return well_conditioned(self.covariance_operator) 

376 

377 def __post_init__(self) -> None: 

378 """Initialize the CLA object and compute the efficient frontier. 

379 

380 This method is automatically called after initialization. It computes 

381 the entire efficient frontier by finding all turning points, starting 

382 from the first turning point (highest expected return) and iteratively 

383 computing the next turning point with a lower expected return until 

384 it reaches the minimum variance portfolio. 

385 

386 The actual walk is driven by the generic ``cvxcla.pathtracer.trace`` 

387 loop; this class supplies the portfolio-specific hooks (``begin``, 

388 ``segment``, ``event_matrix``, ``step``, ``finish``) it calls. 

389 

390 The reduced KKT system at each turning point is solved by block 

391 elimination: a single multi-RHS solve against the free covariance block 

392 (via the covariance backend), covering the constraint columns and the 

393 alpha and beta systems together so ``Sigma_FF`` is factorised once, then a 

394 small Schur-complement solve ``A_F @ Sigma_FF^{-1} @ A_F.T`` over the 

395 equality (and active inequality) rows. The covariance only enters through 

396 the ``QuadraticForm`` interface, so structured backends (e.g. 

397 ``FactorCovariance``) never materialise an n x n matrix. 

398 

399 The array inputs are first copied into read-only arrays owned by the object 

400 (see :func:`_own_inputs`). Redundant equality rows (a row in the span of the 

401 others, such as a repeated budget) are then dropped, keeping the earliest independent rows; 

402 ``a`` and ``b`` then hold the reduced system. 

403 

404 Raises: 

405 ValueError: If the inequality matrix ``g`` and vector ``h`` have 

406 mismatched or wrong shapes, ``leverage`` is not a positive finite 

407 number, ``stop`` is not an asset index or is combined with 

408 ``leverage``, ``q`` does not have ``n`` entries, or an input is not 

409 finite (see :func:`_check_finite_inputs`). 

410 InfeasibleProblemError: If the constraints admit no portfolio, including 

411 an equality system whose dependent rows contradict the others. 

412 DegenerateProblemError: If the problem is feasible but outside the 

413 supported domain (see :mod:`cvxcla.errors`). 

414 NumericalError: If the trace breaks down numerically. 

415 

416 """ 

417 _own_inputs(self) 

418 _check_finite_inputs(self) 

419 _check_shapes(self) 

420 _check_options(self) 

421 a, b = _independent_equalities(np.atleast_2d(np.asarray(self.a, dtype=np.float64)), np.atleast_1d(self.b)) 

422 a.setflags(write=False) 

423 b.setflags(write=False) 

424 object.__setattr__(self, "a", a) # frozen dataclass: normalise once, before tracing 

425 object.__setattr__(self, "b", b) 

426 if self.leverage is None: 

427 trace(self) 

428 else: 

429 self._trace_leveraged(self.leverage) 

430 self._restore_mean_units() 

431 

432 @cached_property 

433 def _mean_shift(self) -> tuple[float, float, NDArray[np.float64]]: 

434 """Return ``(c, d, r)``: the trace runs on ``(mean - c) / d`` (see :attr:`_traced_mean`). 

435 

436 When ``1`` lies in the row space of ``A`` (``A^T r = 1``, e.g. a budget row 

437 ``1'w = b``), ``1'w`` is the same for every feasible portfolio, so subtracting 

438 ``c`` from every return changes the objective by a constant only, and dividing 

439 ``mean`` by ``d`` relabels ``lambda`` as ``lambda d``. Centring on the midpoint 

440 of ``mean`` and scaling to unit half-range makes the event and held-bound 

441 tolerances, which are absolute in ``mean``, see the spread of the returns rather 

442 than their level: returns ``0.5 +- 1e-10`` trace like ``+-1`` (issue #967). 

443 Without such a row, or with all returns equal, it is the identity ``(0, 1, 0)``. 

444 """ 

445 identity = 0.0, 1.0, np.zeros(self.a.shape[0]) 

446 ones = np.ones(self.dimension) 

447 r = np.asarray(np.linalg.lstsq(self.a.T, ones, rcond=None)[0], dtype=np.float64) 

448 if not np.allclose(self.a.T @ r, ones, rtol=0.0, atol=1e-12): # pragma: no mutate 

449 return identity 

450 hi, lo = float(np.max(self.mean)), float(np.min(self.mean)) 

451 if hi == lo: 

452 return identity 

453 return (hi + lo) / 2, (hi - lo) / 2, r 

454 

455 @cached_property 

456 def _traced_mean(self) -> NDArray[np.float64]: 

457 """The returns the trace runs on: ``(mean - c) / d`` (see :attr:`_mean_shift`).""" 

458 c, d, _ = self._mean_shift 

459 if c == 0.0 and d == 1.0: 

460 return self.mean 

461 return (self.mean - c) / d 

462 

463 def _restore_mean_units(self) -> None: 

464 """Map the turning points traced on :attr:`_traced_mean` back to ``mean``. 

465 

466 With ``lambda' (mean - c) / d = lambda (mean - c 1)`` the original problem has 

467 ``lambda = lambda' / d``, ``eta = eta'`` and ``nu = nu' + lambda c r``; at 

468 ``lambda = inf`` the recorded slopes become ``d nu' + c r`` and ``d eta'``. 

469 The weights are unchanged. 

470 """ 

471 c, d, r = self._mean_shift 

472 if c == 0.0 and d == 1.0: 

473 return 

474 restored = [] 

475 for tp in self.turning_points: 

476 if tp.lamb == np.inf: 

477 restored.append(replace(tp, nu=d * tp.nu + c * r, eta=d * tp.eta)) 

478 else: 

479 lamb = tp.lamb / d 

480 restored.append(replace(tp, lamb=lamb, nu=tp.nu + lamb * c * r)) 

481 self.turning_points[:] = restored 

482 

483 def _trace_leveraged(self, leverage: float) -> None: 

484 """Trace the frontier under ``||w||_1 <= leverage`` via the signed lift. 

485 

486 Builds the lifted problem over the long/short legs -- the covariance as a 

487 :class:`cvxcla._leverage.SignedLift` of this problem's backend, every 

488 constraint matrix mapped through ``w = P x``, and the gross-exposure row 

489 ``sum(x) <= leverage`` appended to ``G`` -- traces it with 

490 :class:`_LeveragedCLA`, and maps its turning points back to asset weights. 

491 A cap at the smallest feasible gross exposure is first resolved into 

492 tightened bounds (see :func:`cvxcla._leverage.tighten_at_minimum_gross`), 

493 which keeps the maximum-return vertex non-degenerate. 

494 The objective ``x.T P.T Sigma P x / 2 - lam mean.T P x`` is the original one 

495 in ``w = P x``, so the lifted ``lambda`` is the original ``lambda``. 

496 

497 Args: 

498 leverage: The gross-exposure cap ``c``. 

499 """ 

500 lower, upper, keep_cap = tighten_at_minimum_gross( 

501 self.lower_bounds, self.upper_bounds, self.a, self.b, self.g_matrix, self.h_vector, leverage, self.tol 

502 ) 

503 lift = LeverageLift.from_bounds(lower, upper) 

504 g, h = lift.with_cap(self.g_matrix, self.h_vector, leverage if keep_cap else None) 

505 lifted = _LeveragedCLA( 

506 mean=self._traced_mean[lift.asset] * lift.sign, 

507 q=self.q_vector[lift.asset] * lift.sign, 

508 covariance=SignedLift(self.covariance_operator, lift.asset, lift.sign), 

509 lower_bounds=lift.lower, 

510 upper_bounds=lift.upper, 

511 a=lift.columns(self.a), 

512 b=self.b, 

513 g=g, 

514 h=h, 

515 tol=self.tol, 

516 logger=self.logger, 

517 lift=lift, 

518 ) 

519 p = self.g_matrix.shape[0] 

520 for tp in lifted.turning_points: 

521 self._append(lift.to_turning_point(tp, self.dimension, p)) 

522 

523 def begin(self) -> tuple[float, TurningPoint]: 

524 """Record the first turning point and start the trace at ``lambda = inf``. 

525 

526 Returns: 

527 ``(inf, first_turning_point)``: the starting lambda bound and the 

528 initial state for the path tracer. 

529 """ 

530 first = self._first_turning_point() 

531 if self._tied_start(first): 

532 first = self._face_minimiser(first) 

533 self._append(first) 

534 return np.inf, first 

535 

536 def _tied_start(self, first: TurningPoint) -> bool: 

537 """Whether ``first`` holds a tied asset on a bound it should leave at ``lambda = inf``. 

538 

539 An asset whose multiplier has no slope in ``lambda`` (``delta = 0``: its return ties 

540 with the free assets') and the wrong sign in its intercept ``gamma`` should have left 

541 its bound before the trace starts. The maximum-return vertex is then not the limit of 

542 the path at ``lambda = inf``: returns tie on a whole face of the linear program, and 

543 the limit is the point of that face the quadratic term picks (see 

544 :meth:`_face_minimiser`). 

545 """ 

546 segment = critical_segment( 

547 self.covariance_operator, 

548 self._traced_mean, 

549 self.a, 

550 self.b, 

551 self.g_matrix, 

552 self.h_vector, 

553 self.lower_bounds, 

554 self.upper_bounds, 

555 self.tol, 

556 first, 

557 self.q_vector, 

558 self._free_blocks_well_conditioned, 

559 ) 

560 lam_scale, mu_scale = self._scales 

561 root = float(np.sqrt(np.finfo(np.float64).eps)) 

562 floor = root * max(lam_scale * mu_scale, float(np.max(np.abs(segment.gamma), initial=0.0))) 

563 tied = np.abs(segment.delta) <= root * mu_scale 

564 wrong = (segment.at_lower & (segment.gamma < -floor)) | (segment.at_upper & (segment.gamma > floor)) 

565 return bool(np.any(tied & wrong)) 

566 

567 def _face_minimiser(self, first: TurningPoint) -> TurningPoint: 

568 """The limit of the path at ``lambda = inf`` when the maximum return is attained on a face. 

569 

570 For large ``lambda`` the program ``min w^T Sigma w / 2 - (q + lambda mean)^T w`` is 

571 solved, to leading order, by any maximum-return point, and to the next order by the one 

572 that minimises ``w^T Sigma w / 2 - q^T w`` over the face ``mean^T w = mean^T first``. That 

573 point is the ``lambda = 0`` end of a CLA on the face, traced under a generic tilt so its 

574 own start is a unique vertex. On the face ``mean^T w`` is constant, so a covariance 

575 that is singular there is first shifted by ``c mean mean^T`` (see :class:`_FaceShift`), 

576 which changes the face's objective by a constant only. The free set here is the assets strictly inside their 

577 box at that point, not the face trace's own free set: there the row ``mean^T w`` can 

578 pin an asset that sits on a bound, which nothing pins here. On the interior assets the 

579 returns are a combination of the active rows (moving them along the face keeps the 

580 maximum), so the first segment holds the point still until an asset with a nonzero 

581 slope leaves its bound. The active rows are the face trace's. 

582 """ 

583 mean = self._traced_mean 

584 tilt = np.random.default_rng(0).standard_normal(self.dimension) * self._scales[1] 

585 covariance = self.covariance_operator 

586 if not self._free_blocks_well_conditioned: 

587 lam_scale, mu_scale = self._scales 

588 covariance = _FaceShift(covariance, mean, lam_scale / mu_scale) 

589 face = CLA( 

590 mean=tilt, 

591 covariance=covariance, 

592 lower_bounds=self.lower_bounds, 

593 upper_bounds=self.upper_bounds, 

594 a=np.vstack([self.a, mean]), 

595 b=np.append(self.b, float(mean @ first.weights)), 

596 g=self.g, 

597 h=self.h, 

598 q=self.q_vector, 

599 tol=self.tol, 

600 logger=self.logger, 

601 ) 

602 end = face.turning_points[-1] 

603 free = (end.weights > self.lower_bounds + self.tol) & (end.weights < self.upper_bounds - self.tol) 

604 # Where the point sits on a vertex, complete the basis from the face trace's free set. 

605 rows = np.vstack([self.a, self.g_matrix[end.active_ineq]]) 

606 freed, _ = vertex_partition(rows, free, end.free & ~free, np.zeros(rows.shape[0], dtype=bool), -mean) 

607 free = free | freed 

608 reject_degenerate_vertex(self.a, self.g_matrix, free, end.active_ineq) 

609 return TurningPoint(free=free, weights=end.weights, active_ineq=end.active_ineq) 

610 

611 def segment(self, state: TurningPoint) -> Segment: 

612 """Solve the reduced KKT system for the critical-line segment at ``state``. 

613 

614 The first segment also completes the first turning point, recorded before 

615 any solve: at ``lambda = inf`` it gets the multiplier slopes ``nu_beta`` and 

616 ``eta_beta`` (see :class:`cvxcla.types.TurningPoint`). 

617 """ 

618 segment = critical_segment( 

619 self.covariance_operator, 

620 self._traced_mean, 

621 self.a, 

622 self.b, 

623 self.g_matrix, 

624 self.h_vector, 

625 self.lower_bounds, 

626 self.upper_bounds, 

627 self.tol, 

628 state, 

629 self.q_vector, 

630 self._free_blocks_well_conditioned, 

631 ) 

632 if state.lamb == np.inf: 

633 self.turning_points[0] = replace(state, nu=segment.nu_beta, eta=segment.eta_beta) 

634 return segment 

635 

636 @cached_property 

637 def q_vector(self) -> NDArray[np.float64]: 

638 """The linear term ``q`` as a length-``n`` float array (zeros if ``q`` is ``None``).""" 

639 if self.q is None: 

640 return np.zeros(self.dimension) 

641 return np.atleast_1d(np.asarray(self.q, dtype=np.float64)) 

642 

643 @cached_property 

644 def _scales(self) -> tuple[float, float]: 

645 """Return ``(lambda_scale, mu_scale)``, the natural units of the problem. 

646 

647 ``mu_scale`` is ``max |mu|`` and the covariance scale is ``max |Sigma v| / n`` 

648 over two probes ``v``: the equal-weight portfolio and a fixed pseudo-random 

649 sign vector. Products are available for any backend. The second probe guards 

650 against a covariance that cancels along ``1``: splitting coefficients into 

651 long and short legs (``S^T G S`` with ``S = [I, -I]``) gives ``Sigma 1 = 0`` 

652 up to round-off, and a round-off scale would set every weight-slope floor 

653 astronomically high and suppress the move-to-bound events. For a covariance 

654 with mostly positive correlations ``|Sigma 1|`` dominates and the scale is 

655 unchanged. Their ratio is the scale of ``lambda``, at which risk and return 

656 balance. Both are positively homogeneous: rescaling ``mu`` by ``c`` and 

657 ``Sigma`` by ``s`` rescales them by ``c`` and ``s / c``, which is what makes 

658 the event tests invariant under a change of units. A zero scale (``mu = 0`` 

659 or ``Sigma = 0``) falls back to ``1``. 

660 """ 

661 n = self.dimension 

662 mu_scale = float(np.max(np.abs(self._traced_mean))) if n else 0.0 

663 probes = np.column_stack([np.ones(n), np.random.default_rng(0).choice([-1.0, 1.0], size=n)]) 

664 cov_scale = float(np.max(np.abs(self.covariance_operator.matvec(probes)))) / n if n else 0.0 

665 mu_scale = mu_scale if mu_scale > 0 else 1.0 

666 cov_scale = cov_scale if cov_scale > 0 else 1.0 

667 return cov_scale / mu_scale, mu_scale 

668 

669 @property 

670 def lambda_scale(self) -> float: 

671 """The natural scale of ``lambda`` (covariance scale over return scale). 

672 

673 The path tracer takes its event-ordering window relative to this scale near 

674 ``lambda = 0`` (see :func:`cvxcla.pathtracer.select_next_event`). 

675 """ 

676 return self._scales[0] 

677 

678 def event_matrix(self, state: TurningPoint, segment: Segment) -> NDArray[np.float64]: # noqa: ARG002 

679 """Return the ``(n + p, 4)`` event matrix for ``segment`` (see :func:`cvxcla._events.segment_events`). 

680 

681 The first ``n`` rows are box events and the trailing ``p`` rows are 

682 inequality-row events; ``step`` decodes a row index ``>= n`` as a row 

683 event. ``state`` is part of the uniform ``ParametricProblem`` signature; 

684 the CLA does not need it because ``segment`` already bundles the masks. 

685 """ 

686 lam_scale, mu_scale = self._scales 

687 events = segment_events( 

688 segment, self.lower_bounds, self.upper_bounds, self.g_matrix, self.h_vector, lam_scale, mu_scale 

689 ) 

690 return roundoff_events_at_zero(events, segment.gamma, self._gamma_noise(segment)) 

691 

692 def _gamma_noise(self, segment: Segment) -> NDArray[np.float64]: 

693 """The round-off level of each multiplier intercept ``gamma``. 

694 

695 ``gamma = Sigma r_alpha + C^T nu_alpha - q`` is a sum of terms that can cancel: 

696 when the fit at ``lambda = 0`` makes every gradient vanish (a LASSO with more 

697 predictors than observations interpolates, issue #957) the intercepts are pure 

698 round-off of terms of size ``|q|``, and their roots scatter around zero on 

699 either side. Measured against those terms with the inner-product bound 

700 ``n eps``, such an intercept is zero. A genuinely small one is not: an 

701 ill-conditioned covariance has intercepts as small as its variances, but they 

702 are not the residue of a cancellation (issue #954). 

703 """ 

704 rows = np.vstack([self.a, self.g_matrix[segment.active_ineq]]) 

705 nu = np.concatenate([segment.nu_alpha, segment.eta_alpha[segment.active_ineq]]) 

706 sigma_w = np.asarray(self.covariance_operator.matvec(segment.r_alpha), dtype=np.float64) 

707 terms = np.abs(sigma_w) + np.abs(rows.T @ nu) + np.abs(self.q_vector) 

708 noise: NDArray[np.float64] = _GAMMA_NOISE_ULPS * self.dimension * float(np.finfo(np.float64).eps) * terms 

709 return noise 

710 

711 def ends_trace(self, sec: int, direction: int) -> bool: 

712 """Whether the event ``(sec, direction)`` ends the trace: asset ``stop`` leaving its bound.""" 

713 return sec == self.stop and direction >= 2 

714 

715 def step(self, state: TurningPoint, segment: Segment, sec: int, direction: int, lam: float) -> TurningPoint: 

716 """Emit the turning point at ``lam`` after flipping the activity at ``sec``. 

717 

718 ``sec < n`` is a box event on asset ``sec``: a "leaves a bound" event 

719 (``direction`` in {2, 3}) makes it free, a "moves to a bound" event 

720 (``direction`` in {0, 1}) blocks it. ``sec >= n`` is an inequality-row 

721 event on row ``sec - n``: ``direction == 0`` activates the row (its slack 

722 reached zero), ``direction == 1`` releases it (its multiplier reached 

723 zero). The weight vector is continuous across either event. 

724 

725 When the event ends the trace (see :meth:`ends_trace`), the turning point's 

726 weights come from the segment above it and the free block below it is never 

727 solved, so its degeneracy guard is skipped. 

728 """ 

729 n = self.dimension 

730 free = state.free 

731 active_ineq = state.active_ineq 

732 self._check_held_bounds(segment, lam, sec if sec < n else -1) 

733 if sec < n: 

734 free = free.copy() 

735 free[sec] = direction >= 2 

736 else: 

737 active_ineq = active_ineq.copy() 

738 active_ineq[sec - n] = direction == 0 

739 self._emit( 

740 lam, 

741 segment.r_alpha + lam * segment.r_beta, 

742 free, 

743 active_ineq, 

744 segment.nu_alpha + lam * segment.nu_beta, 

745 segment.eta_alpha + lam * segment.eta_beta, 

746 guard=not self.ends_trace(sec, direction), 

747 ) 

748 return self.turning_points[-1] 

749 

750 def finish(self, state: TurningPoint, segment: Segment) -> None: 

751 """Emit the minimum-variance endpoint at ``lambda = 0``.""" 

752 self._check_held_bounds(segment, 0.0, -1) 

753 self._emit(0.0, segment.r_alpha, state.free, state.active_ineq, segment.nu_alpha, segment.eta_alpha) 

754 

755 def _check_held_bounds(self, segment: Segment, lam: float, event: int) -> None: 

756 """Check the segment's held bounds where it ends (see :func:`cvxcla._checks.check_held_bounds`). 

757 

758 A segment that ends at ``lambda = inf`` (an event at the vertex itself) is 

759 empty and holds nothing, so it is not checked. The multipliers are 

760 ``Sigma w - q - lambda mu``, so their round-off scales with ``q`` as well as with 

761 ``Sigma w``: near ``lambda = 0`` the first two nearly cancel, and the probe 

762 estimate of ``Sigma``'s scale alone can be far smaller than either of them. 

763 """ 

764 if np.isfinite(lam): 

765 lam_scale, mu_scale = self._scales 

766 rows = np.vstack([self.a, self.g_matrix[segment.active_ineq]]) 

767 check_held_bounds( 

768 segment, 

769 lam, 

770 event, 

771 rows, 

772 self.lower_bounds, 

773 self.upper_bounds, 

774 self.tol, 

775 mu_scale, 

776 max(lam_scale * mu_scale, float(np.max(np.abs(self.q_vector), initial=0.0))), 

777 ) 

778 

779 def __len__(self) -> int: 

780 """Get the number of turning points in the efficient frontier. 

781 

782 Returns: 

783 The number of turning points currently stored in the object. 

784 

785 """ 

786 return len(self.turning_points) 

787 

788 def _first_turning_point(self) -> TurningPoint: 

789 """Return the maximum-return vertex (see :func:`cvxcla.first.first_turning_point`).""" 

790 return first_turning_point( 

791 self._traced_mean, 

792 self.lower_bounds, 

793 self.upper_bounds, 

794 self.a, 

795 self.b, 

796 self.g_matrix, 

797 self.h_vector, 

798 self.tol, 

799 ) 

800 

801 def _append(self, tp: TurningPoint, tol: float | None = None) -> None: 

802 """Append a turning point to the list of turning points. 

803 

804 This method validates that the turning point satisfies the constraints 

805 (see :func:`cvxcla._checks.check_feasible`) before adding it to the list. 

806 

807 Args: 

808 tp: The turning point to append. 

809 tol: Tolerance for constraint validation. If None, uses the class's 

810 tol attribute. Pass 0 for exact validation. 

811 

812 Raises: 

813 ValueError: If the turning point violates any constraints. 

814 

815 """ 

816 tol = self.tol if tol is None else tol 

817 check_feasible( 

818 tp.weights, 

819 self.lower_bounds, 

820 self.upper_bounds, 

821 self.a, 

822 self.b, 

823 self.g_matrix, 

824 self.h_vector, 

825 self.leverage, 

826 tol, 

827 ) 

828 self.turning_points.append(tp) 

829 

830 def _emit( 

831 self, 

832 lamb: float, 

833 weights: NDArray[np.float64], 

834 free: NDArray[np.bool_], 

835 active_ineq: NDArray[np.bool_], 

836 nu: NDArray[np.float64], 

837 eta: NDArray[np.float64], 

838 guard: bool = True, 

839 ) -> None: 

840 """Build and store a turning point, projecting away sub-tolerance round-off. 

841 

842 Orchestrates the three steps taken at every turning point: refuse the point 

843 if the free-asset block is numerically singular (see 

844 :func:`cvxcla._checks.guard_degeneracy`); project the candidate back onto the feasible 

845 set to clear sub-tolerance round-off (see 

846 :func:`cvxcla._projection.project_feasible`); then validate and store it 

847 (see :meth:`_append`). 

848 

849 On tie-heavy or near-degenerate problems (a short, near-rank-deficient 

850 sample covariance, duplicated assets, or many coincident events) accumulated 

851 floating-point round-off over the many turning points of a large trace can 

852 place a free weight a hair outside its box. The covariance there has 

853 near-flat directions (its small eigenvalues) and the round-off lies in 

854 exactly those directions, so the candidate is optimal to solver precision 

855 but not exactly feasible; the projection clears it and is a strict no-op for 

856 the well-posed turning points that are already feasible. 

857 """ 

858 if guard and not self._free_blocks_well_conditioned: 

859 guard_degeneracy(self.covariance_operator, lamb, free, np.vstack([self.a, self.g_matrix[active_ineq]])) 

860 weights = project_feasible( 

861 weights, 

862 self.lower_bounds, 

863 self.upper_bounds, 

864 self.a, 

865 self.b, 

866 self.g_matrix, 

867 self.h_vector, 

868 active_ineq, 

869 ) 

870 self._append(TurningPoint(lamb=lamb, weights=weights, free=free, active_ineq=active_ineq, nu=nu, eta=eta)) 

871 

872 @property 

873 def frontier(self) -> Frontier: 

874 """Get the efficient frontier constructed from the turning points. 

875 

876 This property creates a Frontier object from the list of turning points, 

877 which can be used to analyze the risk-return characteristics of the 

878 efficient portfolios. 

879 

880 Returns: 

881 A Frontier object representing the efficient frontier. 

882 

883 """ 

884 return Frontier( 

885 covariance=self.covariance, 

886 mean=self.mean, 

887 frontier=[FrontierPoint(point.weights) for point in self.turning_points], 

888 ) 

889 

890 

891@dataclass(frozen=True) 

892class _LeveragedCLA(CLA): 

893 """The CLA over the long/short legs of a leverage-constrained problem. 

894 

895 Built only by :meth:`CLA._trace_leveraged`; its covariance is a 

896 :class:`cvxcla._leverage.SignedLift` and its last inequality row is the 

897 gross-exposure cap. It differs from the plain CLA in three places, all 

898 stemming from the lifted covariance being singular along "raise both legs of 

899 one asset": 

900 

901 * the leave-a-bound event of a leg whose partner is off its lower bound is 

902 masked, so both legs of an asset are never free together (see 

903 :func:`cvxcla._leverage.mask_leg_events`); 

904 * a maximum-return vertex with overlapping legs is netted before the trace 

905 starts (the LP can return one when the cap is tight with a zero multiplier); 

906 * the up-front conditioning test is taken on the asset covariance, since the 

907 lifted form is singular as a whole but never on a free block that is traced. 

908 

909 Attributes: 

910 lift: The signed leg structure. 

911 """ 

912 

913 lift: LeverageLift | None = None 

914 

915 @property 

916 def _legs(self) -> LeverageLift: 

917 """The leg structure (always set by :meth:`CLA._trace_leveraged`).""" 

918 return cast(LeverageLift, self.lift) 

919 

920 @cached_property 

921 def _free_blocks_well_conditioned(self) -> bool: 

922 """Whether the asset covariance clears the singularity floor. 

923 

924 A traced free block holds at most one leg per asset, so it is a signed 

925 principal block of the asset covariance and interlacing applies to that. 

926 """ 

927 return well_conditioned(cast(SignedLift, self.covariance).base) 

928 

929 def event_matrix(self, state: TurningPoint, segment: Segment) -> NDArray[np.float64]: 

930 """Return the event matrix with the competing leg events masked.""" 

931 events = super().event_matrix(state, segment) 

932 legs = self.dimension 

933 events[:legs] = mask_leg_events(events[:legs], self._legs.partner, segment.at_lower) 

934 return events 

935 

936 def _first_turning_point(self) -> TurningPoint: 

937 """Return the maximum-return vertex with overlapping legs netted out.""" 

938 first = super()._first_turning_point() 

939 netted = self._legs.net(first.weights) 

940 if np.array_equal(netted, first.weights): 

941 return first 

942 return classify_vertex( 

943 netted, self.lower_bounds, self.upper_bounds, self.a, self.g_matrix, self.h_vector, self.tol 

944 )