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

141 statements  

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

1"""First turning point computation for the Critical Line Algorithm. 

2 

3This module provides functions to compute the first turning point on the efficient frontier, 

4which is the portfolio with the highest expected return that satisfies the constraints. 

5Two implementations are provided: a direct algorithm and a linear programming approach. 

6""" 

7 

8from __future__ import annotations 

9 

10from typing import NamedTuple 

11 

12import numpy as np 

13from numpy.typing import NDArray 

14from scipy.optimize import linprog # type: ignore[import-untyped] 

15 

16from .errors import DegenerateProblemError, InfeasibleProblemError, NumericalError 

17from .operators import orthonormal_rows 

18from .types import TurningPoint 

19 

20 

21# 

22def init_algo( 

23 mean: NDArray[np.float64], 

24 lower_bounds: NDArray[np.float64], 

25 upper_bounds: NDArray[np.float64], 

26 total: float = 1.0, 

27) -> TurningPoint: 

28 """Compute the first turning point for a single all-ones budget constraint. 

29 

30 The key insight behind Markowitz's CLA is to find first the 

31 turning point associated with the highest expected return, and then 

32 compute the sequence of turning points, each with a lower expected 

33 return than the previous. That first turning point consists in the 

34 smallest subset of assets with highest return such that the sum of 

35 their upper boundaries equals or exceeds the budget ``total``. 

36 

37 We sort the expected returns in descending order. 

38 This gives us a sequence for searching for the 

39 first free asset. All weights are initially set to their lower bounds, 

40 and following the sequence from the previous step, we move those 

41 weights from the lower to the upper bound until the sum of weights 

42 reaches ``total``. The last iterated weight is then reduced 

43 to comply with the constraint that the sum of weights equals ``total``. 

44 This last weight is the first free asset, 

45 and the resulting vector of weights the first turning point. 

46 

47 Args: 

48 mean: Vector of expected returns. 

49 lower_bounds: Lower box bounds. 

50 upper_bounds: Upper box bounds. 

51 total: Target sum of weights (the right-hand side ``b`` of the all-ones 

52 budget constraint ``sum(w) = total``; ``1`` for fully-invested, 

53 ``0`` for dollar-neutral, ``> 1`` for a leveraged total). 

54 

55 Raises: 

56 InfeasibleProblemError: If a lower bound exceeds its upper bound, or the 

57 bounds cannot sum to ``total``. 

58 """ 

59 if np.any(lower_bounds > upper_bounds): 

60 msg = "Lower bounds must be less than or equal to upper bounds" 

61 raise InfeasibleProblemError(msg) 

62 

63 # Initialize weights to lower bounds 

64 weights = np.copy(lower_bounds).astype(np.float64) 

65 free = np.full_like(mean, False, dtype=np.bool_) 

66 

67 # Move weights from lower to upper bound until the sum reaches ``total``. The 

68 # check needs a tolerance: the increment ``total - sum(weights)`` can bring the 

69 # sum to ``total`` only up to floating-point error, and without the slack the 

70 # loop would move on and mark the NEXT asset (sitting on its bound) as free 

71 # while the genuinely interior asset stays blocked. 

72 for index in np.argsort(-mean): 

73 weights[index] += np.min([upper_bounds[index] - lower_bounds[index], total - np.sum(weights)]) 

74 if np.sum(weights) >= total - 1e-12: 

75 free[index] = True 

76 break 

77 

78 if not np.any(free): 

79 # No asset ended up interior: the bounds cannot sum to the target. 

80 msg = "Could not construct a fully invested portfolio" 

81 raise InfeasibleProblemError(msg) 

82 

83 # Return first turning point, the point with the highest expected return. 

84 return TurningPoint(free=free, weights=weights) 

85 

86 

