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

49 statements  

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

1"""Critical-lambda event scans for the Critical Line Algorithm. 

2 

3Along a critical-line segment ``w(lam) = r_alpha + lam * r_beta`` two families of 

4events end the segment's validity: a *box* event (a free weight reaching a bound, 

5or a blocked weight's multiplier changing sign) and an *inequality-row* event (an 

6inactive ``G w <= h`` row's slack reaching zero, or an active row's multiplier 

7changing sign). Both reduce to the same ``-intercept / slope`` critical-lambda 

8ratio, computed here as pure functions and stacked by :func:`segment_events` into 

9the ``(n + p, 4)`` matrix the generic path tracer scans. 

10""" 

11 

12from __future__ import annotations 

13 

14import numpy as np 

15from numpy.typing import NDArray 

16 

17from ._kkt import Segment 

18 

19 

20def event_ratios( 

21 r_alpha: NDArray[np.float64], 

22 r_beta: NDArray[np.float64], 

23 gamma: NDArray[np.float64], 

24 delta: NDArray[np.float64], 

25 free_in: NDArray[np.bool_], 

26 at_upper: NDArray[np.bool_], 

27 at_lower: NDArray[np.bool_], 

28 lower: NDArray[np.float64], 

29 upper: NDArray[np.float64], 

30 beta_floor: float | None = None, 

31 delta_floor: float | None = None, 

32) -> NDArray[np.float64]: 

33 """Critical lambda for every candidate box event, as an ``(n, 4)`` matrix. 

34 

35 Along the segment ``w(lam) = r_alpha + lam * r_beta`` a free weight can 

36 reach a box bound (columns 0/1, "moves to a bound") and a blocked weight's 

37 multiplier can change sign so it re-enters the free set (columns 2/3, 

38 "leaves a bound"). Entries with no event are ``-inf``. 

39 

40 A free weight moves with even a tiny slope, so given a long enough lam 

41 range it still crosses a bound; filtering slopes at the classification 

42 tolerance would miss such crossings and let weights drift out of bounds. 

43 Only slopes at floating-point noise level are excluded: below 

44 ``sqrt(machine epsilon)`` a slope is indistinguishable from solve noise, and 

45 the huge ratios it would produce only amplify rounding errors. 

46 

47 Args: 

48 r_alpha: Segment intercept ``w(0)``. 

49 r_beta: Segment slope ``dw/dlam``. 

50 gamma: Multiplier gradient for the alpha system. 

51 delta: Multiplier gradient for the beta system. 

52 free_in: Mask of assets in the reduced solve. 

53 at_upper: Mask of assets blocked at their upper bound. 

54 at_lower: Mask of assets blocked at their lower bound. 

55 lower: Per-asset lower bounds. 

56 upper: Per-asset upper bounds. 

57 beta_floor: Smallest weight slope treated as genuine; ``None`` uses 

58 ``sqrt(machine eps)``. :func:`segment_events` scales it with the problem. 

59 delta_floor: Smallest multiplier slope treated as genuine; ``None`` uses 

60 ``sqrt(machine eps)``. 

61 

62 Returns: 

63 The ``(n, 4)`` matrix of critical lambdas. 

64 """ 

65 ns = len(r_alpha) 

66 eps = np.sqrt(np.finfo(np.float64).eps) 

67 beta_eps = eps if beta_floor is None else beta_floor 

68 delta_eps = eps if delta_floor is None else delta_floor 

69 # 4 columns = the 4 event types; extra unused columns are harmless. 

70 l_mat = np.full((ns, 4), -np.inf) # pragma: no mutate 

71 

72 # Precompute each event mask exactly once. The <,> vs <=,>= choice at 

73 # the eps boundary is numerically irrelevant — a slope/derivative 

74 # landing exactly on +/-sqrt(machine-eps) never occurs with real 

75 # data — so those boundary comparisons are marked no-mutate. 

76 beta_down = free_in & (r_beta < -beta_eps) # pragma: no mutate 

77 beta_up = free_in & (r_beta > +beta_eps) # pragma: no mutate 

78 delta_down = at_upper & (delta < -delta_eps) # pragma: no mutate 

