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

72 statements  

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

1"""Generic parametric active-set path tracer. 

2 

3The Critical Line Algorithm is one instance of a broader scheme: the optimiser of 

4a convex quadratic program is followed as a single scalar parameter ``lambda`` 

5varies, the solution path is piecewise linear, and it is traced exactly by 

6stepping from one breakpoint to the next while maintaining a *coordinate* active 

7set. The same scheme drives least angle regression (LARS) and the LASSO homotopy. 

8 

9This module factors out the part that is identical across those problems: 

10 

11* ``select_next_event`` -- the simplex-style "smallest positive ratio to the next 

12 event" rule with a Bland lowest-index tie-break for anti-cycling. It works on an 

13 ``(n, k)`` matrix of candidate critical ``lambda`` values, where the row is the 

14 coordinate and the column is the (problem-defined) event type. 

15* ``trace`` -- the control loop: build the first vertex, solve the current affine 

16 segment, scan events, pick the next one, flip one coordinate's activity, repeat. 

17 

18Everything problem-specific (the segment solve, what an event *means*, how a vertex 

19is recorded) lives behind the ``ParametricProblem`` protocol. ``CLA`` (portfolio 

20frontier) and ``Lasso`` (regression path) are two implementations; both are driven 

21by the same ``trace`` here. 

22""" 

23 

24from __future__ import annotations 

25 

26from functools import cached_property 

27from typing import Any, Protocol, runtime_checkable 

28 

29import numpy as np 

30from numpy.typing import NDArray 

31 

32from .errors import NumericalError 

33 

34# An event parameter within this many ulps of zero, relative to the first event, is lambda = 0. 

35_ROUNDOFF_FLOOR = 100 * float(np.finfo(np.float64).eps) 

36 

37 

38@runtime_checkable 

39class ParametricProblem(Protocol): 

40 """The problem-specific contract the generic ``trace`` loop drives. 

41 

42 A ``State`` describes the current vertex (which coordinates are free/blocked 

43 and their values); a ``Segment`` describes the affine piece valid until the 

44 next event. Both are opaque to the tracer: it only passes them back to the 

45 problem. Implementations record vertices as they are discovered (the tracer 

46 returns nothing). 

47 """ 

48 

49 @property 

50 def tol(self) -> float: 

51 """Tolerance for the event-selection tie-break and validity window.""" 

52 ... # pragma: no cover 

53 

54 @property 

55 def dimension(self) -> int: 

56 """Number of coordinates ``n`` (sets the iteration safety cap).""" 

57 ... # pragma: no cover 

58 

59 def begin(self) -> tuple[float, Any]: 

60 """Record the first vertex and return ``(lambda_start, initial_state)``.""" 

61 ... # pragma: no cover 

62 

63 def segment(self, state: Any) -> Any: 

64 """Solve the affine segment valid at ``state`` (the reduced KKT system).""" 

65 ... # pragma: no cover 

66 

67 def event_matrix(self, state: Any, segment: Any) -> NDArray[np.float64]: 

68 """Return the ``(n, k)`` matrix of candidate critical ``lambda`` values. 

69 

70 Entry ``(i, j)`` is the ``lambda`` at which coordinate ``i`` would fire 

71 event type ``j`` along ``segment``; ``-inf`` means "no such event". 

72 """ 

73 ... # pragma: no cover 

74 

75 def step(self, state: Any, segment: Any, sec: int, direction: int, lam: float) -> Any: 

76 """Record the vertex at ``lam`` after flipping coordinate ``sec``'s activity. 

77 

78 ``direction`` is the winning event-matrix column; the implementation maps 

79 it to the new activity (and, where relevant, the sign) of ``sec``. Returns 

80 the next ``State``. A problem may also define ``ends_trace(sec, direction)``; 

81 when it returns ``True`` the trace ends at the vertex ``step`` just recorded 

82 and no ``finish`` follows. 

83 """ 

84 ... # pragma: no cover 

85 

86 def finish(self, state: Any, segment: Any) -> None: 

87 """Record the final ``lambda = 0`` vertex (the segment's intercept).""" 

88 ... # pragma: no cover 

89 

90 

91class InequalityConstrained: 

92 """Mixin: normalise optional ``G x <= h`` inequality rows for a parametric problem. 

93 

94 Both the CLA (``G w <= h`` exposure caps) and the LASSO (``G beta <= h``) carry an 

95 optional inequality system through the same bordered machinery, so normalising the 

96 raw ``g``/``h`` inputs -- and counting the resulting path-length coordinates -- lives 

97 here once rather than being duplicated in each class. A concrete problem supplies the 

98 ``g``/``h`` inputs (``None`` when there are no inequality rows) and a ``dimension``. 

99 """ 