87def first_vertex_lp( 

88 mean: NDArray[np.float64], 

89 lower_bounds: NDArray[np.float64], 

90 upper_bounds: NDArray[np.float64], 

91 a: NDArray[np.float64], 

92 b: NDArray[np.float64], 

93 tol: float, 

94 g: NDArray[np.float64] | None = None, 

95 h: NDArray[np.float64] | None = None, 

96) -> TurningPoint: 

97 """Compute the first turning point for a general ``A w = b``, ``G w <= h`` system. 

98 

99 The maximum-return vertex of the feasible polytope 

100 ``{w : A w = b, G w <= h, lower <= w <= upper}`` is a linear program, 

101 ``maximize mean @ w``. The greedy fill of :func:`init_algo` only solves the 

102 single all-ones budget with no inequality rows; for a general (weighted, or 

103 multi-row) ``A`` or any ``G`` we solve the LP directly with HiGHS (via 

104 :func:`scipy.optimize.linprog`), which returns a vertex. The free set is read 

105 off the solution (assets strictly inside their box bounds) and the initial 

106 active inequality set off the tight rows (``g_i w`` at ``h_i`` to tolerance). 

107 

108 Args: 

109 mean: Vector of expected returns. 

110 lower_bounds: Lower box bounds. 

111 upper_bounds: Upper box bounds. 

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

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

114 tol: Tolerance for classifying an asset as free (strictly interior) and a 

115 row as active (tight). 

116 g: Inequality-constraint matrix (``p x n``); ``None`` means no rows. 

117 h: Inequality-constraint right-hand side (length ``p``). 

118 

119 Returns: 

120 The maximum-return vertex as a :class:`TurningPoint`, carrying the active 

121 inequality rows in ``active_ineq``. 

122 

123 A degenerate vertex (every weight on a bound, or a duplicated active row) is 

124 resolved from the set of the linear program's optimal duals, as the greedy fill 

125 of :func:`init_algo` resolves it for the budget: see :func:`classify_vertex`. 

126 

127 Raises: 

128 InfeasibleProblemError: If the linear program is infeasible. 

129 DegenerateProblemError: If it is unbounded, or its vertex is degenerate 

130 beyond what its duals resolve: no optimal dual solution yields a free 

131 set that spans the equality rows together with the active inequality rows. 

132 NumericalError: If the linear program fails for another reason. 

133 """ 

134 g = np.zeros((0, mean.shape[0])) if g is None else np.asarray(g, dtype=np.float64) 

135 h = np.zeros(0) if h is None else np.asarray(h, dtype=np.float64) 

136 

137 weights, gap, eta = _solve_max_return_lp(mean, lower_bounds, upper_bounds, a, b, g, h) 

138 mean = np.asarray(mean, dtype=np.float64) 

139 # Duals carry the units of mu, so their zero test is relative to its scale. 

140 dual_tol = float(np.sqrt(np.finfo(np.float64).eps)) * max(float(np.max(np.abs(mean), initial=0.0)), 1e-300) 

141 return classify_vertex( 

142 weights, 

143 lower_bounds, 

144 upper_bounds, 

145 a, 

146 g, 

147 h, 

148 tol, 

149 duals=VertexDuals(mean=mean, gap=gap, ineq=eta, tol=dual_tol), 

150 ) 

151 

152 

153def first_turning_point( 

154 mean: NDArray[np.float64], 

155 lower_bounds: NDArray[np.float64], 

156 upper_bounds: NDArray[np.float64], 

157 a: NDArray[np.float64], 

158 b: NDArray[np.float64], 

159 g: NDArray[np.float64], 

160 h: NDArray[np.float64], 

161 tol: float, 

162) -> TurningPoint: 