79 delta_up = at_lower & (delta > +delta_eps) # pragma: no mutate 

80 

81 # Columns 0,1 are "moves to a bound" (free->blocked) and 2,3 are 

82 # "leaves a bound" (blocked->free); the next-free update only tests 

83 # dirchg >= 2, so swapping a column *within* a group (0<->1 or 2<->3) is 

84 # behaviourally identical and marked no-mutate. Crossing the 1<->2 group 

85 # boundary IS exercised by the frontier tests. 

86 l_mat[beta_down, 0] = (upper[beta_down] - r_alpha[beta_down]) / r_beta[beta_down] # pragma: no mutate 

87 l_mat[beta_up, 1] = (lower[beta_up] - r_alpha[beta_up]) / r_beta[beta_up] 

88 l_mat[delta_down, 2] = -gamma[delta_down] / delta[delta_down] # pragma: no mutate 

89 l_mat[delta_up, 3] = -gamma[delta_up] / delta[delta_up] 

90 return l_mat 

91 

92 

93def ineq_event_ratios( 

94 r_alpha: NDArray[np.float64], 

95 r_beta: NDArray[np.float64], 

96 eta_alpha: NDArray[np.float64], 

97 eta_beta: NDArray[np.float64], 

98 active_ineq: NDArray[np.bool_], 

99 g: NDArray[np.float64], 

100 h: NDArray[np.float64], 

101 slack_floor: float | None = None, 

102 eta_floor: float | None = None, 

103) -> NDArray[np.float64]: 

104 """Critical lambda for every inequality-row event, as a ``(p, 4)`` matrix. 

105 

106 The row analogue of :func:`event_ratios`. Along the segment an *inactive* 

107 row ``i`` becomes active when its slack ``s_i(lam) = g_i w(lam) - h_i`` 

108 rises to zero from the feasible (negative) side (column 0); an *active* 

109 row releases when its multiplier ``eta_i(lam)`` falls to zero (column 1). 

110 Both are affine in ``lam``, so the critical lambda is the same 

111 ``-intercept / slope`` ratio used for the box events, with the same 

112 ``sqrt(machine eps)`` slope floor: a slope below noise level is 

113 indistinguishable from solve round-off and would only produce a huge, 

114 rounding-dominated ratio. Entries with no event are ``-inf``. Columns 2 

115 and 3 are unused (kept so the block stacks onto the ``(n, 4)`` box block). 

116 

117 Args: 

118 r_alpha: Segment intercept ``w(0)``. 

119 r_beta: Segment slope ``dw/dlam``. 

120 eta_alpha: Affine inequality-multiplier intercept (length ``p``). 

121 eta_beta: Affine inequality-multiplier slope (length ``p``). 

122 active_ineq: Boolean mask (length ``p``) of the active inequality rows. 

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

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

125 slack_floor: Smallest slack slope treated as genuine; ``None`` uses 

126 ``sqrt(machine eps)``. 

127 eta_floor: Smallest row-multiplier slope treated as genuine; ``None`` uses 

128 ``sqrt(machine eps)``. 

129 

130 Returns: 

131 The ``(p, 4)`` matrix of critical lambdas. 

132 """ 

133 p = g.shape[0] 

134 l_mat = np.full((p, 4), -np.inf) # pragma: no mutate 

135 if p == 0: 

136 return l_mat 

137 

138 eps = np.sqrt(np.finfo(np.float64).eps) 

139 slack_eps = eps if slack_floor is None else slack_floor 

140 eta_eps = eps if eta_floor is None else eta_floor 

141 inactive = ~active_ineq 

142 

143 # Enter: an inactive row's slack rises to zero. The slope/intercept split 

144 # comes straight from the affine weights; the slope sign mirrors the box 

145 # "moves to a bound" event (decreasing lam must raise the slack). 

146 s_alpha = g @ r_alpha - h 

147 s_beta = g @ r_beta 

148 enter = inactive & (s_beta < -slack_eps) # pragma: no mutate 

149 l_mat[enter, 0] = -s_alpha[enter] / s_beta[enter] 

150 

151 # Release: an active row's non-negative multiplier falls back to zero, 

152 # the row analogue of a blocked multiplier changing sign. 