100 

101 g: NDArray[np.float64] | None 

102 h: NDArray[np.float64] | None 

103 

104 @property 

105 def dimension(self) -> int: 

106 """Number of coordinates ``n``; provided by the concrete problem class.""" 

107 raise NotImplementedError # pragma: no cover 

108 

109 @cached_property 

110 def g_matrix(self) -> NDArray[np.float64]: 

111 """Inequality matrix ``G`` of ``G x <= h`` as a ``(p, n)`` float array. 

112 

113 ``None`` is normalised to an empty ``(0, n)`` matrix, so the inequality 

114 machinery is a no-op and the trace reduces exactly to the unconstrained 

115 problem. This is the single point where the inequality input is normalised. 

116 """ 

117 if self.g is None: 

118 return np.zeros((0, self.dimension)) 

119 return np.atleast_2d(np.asarray(self.g, dtype=np.float64)) 

120 

121 @cached_property 

122 def h_vector(self) -> NDArray[np.float64]: 

123 """Inequality right-hand side ``h`` of ``G x <= h`` as a ``(p,)`` float array (empty if none).""" 

124 if self.h is None: 

125 return np.zeros(0) 

126 return np.atleast_1d(np.asarray(self.h, dtype=np.float64)) 

127 

128 @property 

129 def event_dimension(self) -> int: 

130 """Coordinate count for the tracer's path-length safety cap: ``n`` + ``p`` rows. 

131 

132 Each turning point fixes the activity of exactly one coordinate -- a box bound 

133 (or LASSO coefficient) or an inequality row of ``G x <= h`` -- so the iteration 

134 cap scales with ``n + p`` rather than ``n`` alone. With no inequality rows this 

135 is just ``n``. 

136 """ 

137 return self.dimension + int(self.g_matrix.shape[0]) 

138 

139 

140def select_next_event( 

141 l_mat: NDArray[np.float64], 

142 lam: float, 

143 tol: float, 

144 scale: float = 1.0, 

145 floor: float = 0.0, 

146 prefer: int | None = None, 

147) -> tuple[int, int, float] | None: 

148 """Pick the next breakpoint from the event matrix, or ``None`` to stop. 

149 

150 The current segment is valid only for ``lambda`` at or below the current value 

151 (the path is traced with non-increasing ``lambda``), so ratios above it are 

152 spurious crossings outside the segment and are discarded; if none remain the 

153 trace is complete. Among events tied for the largest valid ratio, a Bland-style 

154 lowest-``(coordinate, event type)`` rule makes the choice deterministic and 

155 prevents cycling on degenerate problems. 

156 

157 Two events are "the same" breakpoint only when their ``lambda`` values agree to 

158 floating-point scale, so the validity window and the tie-break use a tolerance 

159 *relative* to the ``lambda`` magnitude. A fixed absolute tolerance mis-ranks the 

160 densely spaced breakpoints of large paths: their spacing shrinks with the problem 

161 size, so an absolute window eventually merges genuinely distinct events, picks the 

162 wrong one by the tie-break, and lets ``lambda`` step backwards. The caller's 

163 ``tol`` is treated as an upper bound on this relative rate; event ordering needs a 

164 roundoff-scale window regardless of the coarser ``tol`` used elsewhere (e.g. to 

165 classify a weight as sitting on a bound). Finally, the chosen ``lambda`` is clamped 

166 below the current value, so roundoff in the segment solve can never make a 

167 breakpoint appear above it. 

168 

169 Args: 

170 l_mat: The ``(n, k)`` matrix of candidate critical ``lambda`` values. 

171 lam: The current (upper) ``lambda`` bound on valid events. 

172 tol: Upper bound on the relative event-ordering tolerance. 

173 scale: The natural scale of ``lambda``. Near ``lambda = 0`` the window is 

174 taken relative to this scale rather than to ``|lambda|``, so it 

175 does not shrink to nothing; ``1.0`` reproduces an absolute floor. 

176 floor: Events at or below this ``lambda`` are taken to be at ``lambda = 0`` 

177 and end the trace. ``trace`` sets it relative to the first finite event, 

178 so a root that belongs at zero but rounds to a tiny positive value 

179 (e.g. ``1e-16``) does not fire. 

180 prefer: Optional coordinate whose event wins a tie: if any of its events 

181 is among those tied for the largest valid ratio, it is chosen over the 

182 Bland lowest-index pick. 

183 

184 Returns: 

185 ``(sec, direction, lam_next)`` for the chosen event, or ``None`` if no 

186 valid event remains above ``lambda = 0``. 

187 """ 