163 """Calculate the first turning point on the efficient frontier. 

164 

165 The first turning point is the maximum-return vertex of the feasible 

166 polytope. For the all-ones budget constraint with no inequality rows and finite 

167 bounds it is found by the greedy fill of :func:`init_algo`; for a general equality system 

168 ``A w = b`` or any ``G w <= h`` it is found by solving the linear program 

169 in :func:`first_vertex_lp`, which also reports the initially-active rows. 

170 

171 Args: 

172 mean: Vector of expected returns. 

173 lower_bounds: Lower box bounds. 

174 upper_bounds: Upper box bounds. 

175 a: Equality-constraint matrix ``A`` of ``A w = b``. 

176 b: Equality-constraint right-hand side ``b``. 

177 g: Inequality-constraint matrix ``G`` of ``G w <= h`` (``(p, n)``). 

178 h: Inequality-constraint right-hand side ``h`` (length ``p``). 

179 tol: Tolerance for the linear-programming vertex classification. 

180 

181 Returns: 

182 A TurningPoint object representing the first point on the efficient frontier. 

183 """ 

184 # The greedy fill needs finite bounds (it starts every weight at its lower bound); 

185 # infinite ones go to the linear program, which reports an unbounded problem. 

186 finite = bool(np.all(np.isfinite(lower_bounds)) and np.all(np.isfinite(upper_bounds))) 

187 if g.shape[0] == 0 and a.shape[0] == 1 and np.allclose(a, 1.0) and finite: 

188 return init_algo(mean=mean, lower_bounds=lower_bounds, upper_bounds=upper_bounds, total=float(b[0])) 

189 return first_vertex_lp(mean=mean, lower_bounds=lower_bounds, upper_bounds=upper_bounds, a=a, b=b, tol=tol, g=g, h=h) 

190 

191 

192class VertexDuals(NamedTuple): 

193 """An optimal dual solution of the maximum-return linear program. 

194 

195 The duals satisfy ``mean = A^T nu + G^T eta + gap``: ``eta >= 0`` holds the 

196 inequality multipliers and ``gap`` the reduced costs of the box bounds (``<= 0`` 

197 on a lower bound, ``>= 0`` on an upper bound, ``0`` off them). The equality 

198 multipliers ``nu`` are not carried: they follow from the rest. 

199 

200 Attributes: 

201 mean: The expected returns (the linear program's objective). 

202 gap: The reduced cost of each variable, in the sign above. 

203 ineq: The inequality multipliers ``eta`` (length ``p``). 

204 tol: Zero tolerance for the duals, in the units of ``mean``. 

205 """ 

206 

207 mean: NDArray[np.float64] 

208 gap: NDArray[np.float64] 

209 ineq: NDArray[np.float64] 

210 tol: float 

211 

212 

213def classify_vertex( 

214 weights: NDArray[np.float64], 

215 lower_bounds: NDArray[np.float64], 

216 upper_bounds: NDArray[np.float64], 

217 a: NDArray[np.float64], 

218 g: NDArray[np.float64], 

219 h: NDArray[np.float64], 

220 tol: float, 

221 duals: VertexDuals | None = None, 

222) -> TurningPoint: 

223 """Read the free set and the active rows off a maximum-return vertex. 

224 

225 An asset is free when it sits strictly inside its box (by more than ``tol``) 

226 and an inequality row is active when it is tight to ``tol``. The vertex is 

227 then checked for degeneracy (see :func:`reject_degenerate_vertex`). 

228 

229 With the linear program's ``duals`` a degenerate vertex -- one whose interior 

230 assets do not span the tight rows -- is resolved first. Its optimal duals are 

231 not unique, and the one the solver happens to report need not show which 

232 partition works, so the partition is chosen from the whole optimal dual set: 

233 :func:`_dual_vertex` moves the reported duals to a vertex of that set, and 

234 :func:`vertex_partition` reads a partition off it -- the tight rows with a 

235 zero multiplier stay inactive, and assets on a bound with a zero reduced cost 

236 are freed, in order of decreasing return, until the free block of the active 

237 rows is square and nonsingular. The segment then reproduces the vertex, and the 

238 multipliers it implies are those of the dual vertex, which carry the right 

239 signs. This generalises the greedy fill of :func:`init_algo`, which marks its 

240 last asset free even when it lands on a bound. 

241 

242 Args: 

243 weights: The vertex weights. 

244 lower_bounds: Lower box bounds. 

245 upper_bounds: Upper box bounds. 

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

247 g: Inequality-constraint matrix (``p x n``); empty ``(0, n)`` when none. 

248 h: Inequality-constraint right-hand side (length ``p``). 

249 tol: Classification tolerance. 

250 duals: An optimal dual solution of the linear program, or ``None`` to 

251 classify without resolving degeneracy. 

252 

253 Returns: 

254 The vertex as a :class:`TurningPoint` carrying its active rows. 

255 

256 Raises: 

257 DegenerateProblemError: If the vertex is degenerate and cannot be resolved. 

258 """ 

