Coverage for src/cvxcla/types.py: 100%
123 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"""Type definitions and classes for the Critical Line Algorithm.
3This module defines the core data structures used in the Critical Line Algorithm:
4- FrontierPoint: Represents a point on the efficient frontier.
5- TurningPoint: Represents a turning point on the efficient frontier.
6- Frontier: Represents the entire efficient frontier.
8It also defines type aliases for commonly used types.
9"""
11from __future__ import annotations
13import itertools
14import warnings
15from collections.abc import Iterator
16from dataclasses import dataclass, field
17from typing import TYPE_CHECKING
19if TYPE_CHECKING:
20 import plotly.graph_objects as go
22import numpy as np
23from numpy.typing import NDArray
25from .operators import CovarianceOperator
28def _covariance_matvec(
29 covariance: NDArray[np.float64] | CovarianceOperator, x: NDArray[np.float64]
30) -> NDArray[np.float64]:
31 """Compute ``Sigma @ x`` for a dense matrix or a ``CovarianceOperator`` backend."""
32 if isinstance(covariance, CovarianceOperator):
33 return covariance.matvec(x)
34 return covariance @ x
37@dataclass(frozen=True)
38class FrontierPoint:
39 """A point on the efficient frontier.
41 This class represents a portfolio on the efficient frontier, defined by its weights.
42 It provides methods to compute the expected return and variance of the portfolio.
44 Attributes:
45 weights: Vector of portfolio weights for each asset.
47 """
49 weights: NDArray[np.float64]
51 def mean(self, mean: NDArray[np.float64]) -> float:
52 """Compute the expected return of the portfolio.
54 Args:
55 mean: Vector of expected returns for each asset.
57 Returns:
58 The expected return of the portfolio.
60 Examples:
61 >>> import numpy as np
62 >>> fp = FrontierPoint(weights=np.array([0.5, 0.5]))
63 >>> fp.mean(np.array([0.1, 0.2]))
64 0.15000000000000002
66 """
67 return float(mean.T @ self.weights)
69 def variance(self, covariance: NDArray[np.float64] | CovarianceOperator) -> float:
70 """Compute the expected variance of the portfolio.
72 Args:
73 covariance: Covariance matrix of asset returns, either as a dense
74 matrix or as a ``CovarianceOperator`` backend.
76 Returns:
77 The expected variance of the portfolio.
79 Examples:
80 >>> import numpy as np
81 >>> fp = FrontierPoint(weights=np.array([0.5, 0.5]))
82 >>> covariance = np.array([[0.04, 0.0], [0.0, 0.09]])
83 >>> fp.variance(covariance)
84 0.0325
86 A ``CovarianceOperator`` backend gives the same number without
87 forming the matrix:
89 >>> from cvxcla import DenseCovariance
90 >>> fp.variance(DenseCovariance(covariance))
91 0.0325
93 """
94 return float(self.weights.T @ _covariance_matvec(covariance, self.weights))
97@dataclass(frozen=True)
98class TurningPoint(FrontierPoint):
99 """Turning point.
101 A turning point is a vector of weights, a lambda value, and a boolean vector
102 indicating which assets are free. All assets that are not free are blocked.
104 For problems with general inequality constraints ``G w <= h`` the turning
105 point also records which inequality *rows* are active (held at equality
106 ``g_i w = h_i``) via ``active_ineq``. These are the row analogue of the box
107 active set: a free weight on a bound is a per-variable active constraint, an
108 active inequality row is a per-row one. The default is an empty mask, so
109 box-and-equality problems (and the LASSO path) are unaffected.
111 A turning point traced by ``CLA`` also records the KKT multipliers: ``nu``
112 (one entry per equality row of ``CLA.a``) and ``eta`` (one entry per row of
113 ``G``, zero on the inactive rows), so that on the free assets
115 ``Sigma w - q - lamb * mean + A^T nu + G^T eta = 0``,
117 where ``q`` is the linear term of ``CLA(q=...)`` (zero by default).
119 At ``lamb = inf`` the multipliers grow with ``lamb``, so their slopes
120 ``nu / lamb`` and ``eta / lamb`` are recorded instead, and the identity reads
121 ``-mean + A^T nu + G^T eta = 0`` on the free assets. Both default to empty
122 arrays for a turning point built by hand. On a ``CLA(leverage=...)`` trace
123 ``eta`` covers the rows of ``g`` only, so the gross-exposure cap's multiplier
124 is not included.
126 Examples:
127 >>> import numpy as np
128 >>> tp = TurningPoint(
129 ... weights=np.array([0.5, 0.5, 0.0]),
130 ... free=np.array([True, True, False]),
131 ... lamb=1.25,
132 ... )
133 >>> tp.free_indices
134 array([0, 1])
135 >>> tp.blocked_indices
136 array([2])
138 ``free`` and ``blocked`` partition the assets, so the two index sets are
139 always complementary:
141 >>> len(tp.free_indices) + len(tp.blocked_indices) == len(tp.weights)
142 True
143 """
145 free: NDArray[np.bool_]
146 lamb: float = np.inf
147 active_ineq: NDArray[np.bool_] = field(default_factory=lambda: np.zeros(0, dtype=bool))
148 nu: NDArray[np.float64] = field(default_factory=lambda: np.zeros(0))
149 eta: NDArray[np.float64] = field(default_factory=lambda: np.zeros(0))
151 @property
152 def free_indices(self) -> np.ndarray:
153 """Returns the indices of the free assets."""
154 return np.where(self.free)[0]
156 @property
157 def blocked_indices(self) -> np.ndarray:
158 """Returns the indices of the blocked assets."""
159 return np.where(~self.free)[0]
162@dataclass(frozen=True)
163class Frontier:
164 """A frontier is a list of frontier points. Some of them might be turning points.
166 The frontier owns the ``mean`` and ``covariance`` the points are scored
167 against, so the risk/return properties below (``returns``, ``variance``,
168 ``volatility``, ``sharpe_ratio``) are vectors with one entry per point, in
169 frontier order -- from the maximum-return end towards minimum variance.
171 Examples:
172 >>> import numpy as np
173 >>> mean = np.array([0.1, 0.2])
174 >>> covariance = np.array([[0.04, 0.0], [0.0, 0.09]])
175 >>> frontier = Frontier(
176 ... mean=mean,
177 ... covariance=covariance,
178 ... frontier=[
179 ... FrontierPoint(weights=np.array([0.0, 1.0])),
180 ... FrontierPoint(weights=np.array([1.0, 0.0])),
181 ... ],
182 ... )
183 >>> len(frontier)
184 2
185 >>> frontier.returns
186 array([0.2, 0.1])
187 >>> frontier.volatility
188 array([0.3, 0.2])
190 Usually you get one from a solved :class:`~cvxcla.cla.CLA` rather than
191 by hand:
193 >>> from cvxcla import CLA
194 >>> solved = CLA.problem(mean, covariance).long_only().budget().trace()
195 >>> isinstance(solved.frontier, Frontier)
196 True
197 """
199 mean: NDArray[np.float64]
200 covariance: NDArray[np.float64] | CovarianceOperator
201 frontier: list[FrontierPoint] = field(default_factory=list)
203 def interpolate(self, num: int = 100) -> Frontier:
204 """Interpolate the frontier with additional points between existing points.
206 The weights are linear in lambda between adjacent turning points, so convex
207 combinations of the two are exactly the frontier portfolios in between. Their
208 return and variance are not linear in each other (variance is quadratic along a
209 segment), so a smooth plot of the frontier needs these points; straight lines
210 between the turning points would lie to the right of the frontier.
212 Args:
213 num: The number of points per segment, both ends included. The result is
214 the first point followed by num-1 points for each adjacent pair, ending
215 with the last point.
217 Returns:
218 A new Frontier object with the interpolated points.
220 Examples:
221 >>> import numpy as np
222 >>> frontier = Frontier(
223 ... mean=np.array([0.1, 0.2]),
224 ... covariance=np.array([[0.04, 0.0], [0.0, 0.09]]),
225 ... frontier=[
226 ... FrontierPoint(weights=np.array([0.0, 1.0])),
227 ... FrontierPoint(weights=np.array([1.0, 0.0])),
228 ... ],
229 ... )
230 >>> len(frontier.interpolate(num=10))
231 10
233 One adjacent pair yields ``num - 1`` points, and every interpolated
234 point is a convex combination of its neighbours -- so a budget
235 constraint satisfied at the turning points still holds between them:
237 >>> dense = frontier.interpolate(num=10)
238 >>> bool(np.allclose(dense.weights.sum(axis=1), 1.0))
239 True
241 """
243 def _interpolate() -> Iterator[FrontierPoint]:
244 """Yield the first point, then the interpolated points of each adjacent pair."""
245 if len(self.frontier) > 0:
246 yield FrontierPoint(weights=self.weights[0])
247 for w_right, w_left in zip(self.weights[0:-1], self.weights[1:], strict=False): # pragma: no mutate
248 for lamb in np.linspace(0, 1, num):
249 if lamb > 0:
250 yield FrontierPoint(weights=lamb * w_left + (1 - lamb) * w_right)
252 points = list(_interpolate())
253 return Frontier(frontier=points, mean=self.mean, covariance=self.covariance)
255 def __iter__(self) -> Iterator[FrontierPoint]:
256 """Iterate over all frontier points."""
257 yield from self.frontier
259 def __len__(self) -> int:
260 """Give number of frontier points."""
261 return len(self.frontier)
263 @property
264 def weights(self) -> np.ndarray:
265 """Matrix of weights. One row per point."""
266 return np.array([point.weights for point in self])
268 @property
269 def returns(self) -> np.ndarray:
270 """Vector of expected returns."""
271 return np.array([point.mean(self.mean) for point in self])
273 @property
274 def variance(self) -> np.ndarray:
275 """Vector of expected variances."""
276 return np.array([point.variance(self.covariance) for point in self])
278 @property
279 def sharpe_ratio(self) -> np.ndarray:
280 """Vector of expected Sharpe ratios.
282 The ratio is undefined at a zero-variance point (``w = 0`` at the end of a
283 dollar-neutral frontier, say) and is NaN there, without a warning.
284 """
285 returns = self.returns
286 volatility = self.volatility
287 ratios: np.ndarray = np.full_like(returns, np.nan)
288 np.divide(returns, volatility, out=ratios, where=volatility > 0)
289 return ratios
291 @property
292 def volatility(self) -> np.ndarray:
293 """Vector of expected volatilities."""
294 vol: np.ndarray = np.sqrt(self.variance)
295 return vol
297 @property
298 def max_sharpe(self) -> tuple[float, np.ndarray]:
299 """Maximal Sharpe ratio on the frontier.
301 The frontier is piecewise affine in the weights, and on each segment the
302 Sharpe ratio has a closed-form maximiser (see :meth:`_segment_max_sharpe`).
303 Every segment is scanned, so the result is the exact maximum over the whole
304 frontier and relies on no unimodality argument. Points of zero variance,
305 where the ratio is undefined, are skipped.
307 Returns:
308 Tuple of maximal Sharpe ratio and the weights to achieve it
310 Raises:
311 ValueError: If no point of the frontier has positive variance.
313 Warns:
314 UserWarning: If the maximum is not positive -- no frontier portfolio
315 has a positive expected return, so the result is the least negative
316 ratio rather than a meaningful tangency portfolio.
318 Examples:
319 >>> import numpy as np
320 >>> frontier = Frontier(
321 ... mean=np.array([0.1, 0.2]),
322 ... covariance=np.array([[0.04, 0.0], [0.0, 0.09]]),
323 ... frontier=[
324 ... FrontierPoint(weights=np.array([0.0, 1.0])),
325 ... FrontierPoint(weights=np.array([1.0, 0.0])),
326 ... ],
327 ... )
328 >>> sharpe, weights = frontier.max_sharpe
329 >>> float(np.round(sharpe, 6))
330 0.833333
331 >>> bool(np.allclose(weights, [0.529412, 0.470588], atol=1e-6))
332 True
334 The continuous optimum sits *between* two turning points, so it
335 beats every discrete point on the frontier -- which is the reason
336 this is not simply ``argmax(sharpe_ratio)``:
338 >>> bool(sharpe > frontier.sharpe_ratio.max())
339 True
341 """
342 weights = self.weights
343 points = [(float(ratio), w) for ratio, w in zip(self.sharpe_ratio, weights, strict=True)]
344 segments = [self._segment_max_sharpe(w0, w1) for w0, w1 in itertools.pairwise(weights)]
345 candidates = [(ratio, w) for ratio, w in points + segments if not np.isnan(ratio)]
346 if not candidates:
347 msg = "The Sharpe ratio is undefined: no frontier point has positive variance"
348 raise ValueError(msg)
350 sharpe, best = max(candidates, key=lambda item: item[0])
351 if sharpe <= 0.0:
352 warnings.warn(
353 f"No frontier portfolio has a positive expected return; the maximum Sharpe ratio is {sharpe:.6g}",
354 UserWarning,
355 stacklevel=2,
356 )
357 return sharpe, best
359 def _segment_max_sharpe(self, w0: np.ndarray, w1: np.ndarray) -> tuple[float, np.ndarray]:
360 """Closed-form maximum Sharpe ratio on the affine segment between two points.
362 Parametrise the segment as ``w(t) = (1 - t) w0 + t w1`` for ``t`` in
363 ``[0, 1]``. The expected return is affine and the variance quadratic in
364 ``t``, so the Sharpe ratio is::
366 S(t) = (a0 + a1 t) / sqrt(c0 + c1 t + c2 t**2)
368 Its derivative has a *linear* numerator (the ``t**2`` terms cancel), so
369 there is a single stationary point
370 ``t* = (a0 c1 - 2 a1 c0) / (a1 c1 - 2 a0 c2)``. The maximiser over the
371 segment is therefore whichever of ``{0, 1, clamp(t*)}`` yields the largest
372 Sharpe ratio, evaluated in closed form rather than by a bounded line search.
373 A candidate of zero variance is skipped.
375 Args:
376 w0: Weights at the ``t = 0`` end of the segment.
377 w1: Weights at the ``t = 1`` end of the segment.
379 Returns:
380 Tuple of the maximal Sharpe ratio on the segment and its weights; the
381 ratio is NaN if the variance vanishes at every candidate.
383 """
384 delta = w1 - w0
385 sigma_w0 = _covariance_matvec(self.covariance, w0)
386 sigma_delta = _covariance_matvec(self.covariance, delta)
387 a0 = float(self.mean @ w0)
388 a1 = float(self.mean @ delta)
389 c0 = float(w0 @ sigma_w0)
390 c1 = 2.0 * float(w0 @ sigma_delta)
391 c2 = float(delta @ sigma_delta)
393 # Candidate positions: the two endpoints and the interior stationary point
394 # (only when it falls strictly inside the segment).
395 candidates = [0.0, 1.0]
396 denominator = a1 * c1 - 2.0 * a0 * c2
397 if denominator != 0.0:
398 t_star = (a0 * c1 - 2.0 * a1 * c0) / denominator
399 if 0.0 < t_star < 1.0:
400 candidates.append(t_star)
402 best: tuple[float, np.ndarray] = (np.nan, w0)
403 for t in candidates:
404 variance = c0 + c1 * t + c2 * t * t
405 if variance > 0.0:
406 sharpe = (a0 + a1 * t) / np.sqrt(variance)
407 if np.isnan(best[0]) or sharpe > best[0]:
408 best = (float(sharpe), w0 + t * delta)
409 return best
411 def plot(self, volatility: bool = False, markers: bool = True, num: int = 50) -> go.Figure:
412 """Plot the efficient frontier.
414 Expected return goes on the y-axis and variance or volatility on the x-axis. The
415 curve is drawn through ``num`` frontier portfolios per segment (see
416 :meth:`interpolate`), not by straight lines between the turning points: along a
417 segment the frontier is a parabola in (variance, return) and a hyperbola in
418 (volatility, return).
420 Args:
421 volatility: If True, plot volatility (standard deviation) on the x-axis.
422 If False, plot variance on the x-axis.
423 markers: If True, mark the turning points in a second trace.
424 num: Points per segment for the curve, both ends included.
426 Returns:
427 A plotly Figure object that can be displayed or saved.
429 """
430 try:
431 import plotly.graph_objects as go
432 except ImportError as e:
433 msg = "Plotting requires plotly. Install it with: pip install cvxcla[plot]"
434 raise ImportError(msg) from e
436 def x_of(frontier: Frontier) -> np.ndarray:
437 return frontier.volatility if volatility else frontier.variance
439 curve = self.interpolate(num=num)
440 fig = go.Figure()
441 fig.add_trace(go.Scatter(x=x_of(curve), y=curve.returns, mode="lines", name="Efficient Frontier"))
442 if markers:
443 fig.add_trace(go.Scatter(x=x_of(self), y=self.returns, mode="markers", name="Turning points"))
445 fig.update_layout(
446 xaxis_title="Expected volatility" if volatility else "Expected variance",
447 yaxis_title="Expected Return",
448 )
450 return fig