188 l_mat = l_mat.copy() # do not mutate the caller's matrix 

189 rate = min(tol, 1e-10) # roundoff-scale relative window; tol is only an upper bound 

190 l_mat[l_mat > lam + rate * max(scale, abs(lam))] = -np.inf # pragma: no mutate 

191 

192 lam_max = np.max(l_mat) 

193 # An event at lambda = 0 coincides with the endpoint ``finish`` records, so it 

194 # ends the trace rather than firing: under homogeneous constraints the path runs 

195 # along a ray into the origin and every free coordinate reaches its bound there 

196 # at once, which would otherwise emit one copy of the endpoint per coordinate. 

197 if lam_max <= floor: 

198 return None 

199 

200 # The tie window near zero is absolute, so it can reach entries at or below the floor; 

201 # those are lambda = 0 (the endpoint), never the event to fire. 

202 tied = np.argwhere((l_mat >= lam_max - rate * max(scale, abs(lam_max))) & (l_mat > floor)) # pragma: no mutate 

203 preferred = tied[tied[:, 0] == prefer] 

204 sec, direction = preferred[0] if len(preferred) else tied[0] 

205 # lambda is non-increasing along the path: clamp away any roundoff overshoot. 

206 return int(sec), int(direction), float(min(lam, l_mat[sec, direction])) 

207 

208 

209def trace(problem: ParametricProblem) -> None: 

210 """Trace the full piecewise-linear solution path of ``problem``. 

211 

212 Mirrors the turning-point loop of the Critical Line Algorithm, but driven 

213 entirely through the ``ParametricProblem`` interface so the same control flow 

214 serves any coordinate-active-set parametric quadratic program. 

215 

216 Args: 

217 problem: The problem to trace; its ``begin``/``segment``/``event_matrix``/ 

218 ``step``/``finish`` hooks record the discovered vertices. 

219 

220 Raises: 

221 NumericalError: If the event loop fails to terminate within the safety cap 

222 (each step fixes the activity of at least one coordinate, so a correct 

223 trace runs ``O(n)`` times; vastly exceeding this signals cycling). 

224 """ 

225 lam, state = problem.begin() 

226 

227 # Safety bound: far above any valid path length; exceeding it means the event 

228 # loop failed to terminate, so we fail loudly rather than hang. Each step fixes 

229 # the activity of one coordinate -- a box bound (n of them) or an inequality row 

230 # (p of them) -- so the bound scales with the total n + p, not n alone; a problem 

231 # that exposes only ``dimension`` (no inequality rows) falls back to n. 

232 path_coords = getattr(problem, "event_dimension", problem.dimension) # pragma: no mutate 

233 max_iterations = 100 * (path_coords + 1) # pragma: no mutate 

234 scale = float(getattr(problem, "lambda_scale", 1.0)) 

235 # Events below a floor relative to the first finite event are lambda = 0: roundoff 

236 # can move a root at zero to ~1e-16, and firing it would emit a turning point whose 

237 # free block is singular. Taken from the path itself rather than ``scale``, which a 

238 # covariance that cancels along the equal-weight direction can drive to roundoff. 

239 # The floor sits at machine precision, not at ``tol``: an ill-conditioned covariance 

240 # has genuine turning points many decades below the first event (~1e-13 of it for a 

241 # spectrum spanning 1e12), and a coarser floor truncates the frontier there. 

242 floor = 0.0 

243 prefer = getattr(problem, "stop", None) 

244 ends_trace = getattr(problem, "ends_trace", None) 

245 iterations = 0 # pragma: no mutate 

246 

247 while True: # pragma: no mutate 

248 iterations += 1 # pragma: no mutate 

249 if iterations > max_iterations: # pragma: no mutate 

250 msg = "path tracer failed to converge: too many iterations" # pragma: no mutate 

251 raise NumericalError(msg) # pragma: no mutate 

252 

253 segment = problem.segment(state) 

254 event = select_next_event(problem.event_matrix(state, segment), lam, problem.tol, scale, floor, prefer) 

255 if event is None: 

256 problem.finish(state, segment) 

257 return 

258 

259 sec, direction, lam = event 

260 if floor == 0.0: # pragma: no mutate 

261 floor = _ROUNDOFF_FLOOR * lam 

262 state = problem.step(state, segment, sec, direction, lam) 

263 if ends_trace is not None and ends_trace(sec, direction): 

264 return