259 free = (weights > lower_bounds + tol) & (weights < upper_bounds - tol) 

260 active_ineq = (g @ weights >= h - tol) if g.shape[0] else np.zeros(0, dtype=bool) 

261 

262 if duals is not None and not _spans(np.vstack([a, g[active_ineq]]), free): 

263 free, active_ineq = _resolve_vertex(weights, lower_bounds, upper_bounds, a, g, tol, free, active_ineq, duals) 

264 

265 reject_degenerate_vertex(a, g, free, active_ineq) 

266 return TurningPoint(free=free, weights=weights, active_ineq=active_ineq) 

267 

268 

269def _spans(c: NDArray[np.float64], free: NDArray[np.bool_]) -> bool: 

270 """Whether the free block ``c[:, free]`` has full row rank. 

271 

272 ``rank(C[:, free]) <= min(rows, n_free)``, so fewer free assets than rows fails 

273 by itself. Testing this first also keeps ``matrix_rank`` off a zero-column 

274 block, whose empty singular-value reduction raises on numpy 2.0. No rows are 

275 spanned by any free set, including the empty one of a box-only vertex, so that 

276 case returns before ``matrix_rank`` sees a ``0 x 0`` block (which raises on 

277 numpy < 2.5). 

278 

279 Args: 

280 c: The active constraint rows (``[A ; G_active]``). 

281 free: Boolean mask of the free assets. 

282 

283 Returns: 

284 ``True`` when the free assets span the rows. 

285 """ 

286 rows = c.shape[0] 

287 if rows == 0: 

288 return True 

289 return bool(int(np.count_nonzero(free)) >= rows and int(np.linalg.matrix_rank(c[:, free])) == rows) 

290 

291 

292def _resolve_vertex( 

293 weights: NDArray[np.float64], 

294 lower_bounds: NDArray[np.float64], 

295 upper_bounds: NDArray[np.float64], 

296 a: NDArray[np.float64], 

297 g: NDArray[np.float64], 

298 tol: float, 

299 free: NDArray[np.bool_], 

300 tight: NDArray[np.bool_], 

301 duals: VertexDuals, 

302) -> tuple[NDArray[np.bool_], NDArray[np.bool_]]: 

303 """Choose the free set and the active rows of a degenerate vertex from its optimal duals. 

304 

305 Args: 

306 weights: The vertex weights. 

307 lower_bounds: Lower box bounds. 

308 upper_bounds: Upper box bounds. 

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

310 g: Inequality-constraint matrix (``p x n``). 

311 tol: Classification tolerance. 

312 free: Boolean mask of the assets strictly inside their box. 

313 tight: Boolean mask of the tight rows of ``g``. 

314 duals: An optimal dual solution of the linear program. 

315 

316 Returns: 

317 ``(free, active_ineq)``: the completed free set and the active rows of ``g``. 

318 """ 

319 m = a.shape[0] 

320 rows = np.vstack([a, g[tight]]) 

321 # The sign the reduced cost keeps on a bound: +1 on an upper bound, -1 on a 

322 # lower one, and none for an asset pinned at both (it is never freed). 

323 sign = (~free & (weights >= upper_bounds - tol)).astype(np.float64) - ( 

324 ~free & (weights <= lower_bounds + tol) 

325 ).astype(np.float64) 

