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
« 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.
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"""
8from __future__ import annotations
10from typing import NamedTuple
12import numpy as np
13from numpy.typing import NDArray
14from scipy.optimize import linprog # type: ignore[import-untyped]
16from .errors import DegenerateProblemError, InfeasibleProblemError, NumericalError
17from .operators import orthonormal_rows
18from .types import TurningPoint
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.
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``.
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.
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).
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)
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_)
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
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)
83 # Return first turning point, the point with the highest expected return.
84 return TurningPoint(free=free, weights=weights)
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.
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).
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``).
119 Returns:
120 The maximum-return vertex as a :class:`TurningPoint`, carrying the active
121 inequality rows in ``active_ineq``.
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`.
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)
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 )
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.
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.
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.
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)
192class VertexDuals(NamedTuple):
193 """An optimal dual solution of the maximum-return linear program.
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.
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 """
207 mean: NDArray[np.float64]
208 gap: NDArray[np.float64]
209 ineq: NDArray[np.float64]
210 tol: float
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.
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`).
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.
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.
253 Returns:
254 The vertex as a :class:`TurningPoint` carrying its active rows.
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)
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)
265 reject_degenerate_vertex(a, g, free, active_ineq)
266 return TurningPoint(free=free, weights=weights, active_ineq=active_ineq)
269def _spans(c: NDArray[np.float64], free: NDArray[np.bool_]) -> bool:
270 """Whether the free block ``c[:, free]`` has full row rank.
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).
279 Args:
280 c: The active constraint rows (``[A ; G_active]``).
281 free: Boolean mask of the free assets.
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)
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.
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.
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
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.
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.
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.
373 Returns:
374 The multipliers at a vertex of the optimal dual set.
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)
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.
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.
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.
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
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.
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.
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.
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
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
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.
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.
501 Args:
502 a: Equality-constraint matrix (``m x n``).
503 b: Equality-constraint right-hand side (length ``m``).
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)
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.
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.
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``).
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`.
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
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.
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.
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.
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)
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.
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.
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.
626 Returns:
627 A boolean vector indicating which asset is free (True) and which are blocked (False).
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)
633 # Find the index of the asset furthest from its bounds
634 index = np.argmax(distance)
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