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

1"""Type definitions and classes for the Critical Line Algorithm. 

2 

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. 

7 

8It also defines type aliases for commonly used types. 

9""" 

10 

11from __future__ import annotations 

12 

13import itertools 

14import warnings 

15from collections.abc import Iterator 

16from dataclasses import dataclass, field 

17from typing import TYPE_CHECKING 

18 

19if TYPE_CHECKING: 

20 import plotly.graph_objects as go 

21 

22import numpy as np 

23from numpy.typing import NDArray 

24 

25from .operators import CovarianceOperator 

26 

27 

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 

35 

36 

37@dataclass(frozen=True) 

38class FrontierPoint: 

39 """A point on the efficient frontier. 

40 

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. 

43 

44 Attributes: 

45 weights: Vector of portfolio weights for each asset. 

46 

47 """ 

48 

49 weights: NDArray[np.float64] 

50 

51 def mean(self, mean: NDArray[np.float64]) -> float: 

52 """Compute the expected return of the portfolio. 

53 

54 Args: 

55 mean: Vector of expected returns for each asset. 

56 

57 Returns: 

58 The expected return of the portfolio. 

59 

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 

65 

66 """ 

67 return float(mean.T @ self.weights) 

68 

69 def variance(self, covariance: NDArray[np.float64] | CovarianceOperator) -> float: 

70 """Compute the expected variance of the portfolio. 

71 

72 Args: 

73 covariance: Covariance matrix of asset returns, either as a dense 

74 matrix or as a ``CovarianceOperator`` backend. 

75 

76 Returns: 

77 The expected variance of the portfolio. 

78 

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 

85 

86 A ``CovarianceOperator`` backend gives the same number without 

87 forming the matrix: 

88 

89 >>> from cvxcla import DenseCovariance 

90 >>> fp.variance(DenseCovariance(covariance)) 

91 0.0325 

92 

93 """ 

94 return float(self.weights.T @ _covariance_matvec(covariance, self.weights)) 

95 

96 

97@dataclass(frozen=True) 

98class TurningPoint(FrontierPoint): 

99 """Turning point. 

100 

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. 

103 

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. 

110 

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 

114 

115 ``Sigma w - q - lamb * mean + A^T nu + G^T eta = 0``, 

116 

117 where ``q`` is the linear term of ``CLA(q=...)`` (zero by default). 

118 

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. 

125 

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

137 

138 ``free`` and ``blocked`` partition the assets, so the two index sets are 

139 always complementary: 

140 

141 >>> len(tp.free_indices) + len(tp.blocked_indices) == len(tp.weights) 

142 True 

143 """ 

144 

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

150 

151 @property 

152 def free_indices(self) -> np.ndarray: 

153 """Returns the indices of the free assets.""" 

154 return np.where(self.free)[0] 

155 

156 @property 

157 def blocked_indices(self) -> np.ndarray: 

158 """Returns the indices of the blocked assets.""" 

159 return np.where(~self.free)[0] 

160 

161 

162@dataclass(frozen=True) 

163class Frontier: 

164 """A frontier is a list of frontier points. Some of them might be turning points. 

165 

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. 

170 

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

189 

190 Usually you get one from a solved :class:`~cvxcla.cla.CLA` rather than 

191 by hand: 

192 

193 >>> from cvxcla import CLA 

194 >>> solved = CLA.problem(mean, covariance).long_only().budget().trace() 

195 >>> isinstance(solved.frontier, Frontier) 

196 True 

197 """ 

198 

199 mean: NDArray[np.float64] 

200 covariance: NDArray[np.float64] | CovarianceOperator 

201 frontier: list[FrontierPoint] = field(default_factory=list) 

202 

203 def interpolate(self, num: int = 100) -> Frontier: 

204 """Interpolate the frontier with additional points between existing points. 

205 

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. 

211 

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. 

216 

217 Returns: 

218 A new Frontier object with the interpolated points. 

219 

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 

232 

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: 

236 

237 >>> dense = frontier.interpolate(num=10) 

238 >>> bool(np.allclose(dense.weights.sum(axis=1), 1.0)) 

239 True 

240 

241 """ 

242 

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) 

251 

252 points = list(_interpolate()) 

253 return Frontier(frontier=points, mean=self.mean, covariance=self.covariance) 

254 

255 def __iter__(self) -> Iterator[FrontierPoint]: 

256 """Iterate over all frontier points.""" 

257 yield from self.frontier 

258 

259 def __len__(self) -> int: 

260 """Give number of frontier points.""" 

261 return len(self.frontier) 

262 

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

267 

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

272 

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

277 

278 @property 

279 def sharpe_ratio(self) -> np.ndarray: 

280 """Vector of expected Sharpe ratios. 

281 

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 

290 

291 @property 

292 def volatility(self) -> np.ndarray: 

293 """Vector of expected volatilities.""" 

294 vol: np.ndarray = np.sqrt(self.variance) 

295 return vol 

296 

297 @property 

298 def max_sharpe(self) -> tuple[float, np.ndarray]: 

299 """Maximal Sharpe ratio on the frontier. 

300 

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. 

306 

307 Returns: 

308 Tuple of maximal Sharpe ratio and the weights to achieve it 

309 

310 Raises: 

311 ValueError: If no point of the frontier has positive variance. 

312 

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. 

317 

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 

333 

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

337 

338 >>> bool(sharpe > frontier.sharpe_ratio.max()) 

339 True 

340 

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) 

349 

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 

358 

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. 

361 

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

365 

366 S(t) = (a0 + a1 t) / sqrt(c0 + c1 t + c2 t**2) 

367 

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. 

374 

375 Args: 

376 w0: Weights at the ``t = 0`` end of the segment. 

377 w1: Weights at the ``t = 1`` end of the segment. 

378 

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. 

382 

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) 

392 

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) 

401 

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 

410 

411 def plot(self, volatility: bool = False, markers: bool = True, num: int = 50) -> go.Figure: 

412 """Plot the efficient frontier. 

413 

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

419 

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. 

425 

426 Returns: 

427 A plotly Figure object that can be displayed or saved. 

428 

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 

435 

436 def x_of(frontier: Frontier) -> np.ndarray: 

437 return frontier.volatility if volatility else frontier.variance 

438 

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

444 

445 fig.update_layout( 

446 xaxis_title="Expected volatility" if volatility else "Expected variance", 

447 yaxis_title="Expected Return", 

448 ) 

449 

450 return fig