326 # The equality multipliers follow from the rest; the rows are independent. 

327 eta = np.maximum(duals.ineq[tight], 0.0) 

328 nu = np.linalg.lstsq(a.T, duals.mean - duals.gap - g[tight].T @ eta, rcond=None)[0] 

329 y = _dual_vertex(rows, duals.mean, free, sign, m, np.r_[nu, eta], duals.tol) 

330 gap = duals.mean - rows.T @ y 

331 freed, released = vertex_partition( 

332 rows, 

333 free, 

334 (sign != 0) & (sign * gap <= duals.tol), 

335 (np.arange(rows.shape[0]) >= m) & (y <= duals.tol), 

336 -duals.mean, 

337 ) 

338 active_ineq = tight.copy() 

339 active_ineq[tight] = ~released[m:] 

340 return free | freed, active_ineq 

341 

342 

343def _dual_vertex( 

344 rows: NDArray[np.float64], 

345 mean: NDArray[np.float64], 

346 free: NDArray[np.bool_], 

347 sign: NDArray[np.float64], 

348 m: int, 

349 start: NDArray[np.float64], 

350 tol: float, 

351) -> NDArray[np.float64]: 

352 """Move an optimal dual solution to a vertex of the optimal dual set. 

353 

354 The multipliers ``y`` of the rows ``C = [A ; G_tight]`` are optimal when 

355 ``gap = mean - C^T y`` vanishes on the free assets, has the ``sign`` of each 

356 bound on the others (``sign * gap >= 0``; no condition where ``sign`` is zero) 

357 and the inequality multipliers ``y[m:]`` are non-negative. While the 

358 constraints tight at ``y`` do not determine it, ``y`` moves along a direction 

359 that keeps them tight until another one becomes tight; each move adds a 

360 constraint independent of the tight ones, so at most ``len(y)`` moves reach a 

361 vertex. The solver's own dual need not be one: at a degenerate vertex it can 

362 sit inside a face of the optimal set. 

363 

364 Args: 

365 rows: The tight constraint rows ``C`` (``k x n``), equalities first. 

366 mean: Vector of expected returns. 

367 free: Boolean mask of the assets strictly inside their box. 

368 sign: ``+1`` on an upper bound, ``-1`` on a lower bound, ``0`` otherwise. 

369 m: Number of equality rows (the leading rows of ``C``). 

370 start: An optimal dual solution (length ``k``). 

371 tol: Zero tolerance for the duals. 

372 

373 Returns: 

374 The multipliers at a vertex of the optimal dual set. 

375 

376 Raises: 

377 DegenerateProblemError: If the optimal dual set has no vertex (the assets 

378 that can leave their bounds do not determine the multipliers). 

379 """ 

380 k = rows.shape[0] 

381 y = start.copy() 

382 ineq = np.arange(k) >= m 

383 for _ in range(k + 1): 

384 gap = mean - rows.T @ y 

385 tight = np.hstack([rows[:, free | ((sign != 0) & (sign * gap <= tol))], np.eye(k)[:, ineq & (y <= tol)]]) 

386 # A zero row keeps the factorisation defined when nothing is tight yet. 

387 _, sv, vt = np.linalg.svd(np.vstack([tight.T, np.zeros(k)])) 

388 rank = int(np.count_nonzero(sv > k * np.finfo(np.float64).eps * max(float(sv[0]), 1.0))) 

389 if rank == k: 

390 return y 

391 step = _dual_step(rows, gap, y, sign, ineq, vt[rank]) 

392 if step is None: 

393 break 

394 y = y + step 

395 msg = ( 

396 "The maximum-return vertex is degenerate and its optimal duals have no vertex: the assets " 

397 "that can leave their bounds do not determine the multipliers of the active rows. Perturb " 

398 "the bounds or the constraints so the maximum-return vertex is non-degenerate." 

399 ) 

