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
« 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.
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"""
12from __future__ import annotations
14import numpy as np
15from numpy.typing import NDArray
17from ._kkt import Segment
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.
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``.
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.
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)``.
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
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
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
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.
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).
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)``.
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
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
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]
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
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``.
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.
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``.
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
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``.
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.
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.
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])