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
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-17 13:36 +0000
1"""Markowitz implementation of the Critical Line Algorithm.
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"""
9import logging
10from dataclasses import dataclass, field, replace
11from functools import cached_property
12from typing import cast
14import numpy as np
15from cvx.linalg import DenseOperator
16from numpy.typing import NDArray
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
30# Multiplier intercepts within this many ulps per dimension of the terms that form them are zero.
31_GAMMA_NOISE_ULPS = 100
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.
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.
44 Args:
45 a: Equality-constraint matrix (``m x n``).
46 b: Equality-constraint right-hand side (length ``m``).
48 Returns:
49 The independent rows ``(a, b)``; the input itself when none is redundant.
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]
69def _owned(value: NDArray[np.float64]) -> NDArray[np.float64]:
70 """Return a read-only float copy of ``value``, owned by the problem.
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.
77 Args:
78 value: An array-like input (``mean``, a bound, a constraint, a dense covariance).
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
88def _own_inputs(cla: "CLA") -> None:
89 """Replace every array input of ``cla`` by a read-only copy (see :func:`_owned`).
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.
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))
106def _check_finite_inputs(cla: "CLA") -> None:
107 """Refuse non-finite data before anything is traced.
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.
117 Args:
118 cla: The problem being constructed.
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)
141def _check_shapes(cla: "CLA") -> None:
142 """Refuse mis-shaped inequality and benchmark data.
144 Args:
145 cla: The problem being constructed.
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)
163def _check_options(cla: "CLA") -> None:
164 """Refuse an invalid ``stop`` or ``leverage``, or the two combined.
166 Args:
167 cla: The problem being constructed.
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)
187class _FaceShift(QuadraticForm):
188 """The form ``base + c u u^T``, which agrees with ``base`` on ``u^T w = const`` up to a constant.
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.
195 Attributes:
196 base: The unshifted form.
197 u: The direction of the shift (the returns).
198 c: Its weight.
199 """
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
207 @property
208 def n(self) -> int:
209 """Dimension of the form."""
210 return int(self.base.n)
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)
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
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)))
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)
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)))
240@dataclass(frozen=True)
241class CLA(InequalityConstrained):
242 """Critical Line Algorithm implementation based on Markowitz's approach.
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.
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.
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``.
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.
310 """
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
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.
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.
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.
341 Args:
342 mean: Vector of expected returns of length ``n``.
343 covariance: Covariance matrix or ``QuadraticForm`` backend.
345 Returns:
346 A ``ProblemBuilder`` ready to accept constraints, whose ``.trace()``
347 returns a solved ``CLA``.
348 """
349 return ProblemBuilder(mean, covariance, solver=cls)
351 @cached_property
352 def covariance_operator(self) -> QuadraticForm:
353 """Return the covariance as a ``QuadraticForm`` backend.
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)
363 @property
364 def dimension(self) -> int:
365 """Number of assets ``n`` (the problem dimension for the path tracer)."""
366 return len(self.mean)
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`).
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)
377 def __post_init__(self) -> None:
378 """Initialize the CLA object and compute the efficient frontier.
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.
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.
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.
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.
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.
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()
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`).
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
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
463 def _restore_mean_units(self) -> None:
464 """Map the turning points traced on :attr:`_traced_mean` back to ``mean``.
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
483 def _trace_leveraged(self, leverage: float) -> None:
484 """Trace the frontier under ``||w||_1 <= leverage`` via the signed lift.
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``.
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))
523 def begin(self) -> tuple[float, TurningPoint]:
524 """Record the first turning point and start the trace at ``lambda = inf``.
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
536 def _tied_start(self, first: TurningPoint) -> bool:
537 """Whether ``first`` holds a tied asset on a bound it should leave at ``lambda = inf``.
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))
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.
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)
611 def segment(self, state: TurningPoint) -> Segment:
612 """Solve the reduced KKT system for the critical-line segment at ``state``.
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
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))
643 @cached_property
644 def _scales(self) -> tuple[float, float]:
645 """Return ``(lambda_scale, mu_scale)``, the natural units of the problem.
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
669 @property
670 def lambda_scale(self) -> float:
671 """The natural scale of ``lambda`` (covariance scale over return scale).
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]
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`).
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))
692 def _gamma_noise(self, segment: Segment) -> NDArray[np.float64]:
693 """The round-off level of each multiplier intercept ``gamma``.
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
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
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``.
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.
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]
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)
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`).
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 )
779 def __len__(self) -> int:
780 """Get the number of turning points in the efficient frontier.
782 Returns:
783 The number of turning points currently stored in the object.
785 """
786 return len(self.turning_points)
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 )
801 def _append(self, tp: TurningPoint, tol: float | None = None) -> None:
802 """Append a turning point to the list of turning points.
804 This method validates that the turning point satisfies the constraints
805 (see :func:`cvxcla._checks.check_feasible`) before adding it to the list.
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.
812 Raises:
813 ValueError: If the turning point violates any constraints.
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)
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.
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`).
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))
872 @property
873 def frontier(self) -> Frontier:
874 """Get the efficient frontier constructed from the turning points.
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.
880 Returns:
881 A Frontier object representing the efficient frontier.
883 """
884 return Frontier(
885 covariance=self.covariance,
886 mean=self.mean,
887 frontier=[FrontierPoint(point.weights) for point in self.turning_points],
888 )
891@dataclass(frozen=True)
892class _LeveragedCLA(CLA):
893 """The CLA over the long/short legs of a leverage-constrained problem.
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":
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.
909 Attributes:
910 lift: The signed leg structure.
911 """
913 lift: LeverageLift | None = None
915 @property
916 def _legs(self) -> LeverageLift:
917 """The leg structure (always set by :meth:`CLA._trace_leveraged`)."""
918 return cast(LeverageLift, self.lift)
920 @cached_property
921 def _free_blocks_well_conditioned(self) -> bool:
922 """Whether the asset covariance clears the singularity floor.
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)
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
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 )