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

1"""Feasibility projection for Critical Line Algorithm turning points. 

2 

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}``. 

9 

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

14 

15from __future__ import annotations 

16 

17import numpy as np 

18from cvx.linalg import AffineProjection 

19from numpy.typing import NDArray 

20 

21from .errors import ProjectionError 

22from .operators import orthonormal_rows 

23 

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 

36 

37 

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. 

49 

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

56 

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. 

66 

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 

74 

75 if _is_capped_simplex(active_ineq, a): 

76 return project_capped_simplex(weights, lower, upper, float(b[0])) 

77 

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) 

81 

82 

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. 

85 

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

89 

90 Args: 

91 active_ineq: Boolean mask of the active inequality rows. 

92 a: Equality-constraint matrix ``A``. 

93 

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

98 

99 

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. 

107 

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. 

114 

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

120 

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) 

137 

138 

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. 

146 

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. 

153 

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

159 

160 Returns: 

161 The finite bracket ``(theta_lo, theta_hi)``. 

162 """ 

163 theta_0 = float((weights.sum() - budget) / weights.size) 

164 

165 def total(theta: float) -> float: 

166 return float(np.clip(weights - theta, lower, upper).sum()) 

167 

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 

172 

173 

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}``. 

182 

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

190 

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. 

197 

198 Returns: 

199 The projected weight vector, feasible to the box and the constraints. 

200 

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) 

226 

227 

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