153 release = active_ineq & (eta_beta > +eta_eps) # pragma: no mutate 

154 l_mat[release, 1] = -eta_alpha[release] / eta_beta[release] 

155 return l_mat 

156 

157 

158def roundoff_events_at_zero( 

159 l_mat: NDArray[np.float64], 

160 gamma: NDArray[np.float64], 

161 gamma_noise: NDArray[np.float64], 

162) -> NDArray[np.float64]: 

163 """Put the leave-a-bound events whose intercept is round-off at ``lambda = 0``. 

164 

165 A leave-a-bound event fires at ``-gamma / delta``. When ``|gamma|`` is within its 

166 round-off level the root belongs at zero and only rounds to either side of it, so 

167 the event is moved to ``lambda = 0``, where the trace ends; elsewhere it stays. 

168 Only candidate events (finite entries of columns 2 and 3) are moved. 

169 

170 Args: 

171 l_mat: The event matrix whose first ``len(gamma)`` rows are the box events. 

172 gamma: The multiplier intercepts of the box events. 

173 gamma_noise: Per-asset round-off level of ``gamma``. 

174 

175 Returns: 

176 The event matrix with those events at zero (a copy). 

177 """ 

178 l_mat = l_mat.copy() 

179 n = gamma.shape[0] 

180 box = l_mat[:n, 2:] 

181 at_zero = (np.abs(gamma) <= gamma_noise)[:, None] & np.isfinite(box) 

182 box[at_zero] = 0.0 

183 return l_mat 

184 

185 

186def segment_events( 

187 segment: Segment, 

188 lower: NDArray[np.float64], 

189 upper: NDArray[np.float64], 

190 g: NDArray[np.float64], 

191 h: NDArray[np.float64], 

192 lam_scale: float = 1.0, 

193 mu_scale: float = 1.0, 

194) -> NDArray[np.float64]: 

195 """Return the ``(n + p, 4)`` matrix of candidate critical lambdas for ``segment``. 

196 

197 The first ``n`` rows are the box events of :func:`event_ratios` (a free weight 

198 reaching a bound, a blocked multiplier changing sign); the trailing ``p`` rows 

199 are the inequality-row events of :func:`ineq_event_ratios` (an inactive row's 

200 slack reaching zero, an active row's multiplier changing sign). The generic 

201 tracer treats the two blocks uniformly; ``CLA.step`` decodes a row index 

202 ``>= n`` as a row event. 

203 

204 Args: 

205 segment: The critical-line segment to scan. 

206 lower: Per-asset lower bounds. 

207 upper: Per-asset upper bounds. 

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

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

210 lam_scale: The natural scale of ``lambda`` (covariance scale over return 

211 scale). Weight slopes ``dw/dlam`` carry units of ``1/lambda``, so their 

212 noise floor is ``sqrt(eps) / lam_scale``. 

213 mu_scale: The scale of the expected returns. Multiplier slopes carry the 

214 units of ``mu``, so their noise floor is ``sqrt(eps) * mu_scale``. 

215 With both scales the event test is invariant under rescaling the 

216 returns and the covariance; ``1.0`` and ``1.0`` give the unscaled 

217 ``sqrt(eps)`` floor. 

218 

219 Returns: 

220 The stacked ``(n + p, 4)`` event matrix. 

221 """ 

222 eps = np.sqrt(np.finfo(np.float64).eps) 

223 weight_floor = eps / lam_scale 

224 multiplier_floor = eps * mu_scale 

225 box = event_ratios( 

226 segment.r_alpha, 

227 segment.r_beta, 

228 segment.gamma, 

229 segment.delta, 

230 segment.free_in, 

231 segment.at_upper, 

232 segment.at_lower, 

233 lower, 

234 upper, 

235 beta_floor=weight_floor, 

236 delta_floor=multiplier_floor, 

237 ) 

238 ineq = ineq_event_ratios( 

239 segment.r_alpha, 

240 segment.r_beta, 

241 segment.eta_alpha, 

242 segment.eta_beta, 

243 segment.active_ineq, 

244 g, 

245 h, 

246 slack_floor=weight_floor, 

247 eta_floor=multiplier_floor, 

248 ) 

249 return np.vstack([box, ineq])