400 raise DegenerateProblemError(msg) 

401 

402 

403def _dual_step( 

404 rows: NDArray[np.float64], 

405 gap: NDArray[np.float64], 

406 y: NDArray[np.float64], 

407 sign: NDArray[np.float64], 

408 ineq: NDArray[np.bool_], 

409 direction: NDArray[np.float64], 

410) -> NDArray[np.float64] | None: 

411 """The move along ``+direction`` or ``-direction`` until a further dual constraint is tight. 

412 

413 Along ``y + t d`` the constraint value ``sign_i * gap_i`` of asset ``i`` falls at 

414 rate ``sign_i c_i^T d`` and the multiplier of an inequality row at rate 

415 ``-d_j``; the first value to reach zero ends the move. ``+d`` is tried first. 

416 

417 Args: 

418 rows: The tight constraint rows ``C`` (``k x n``). 

419 gap: The current reduced costs ``mean - C^T y``. 

420 y: The current multipliers. 

421 sign: ``+1`` on an upper bound, ``-1`` on a lower bound, ``0`` otherwise. 

422 ineq: Boolean mask of the inequality rows among the ``k``. 

423 direction: A unit direction that keeps every tight constraint tight. 

424 

425 Returns: 

426 The step ``t d``, or ``None`` when neither direction meets a constraint. 

427 """ 

428 floor = float(np.sqrt(np.finfo(np.float64).eps)) 

429 scale = np.maximum(np.linalg.norm(rows, axis=0), 1.0) 

430 for d in (direction, -direction): 

431 rate_asset = sign * (rows.T @ d) 

432 rate_row = np.where(ineq, -d, 0.0) 

433 moving = rate_asset > floor * scale 

434 falling = rate_row > floor 

435 steps = np.r_[(sign * gap)[moving] / rate_asset[moving], y[falling] / rate_row[falling]] 

436 if steps.size: 

437 return float(np.min(np.maximum(steps, 0.0))) * d 

438 return None 

439 

440 

441def vertex_partition( 

442 rows: NDArray[np.float64], 

443 free: NDArray[np.bool_], 

444 candidates: NDArray[np.bool_], 

445 releasable: NDArray[np.bool_], 

446 key: NDArray[np.float64], 

447) -> tuple[NDArray[np.bool_], NDArray[np.bool_]]: 

448 """Read a partition off a vertex of the optimal dual set. 

449 

450 The constraints tight at a dual vertex span the multiplier space, so a basis 

451 can be drawn from them: the free assets' columns of ``C`` first, then the unit 

452 vectors of the zero-multiplier inequality rows, then the columns of the 

453 zero-reduced-cost assets in order of ``key``, each kept while it raises the 

454 rank. Rows whose unit vector is in the basis are released (inactive), assets 

455 whose column is in the basis are freed, and the free block of the remaining 

456 rows is square and nonsingular. 

457 

458 Args: 

459 rows: The tight constraint rows ``C`` (``k x n``). 

460 free: Boolean mask of the assets strictly inside their box. 

461 candidates: Assets on a bound with zero reduced cost. 

462 releasable: Rows (of the ``k``) that are inequalities with a zero multiplier. 

463 key: Ordering key; smaller values are freed first. 

464 

465 Returns: 

466 ``(freed, released)``: the assets to free and the rows to release. 

467 """ 

468 k = rows.shape[0] 

469 order = np.flatnonzero(candidates)[np.argsort(key[candidates], kind="stable")] 

470 basis = rows[:, free] 

471 rank = int(np.linalg.matrix_rank(basis)) if basis.shape[1] else 0 

472 freed = np.zeros_like(free) 

473 released = np.zeros(k, dtype=bool) 

474 columns = [(np.eye(k)[:, j], released, j) for j in np.flatnonzero(releasable)] 

475 columns += [(rows[:, i], freed, i) for i in order] 

476 for column, chosen, index in columns: 

477 trial = np.column_stack([basis, column]) 

