Coverage for src/cvxcla/_projection.py: 100%
51 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"""Feasibility projection for Critical Line Algorithm turning points.
3Accumulated floating-point round-off over the many turning points of a long
4trace can place a candidate a hair outside its box even at a well-conditioned
5vertex: the covariance there has near-flat directions (its small eigenvalues)
6and the round-off lies in exactly those directions, so the candidate is optimal
7to solver precision but not exactly feasible. These pure helpers project such a
8candidate back onto the feasible region ``{w : lower <= w <= upper, C w = d}``.
10They are a strict no-op for the well-posed, already-feasible turning points that
11are the common case, so they never perturb the exact frontier. ``CLA._emit``
12calls :func:`project_feasible` at every turning point.
13"""
15from __future__ import annotations
17import numpy as np
18from cvx.linalg import AffineProjection
19from numpy.typing import NDArray
21from .errors import ProjectionError
22from .operators import orthonormal_rows
24# Alternating projections stop once the iterate violates its box by at most this
25# much (weights are portfolio fractions, so the scale is 1); the affine step keeps
26# C w = d to round-off throughout.
27_PROJECTION_TOL = 1e-12 # pragma: no mutate
28_PROJECTION_MAX_ITER = 100 # pragma: no mutate
29# If the iterations stall short of _PROJECTION_TOL but within this, the clipped point
30# is accepted: the remaining violation is round-off, far inside the turning-point
31# validation tolerance. Only a larger violation means the projection failed.
32_PROJECTION_ACCEPT = float(np.sqrt(np.finfo(np.float64).eps)) # pragma: no mutate
33# The capped-simplex bracket doubles its half-width up to this; far beyond any weight
34# scale, it only bounds the loop for an infeasible budget.
35_BRACKET_MAX_STEP = 2.0**64 # pragma: no mutate
38def project_feasible(
39 weights: NDArray[np.float64],
40 lower: NDArray[np.float64],
41 upper: NDArray[np.float64],
42 a: NDArray[np.float64],
43 b: NDArray[np.float64],
44 g: NDArray[np.float64],
45 h: NDArray[np.float64],
46 active_ineq: NDArray[np.bool_],
47) -> NDArray[np.float64]:
48 """Project ``weights`` onto the feasible region, clearing round-off.
50 Well-posed turning points are already strictly feasible and are returned
51 unchanged so the projection never perturbs the exact frontier. Otherwise the
52 candidate is dispatched to the closed-form capped-simplex projection for the
53 canonical all-ones budget with no active inequality row (see
54 :func:`project_capped_simplex`), and to the general alternating projection
55 otherwise (see :func:`project_alternating`).
57 Args:
58 weights: The candidate weight vector to project.
59 lower: Per-asset lower bounds.
60 upper: Per-asset upper bounds.
61 a: Equality-constraint matrix ``A`` of ``A w = b``.
62 b: Equality-constraint right-hand side ``b``.
63 g: Inequality-constraint matrix ``G`` of ``G w <= h`` (``(p, n)``).
64 h: Inequality-constraint right-hand side ``h`` (length ``p``).
65 active_ineq: Boolean mask (length ``p``) of the active inequality rows.
67 Returns:
68 The projected weight vector, feasible to the box and the constraints.
69 """
70 # Well-posed turning points are already strictly feasible: return them
71 # unchanged so the projection never perturbs the exact frontier.
72 if np.all(weights >= lower) and np.all(weights <= upper):
73 return weights
75 if _is_capped_simplex(active_ineq, a):
76 return project_capped_simplex(weights, lower, upper, float(b[0]))
78 c = np.vstack([a, g[active_ineq]])
79 d = np.concatenate([b, h[active_ineq]])
80 return project_alternating(weights, lower, upper, c, d)
83def _is_capped_simplex(active_ineq: NDArray[np.bool_], a: NDArray[np.float64]) -> bool:
84 """Whether the projection reduces to the closed-form capped simplex.
86 True when no inequality row is active and the equality is the canonical
87 all-ones budget (a single row of ones), the case handled by
88 :func:`project_capped_simplex`.
90 Args:
91 active_ineq: Boolean mask of the active inequality rows.
92 a: Equality-constraint matrix ``A``.
94 Returns:
95 ``True`` if the closed-form capped-simplex projection applies.
96 """
97 return not active_ineq.any() and a.shape[0] == 1 and bool(np.allclose(a, 1.0))
100def project_capped_simplex(
101 weights: NDArray[np.float64],
102 lower: NDArray[np.float64],
103 upper: NDArray[np.float64],
104 budget: float,
105) -> NDArray[np.float64]:
106 """Euclidean projection onto the capped simplex for the all-ones budget.
108 Computed by water-filling a single shift ``theta`` so that
109 ``sum(clip(w - theta, lower, upper)) = budget``. A plain clip-then-rescale is
110 deliberately *not* used: rescaling the clipped weights to restore the budget
111 can push capped weights back over their bound when many assets are capped at
112 once (heavy ties under a tight cap), re-introducing the very infeasibility
113 the projection is meant to clear.
115 Args:
116 weights: The candidate weight vector, known to violate its box.
117 lower: Per-asset lower bounds.
118 upper: Per-asset upper bounds.
119 budget: The all-ones budget right-hand side ``sum(w)``.
121 Returns:
122 The projected weight vector, on the budget and inside the box.
123 """
124 # sum(clip(w - theta, lower, upper)) is non-increasing in theta; bisect
125 # for the theta that hits the budget. The bracket is taken around the
126 # unclipped shift and widened by doubling rather than read off the bounds,
127 # which may be infinite (an uncapped long-only problem would otherwise put
128 # theta_lo at -inf and return inf weights).
129 theta_lo, theta_hi = _bracket_shift(weights, lower, upper, budget)
130 for _ in range(100):
131 theta = 0.5 * (theta_lo + theta_hi)
132 if float(np.clip(weights - theta, lower, upper).sum()) > budget:
133 theta_lo = theta
134 else:
135 theta_hi = theta
136 return np.clip(weights - 0.5 * (theta_lo + theta_hi), lower, upper)
139def _bracket_shift(
140 weights: NDArray[np.float64],
141 lower: NDArray[np.float64],
142 upper: NDArray[np.float64],
143 budget: float,
144) -> tuple[float, float]:
145 """Return a finite ``(theta_lo, theta_hi)`` bracketing the capped-simplex shift.
147 Starts from the shift ``theta_0`` that meets the budget before clipping and
148 widens each side by doubling until ``sum(clip(w - theta_lo)) >= budget`` and
149 ``sum(clip(w - theta_hi)) <= budget``. Infinite bounds on either side are fine:
150 the clipped sum then grows without limit in that direction, so the doubling stops.
151 For a feasible problem (``sum(lower) <= budget <= sum(upper)``) a root lies in
152 the bracket; the doubling is capped so an infeasible one cannot loop forever.
154 Args:
155 weights: The candidate weight vector.
156 lower: Per-asset lower bounds.
157 upper: Per-asset upper bounds.
158 budget: The all-ones budget right-hand side ``sum(w)``.
160 Returns:
161 The finite bracket ``(theta_lo, theta_hi)``.
162 """
163 theta_0 = float((weights.sum() - budget) / weights.size)
165 def total(theta: float) -> float:
166 return float(np.clip(weights - theta, lower, upper).sum())
168 step = 1.0
169 while (total(theta_0 - step) < budget or total(theta_0 + step) > budget) and step < _BRACKET_MAX_STEP:
170 step *= 2.0
171 return theta_0 - step, theta_0 + step
174def project_alternating(
175 weights: NDArray[np.float64],
176 lower: NDArray[np.float64],
177 upper: NDArray[np.float64],
178 c: NDArray[np.float64],
179 d: NDArray[np.float64],
180) -> NDArray[np.float64]:
181 """Alternating projection onto the box and the affine set ``{C w = d}``.
183 ``C`` stacks the equality rows ``A`` and the active inequality rows ``G_S``
184 (held at equality ``g_i w = h_i``). The candidate already satisfies
185 ``C w = d`` (the reduced KKT solve enforces it) and the inactive inequality
186 rows keep a margin, so alternating a box clip with the affine projection
187 converges to a point feasible to the box, the equalities, and every
188 inequality, usually in one iteration. The loop stops as soon as the iterate
189 violates its box by at most ``_PROJECTION_TOL``.
191 Args:
192 weights: The candidate weight vector, known to violate its box.
193 lower: Per-asset lower bounds.
194 upper: Per-asset upper bounds.
195 c: Stacked equality/active-inequality matrix.
196 d: Stacked equality/active-inequality right-hand side.
198 Returns:
199 The projected weight vector, feasible to the box and the constraints.
201 Raises:
202 ProjectionError: If ``_PROJECTION_MAX_ITER`` iterations leave the iterate
203 outside its box by more than ``_PROJECTION_ACCEPT`` (``sqrt(eps)``);
204 the message reports the remaining box violation and equality residual.
205 A stall between ``_PROJECTION_TOL`` and ``_PROJECTION_ACCEPT`` is
206 round-off, and the clipped point is returned.
207 """
208 # The same affine set in orthonormal rows: nearly dependent active rows would
209 # otherwise make the Gram matrix C C^T singular to working precision.
210 affine = AffineProjection(*orthonormal_rows(c, d))
211 projected = weights
212 for _ in range(_PROJECTION_MAX_ITER):
213 projected = affine.project(np.clip(projected, lower, upper))
214 if _box_violation(projected, lower, upper) <= _PROJECTION_TOL:
215 return np.clip(projected, lower, upper)
216 violation = _box_violation(projected, lower, upper)
217 if violation <= _PROJECTION_ACCEPT:
218 return np.clip(projected, lower, upper)
219 residual = float(np.max(np.abs(c @ projected - d), initial=0.0))
220 msg = (
221 f"feasibility projection did not converge in {_PROJECTION_MAX_ITER} iterations: "
222 f"box violation {violation:.1e}, equality residual {residual:.1e}. The free block is "
223 "likely near-singular; a small ridge or a factor model usually cures it."
224 )
225 raise ProjectionError(msg)
228def _box_violation(weights: NDArray[np.float64], lower: NDArray[np.float64], upper: NDArray[np.float64]) -> float:
229 """Return how far ``weights`` lie outside ``[lower, upper]`` (``0`` inside the box)."""
230 return float(np.max(np.maximum(np.maximum(lower - weights, weights - upper), 0.0), initial=0.0))