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
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-17 13:36 +0000
1"""Generic parametric active-set path tracer.
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.
9This module factors out the part that is identical across those problems:
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.
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"""
24from __future__ import annotations
26from functools import cached_property
27from typing import Any, Protocol, runtime_checkable
29import numpy as np
30from numpy.typing import NDArray
32from .errors import NumericalError
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)
38@runtime_checkable
39class ParametricProblem(Protocol):
40 """The problem-specific contract the generic ``trace`` loop drives.
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 """
49 @property
50 def tol(self) -> float:
51 """Tolerance for the event-selection tie-break and validity window."""
52 ... # pragma: no cover
54 @property
55 def dimension(self) -> int:
56 """Number of coordinates ``n`` (sets the iteration safety cap)."""
57 ... # pragma: no cover
59 def begin(self) -> tuple[float, Any]:
60 """Record the first vertex and return ``(lambda_start, initial_state)``."""
61 ... # pragma: no cover
63 def segment(self, state: Any) -> Any:
64 """Solve the affine segment valid at ``state`` (the reduced KKT system)."""
65 ... # pragma: no cover
67 def event_matrix(self, state: Any, segment: Any) -> NDArray[np.float64]:
68 """Return the ``(n, k)`` matrix of candidate critical ``lambda`` values.
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
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.
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
86 def finish(self, state: Any, segment: Any) -> None:
87 """Record the final ``lambda = 0`` vertex (the segment's intercept)."""
88 ... # pragma: no cover
91class InequalityConstrained:
92 """Mixin: normalise optional ``G x <= h`` inequality rows for a parametric problem.
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 """
101 g: NDArray[np.float64] | None
102 h: NDArray[np.float64] | None
104 @property
105 def dimension(self) -> int:
106 """Number of coordinates ``n``; provided by the concrete problem class."""
107 raise NotImplementedError # pragma: no cover
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.
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))
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))
128 @property
129 def event_dimension(self) -> int:
130 """Coordinate count for the tracer's path-length safety cap: ``n`` + ``p`` rows.
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])
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.
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.
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.
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.
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
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
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]))
209def trace(problem: ParametricProblem) -> None:
210 """Trace the full piecewise-linear solution path of ``problem``.
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.
216 Args:
217 problem: The problem to trace; its ``begin``/``segment``/``event_matrix``/
218 ``step``/``finish`` hooks record the discovered vertices.
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()
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
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
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
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