478 if int(np.linalg.matrix_rank(trial)) > rank: 

479 basis, rank = trial, rank + 1 

480 chosen[index] = True 

481 return freed, released 

482 

483 

484# Equality rows whose row-normalised reciprocal condition number is below this are 

485# nearly dependent enough that the linear program enforces the direction they carry 

486# only loosely; they are restated in an orthonormal basis first. Above it the rows go 

487# in as given, so a well-conditioned problem hands HiGHS the system the user wrote. 

488_LP_ROW_RCOND = 1e-6 # pragma: no mutate 

489 

490 

491def _lp_equalities(a: NDArray[np.float64], b: NDArray[np.float64]) -> tuple[NDArray[np.float64], NDArray[np.float64]]: 

492 """The equality system handed to the linear program: ``(a, b)``, or orthonormal rows if nearly dependent. 

493 

494 Two nearly parallel rows (``1^T w = 1`` and ``(1 + eps v)^T w = 1``) carry the 

495 constraint ``v^T w = 0`` only at scale ``eps``, and an absolute feasibility 

496 tolerance enforces it to ``tol / eps``; from ``eps ~ 1e-7`` the vertex comes back 

497 infeasible for the hidden row and is misread as degenerate. The orthonormal form 

498 ``Q^T w = R^{-T} b`` (:func:`cvxcla.operators.orthonormal_rows`) has the same 

499 feasible set with every direction at unit scale. 

500 

501 Args: 

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

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

504 

505 Returns: 

506 The rows and right-hand side to pass to ``linprog``. 

507 """ 

508 if a.shape[0] < 2: 

509 return a, b 

510 norms = np.linalg.norm(a, axis=1, keepdims=True) 

511 sv = np.linalg.svd(a / np.where(norms > 0, norms, 1.0), compute_uv=False) 

512 if sv[-1] >= _LP_ROW_RCOND * sv[0]: 

513 return a, b 

514 return orthonormal_rows(a, b) 

515 

516 

517def _solve_max_return_lp( 

518 mean: NDArray[np.float64], 

519 lower_bounds: NDArray[np.float64], 

520 upper_bounds: NDArray[np.float64], 

521 a: NDArray[np.float64], 

522 b: NDArray[np.float64], 

523 g: NDArray[np.float64], 

524 h: NDArray[np.float64], 

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

526 """Solve the maximum-return linear program and return its vertex weights and duals. 

527 

528 ``maximize mean @ w`` (as ``minimize -mean @ w``) subject to ``A w = b``, 

529 ``G w <= h`` and the box bounds, via HiGHS. The inequality rows are passed 

530 only when ``g`` is non-empty. 

531 

532 Args: 

533 mean: Vector of expected returns. 

534 lower_bounds: Lower box bounds. 

535 upper_bounds: Upper box bounds. 

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

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

538 g: Inequality-constraint matrix (``p x n``); empty ``(0, n)`` when none. 

539 h: Inequality-constraint right-hand side (length ``p``). 

540 

541 Returns: 

542 ``(w, gap, eta)``: the vertex weights, the reduced cost of each variable 

543 (the bound marginals, zero for a basic variable) and the inequality 

544 multipliers, in the signs of :class:`VertexDuals`. 

545 

546 Raises: 

547 InfeasibleProblemError: If the linear program is infeasible. 

548 DegenerateProblemError: If it is unbounded (no maximum-return vertex). 

549 NumericalError: If HiGHS stops for another reason. 

550 """ 

551 has_ineq = g.shape[0] > 0 

552 a_eq, b_eq = _lp_equalities(np.asarray(a, dtype=np.float64), np.asarray(b, dtype=np.float64)) 

553 result = linprog( 

554 c=-np.asarray(mean, dtype=np.float64), 

555 A_eq=a_eq, 

556 b_eq=b_eq, 

557 A_ub=g if has_ineq else None, 

558 b_ub=h if has_ineq else None, 

559 bounds=list(zip(lower_bounds, upper_bounds, strict=True)), 

560 method="highs", 

561 ) 

562 if not result.success: 

563 msg = f"Could not find a maximum-return vertex (linear program: {result.message})" 

564 error = {2: InfeasibleProblemError, 3: DegenerateProblemError}.get(result.status, NumericalError) 

565 raise error(msg) 

566 # HiGHS reports the marginals of the minimisation, ``-mean = A^T y + G^T z + s``; 

567 # the gap and the inequality multipliers of the maximisation are their negatives. 

568 gap = -(np.asarray(result.lower.marginals, dtype=np.float64) + np.asarray(result.upper.marginals, dtype=np.float64)) 

569 eta = -np.asarray(result.ineqlin.marginals, dtype=np.float64) if has_ineq else np.zeros(0) 

570 return np.asarray(result.x, dtype=np.float64), gap, eta 

571 

572 

573def reject_degenerate_vertex( 

574 a: NDArray[np.float64], 

575 g: NDArray[np.float64], 

576 free: NDArray[np.bool_], 

577 active_ineq: NDArray[np.bool_], 

578) -> None: 

579 """Decline a maximum-return vertex whose free set cannot span the active rows. 

580 

581 The free set must span the equality rows together with the active inequality 

582 rows: ``C = [A ; G_active]`` restricted to the free assets must have full row 

583 rank, or the reduced KKT solve is singular. A degenerate maximum-return 

584 vertex (a basic asset pinned on a bound) violates this; decline it with an 

585 actionable diagnosis instead of letting it surface as an opaque "Singular 

586 matrix" error downstream. 

587 

588 Args: 

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

590 g: Inequality-constraint matrix (``p x n``); empty ``(0, n)`` when none. 

591 free: Boolean mask of the assets strictly inside their box bounds. 

592 active_ineq: Boolean mask of the tight (active) inequality rows. 

593 

594 Raises: 

595 DegenerateProblemError: If the free set does not span the active equality 

596 and inequality rows. 

597 """ 

598 c = np.vstack([a, g[active_ineq]]) 

599 mc = c.shape[0] 

600 n_free = int(np.count_nonzero(free)) 

601 if not _spans(c, free): 

602 msg = ( 

603 f"The maximum-return vertex is degenerate (free-set size {n_free}, " 

604 f"active constraints {mc}): a basic asset sits exactly on a box bound, so the free set " 

605 "does not span the active equality and inequality rows and the reduced KKT system is " 

606 "singular, even after freeing the vertex's degenerate basic assets. Perturb the bounds or " 

607 "the constraints so the maximum-return vertex is non-degenerate." 

608 ) 

609 raise DegenerateProblemError(msg) 

610 

611 

612def _free( 

613 w: NDArray[np.float64], lower_bounds: NDArray[np.float64], upper_bounds: NDArray[np.float64] 

614) -> NDArray[np.bool_]: 

615 """Determine which asset should be free in the turning point. 

616 

617 This helper function identifies the asset that should be marked as free 

618 in the turning point. It selects the asset that is furthest from its bounds, 

619 which helps ensure numerical stability in the algorithm. 

620 

621 Args: 

622 w: Vector of portfolio weights. 

623 lower_bounds: Vector of lower bounds for asset weights. 

624 upper_bounds: Vector of upper bounds for asset weights. 

625 

626 Returns: 

627 A boolean vector indicating which asset is free (True) and which are blocked (False). 

628 

629 """ 

630 # Calculate the distance from each weight to its nearest bound 

631 distance = np.min(np.array([np.abs(w - lower_bounds), np.abs(upper_bounds - w)]), axis=0) 

632 

633 # Find the index of the asset furthest from its bounds 

634 index = np.argmax(distance) 

635 

636 # Create a boolean vector with only that asset marked as free 

637 free = np.full_like(w, False, dtype=np.bool_) 

638 free[index] = True 

639 return free