Coverage for src/cvxcla/_lasso_bounded.py: 100%
114 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"""The LASSO under coefficient bounds, equality rows ``A beta = b`` and rows ``G beta <= h``, as one CLA.
3The homotopy of :mod:`cvxcla.lasso` starts from ``beta = 0`` with every row slack,
4and the leverage route of :mod:`cvxcla._lasso_cla` needs every constraint
5homogeneous. Neither takes a sign on only some of the coefficients together with a
6cap, an equality row with a nonzero right-hand side, or inequality rows together with
7either. This module traces those
8with the CLA directly, in the *penalty form* (Schmelzer, "The Constrained LASSO by
9the Critical Line Algorithm"): the penalty ``lam ||beta||_1`` is read as a cost of
10``lam`` per unit of gross position.
12Split ``beta = S z`` with ``z >= 0``, where ``S`` has a column ``e_j`` for every
13``j`` with ``u_j > 0`` and a column ``-e_j`` for every ``j`` with ``l_j < 0``. With
14``G = X^T X`` and ``c = X^T y`` the LASSO
16 min 1/2 ||y - X beta||^2 + lam ||beta||_1 s.t. A beta = b, G beta <= h, l <= beta <= u
18is, up to a constant, the CLA program
20 min 1/2 z^T (S^T X^T X S) z - (S^T c + lam * (-1))^T z
21 s.t. A S z = b, G S z <= h, 0 <= z <= u_bar
23at tilt ``lam``, where ``u_bar`` stacks the bounds ``u_j`` and ``-l_j`` of the
24columns. The CLA's tilt *is* the penalty, so every turning point is a knot,
25``beta = S z`` at ``lam``. At ``lam = inf`` the CLA starts from the vertex of
26smallest ``l1`` norm on the constraints, which is ``z = 0`` without equality rows
27(every row of ``G beta <= h`` with ``h > 0`` is slack there). A row with ``h_r < 0``
28excludes ``beta = 0`` and moves the start to the smallest-``l1`` point it allows, as a
29nonzero ``b`` does; where that point is a whole face the CLA starts on it where its
30quadratic term is smallest. Homogeneous rows with signs only go to the leverage route;
31the cases below are traced here.
33**Homogeneous inequality rows** (``h_r = 0``, such as the ordering ``beta_j <=
34beta_{j+1}`` of a monotone fit) are all tight at ``z = 0``, so the start is degenerate
35too. They are resolved by relaxation and extrapolation. On a fixed sequence of active
36sets the solution on each segment is affine in ``h`` and its slope in ``lam`` does not
37depend on ``h``, so the parameter at which a coordinate reaches a bound, a knot, is
38affine in ``h`` as well. Tracing the rows at ``h_r = eps`` and ``h_r = 2 eps``, both
39nondegenerate, therefore gives the exact path at ``h_r = 0`` as
40``2 path(eps) - path(2 eps)``, provided both runs take the same sequence. Segments that
41shrink to a point at ``h_r = 0`` (rows the relaxed path met one by one, and the
42exact path meets together) are dropped. The result is then *certified*, not trusted: a
43linear program finds the multipliers that best satisfy the LASSO's optimality conditions
44at every knot and segment midpoint, and the extrapolated path is returned only if they
45hold to rounding.
47The relaxation moves every knot, by an amount proportional to it. Where two knots of
48the exact path lie closer together than that, the two relaxed runs can meet their
49events in different orders, and the extrapolation then pairs knots of different events.
50A long path is the usual case: a zero-sum LASSO with 500 parts has knots less than ``1e-6 lam_max``
51apart, and relaxed by the first of :data:`RELAXATIONS` two of them swap. So a path that
52fails either check is traced again with the next, smaller relaxation, and the problem is
53declined only when every relaxation fails, or the CLA cannot start at one.
55**Homogeneous equality rows** (``A beta = 0``, such as a zero sum) together with a finite
56bound or inequality rows are resolved the same way, relaxing ``b`` to ``eps A d`` for a
57generic point ``d`` the bounds and the homogeneous rows admit, alongside any ``h_r = 0``.
58At ``b = 0`` the start ``z = 0`` is degenerate; relaxed it is a whole face of
59smallest-``l1`` points (every same-signed leg of a ones row ties), and the CLA starts on
60that face where its quadratic term is smallest.
61"""
63from __future__ import annotations
65import itertools
67import numpy as np
68from numpy.typing import NDArray
69from scipy.optimize import linprog # type: ignore[import-untyped]
71from ._lasso_cla import BreakpointData
72from .cla import CLA
73from .errors import CLAError, DegenerateProblemError, InfeasibleProblemError
74from .operators import QuadraticForm
77def _split(lower: NDArray[np.float64], upper: NDArray[np.float64]) -> tuple[NDArray[np.float64], NDArray[np.float64]]:
78 """Return the legs ``S`` (one column per allowed sign) and their bounds ``u_bar``.
80 A coefficient whose bounds are both zero has no column: it is fixed at zero.
81 """
82 n = lower.shape[0]
83 keep = np.concatenate([upper > 0, lower < 0])
84 legs = np.hstack([np.eye(n), -np.eye(n)])[:, keep]
85 return legs, np.concatenate([upper, -lower])[keep]
88#: One knot of the path as ``(lam, beta)``.
89Knot = tuple[float, NDArray[np.float64]]
91#: The relaxations of a homogeneous row tried in turn, relative to the scale
92#: ``||X^T y||_inf / max_j (X^T X)_jj`` of a coefficient. The first is large enough that the
93#: CLA starts cleanly; the smaller ones are tried only when it fails, for paths whose
94#: knots lie closer together than the first moves them (module docstring). Below about
95#: ``1e-9`` the relaxed start is lost in rounding.
96RELAXATIONS = (1e-6, 1e-7, 1e-8)
98#: The largest optimality violation, relative to ``||X^T y||_inf``, at which an
99#: extrapolated path is accepted.
100CERTIFIED = 1e-9
103def _trace(
104 sigma: NDArray[np.float64],
105 q: NDArray[np.float64],
106 legs: NDArray[np.float64],
107 cap: NDArray[np.float64],
108 a: NDArray[np.float64],
109 b: NDArray[np.float64],
110 g: NDArray[np.float64] | None,
111 h: NDArray[np.float64] | None,
112) -> list[Knot]:
113 """Run the penalty-form CLA and return its knots, from the first one down to ``lam = 0``."""
114 k = legs.shape[1]
115 try:
116 cla = CLA(
117 mean=-np.ones(k),
118 covariance=sigma,
119 lower_bounds=np.zeros(k),
120 upper_bounds=cap,
121 a=a @ legs,
122 b=b,
123 g=None if g is None else g @ legs,
124 h=h,
125 q=q,
126 )
127 except ValueError as err:
128 msg = f"the bounded LASSO could not be traced through the CLA: {err}"
129 # Keep the error's kind (infeasible, degenerate, ...) when the CLA classified it.
130 raise (type(err) if isinstance(err, CLAError) else ValueError)(msg) from err
131 # The lam = inf vertex is the first knot again, held still until a coefficient enters;
132 # the trace always ends with a finite one, the constrained least-squares fit at lam = 0.
133 return [(float(tp.lamb), legs @ tp.weights) for tp in cla.turning_points if np.isfinite(tp.lamb)]
136def kkt_violation(
137 gram: NDArray[np.float64],
138 xty: NDArray[np.float64],
139 lam: float,
140 beta: NDArray[np.float64],
141 a: NDArray[np.float64],
142 b: NDArray[np.float64],
143 g: NDArray[np.float64],
144 h: NDArray[np.float64],
145 lower: NDArray[np.float64],
146 upper: NDArray[np.float64],
147) -> float:
148 """Largest violation of the LASSO's optimality conditions at ``beta``, relative to ``||X^T y||_inf``.
150 With ``r = X^T X beta - X^T y + A^T nu + G_R^T eta`` over the rows ``R`` of
151 ``G beta <= h`` that are active, a nonzero coefficient strictly inside its bounds needs
152 ``r_j = -lam sign(beta_j)``, one at a cap ``u_j > 0`` needs ``r_j <= -lam``, one at a
153 floor ``l_j < 0`` needs ``r_j >= lam``, and a zero one needs ``-lam <= r_j <= lam``
154 less the side a sign bound takes away; ``eta >= 0``. A linear program picks ``nu`` and
155 ``eta`` to make the worst violation as small as it can, which is zero exactly at the
156 optimum, and the violation is then evaluated again exactly at the multipliers it found,
157 so the LP's own tolerance cannot hide one. Primal feasibility is included.
159 Args:
160 gram: ``X^T X`` as a dense ``(n, n)`` array.
161 xty: ``X^T y``.
162 lam: The penalty.
163 beta: The coefficients to certify.
164 a: Equality rows ``(m, n)``; ``m`` may be zero.
165 b: Their right-hand side.
166 g: Inequality rows ``(p, n)``; ``p`` may be zero.
167 h: Their right-hand side.
168 lower: Lower bounds.
169 upper: Upper bounds.
171 Returns:
172 The violation, relative to ``||X^T y||_inf`` (absolute when ``X^T y = 0``).
173 """
174 tol = 1e-9 * max(1.0, float(np.abs(beta).max()))
175 zero = np.abs(beta) <= tol
176 at_up, at_lo = ~zero & (beta >= upper - tol), ~zero & (beta <= lower + tol)
177 inner = ~zero & ~at_up & ~at_lo
178 rows = np.vstack([a, g[g @ beta >= h - tol * max(1.0, float(np.abs(h).max(initial=1.0)))]])
179 m, k = a.shape[0], rows.shape[0]
180 r0 = gram @ beta - xty
181 lam_sign = lam * np.sign(beta)
182 full = np.full_like(beta, lam)
183 # Each condition is side * r_j + offset <= worst, over the coordinates in its mask.
184 parts = [
185 (inner, 1.0, lam_sign),
186 (inner, -1.0, -lam_sign),
187 (at_up, 1.0, full),
188 (at_lo, -1.0, full),
189 (zero & (lower < 0), 1.0, -full),
190 (zero & (upper > 0), -1.0, -full),
191 ]
192 coord = np.concatenate([np.flatnonzero(mask) for mask, _, _ in parts]).astype(int)
193 side = np.concatenate([np.full(int(mask.sum()), sgn) for mask, sgn, _ in parts])
194 offset = np.concatenate([off[mask] for mask, _, off in parts])
195 lp = linprog(
196 np.append(np.zeros(k), 1.0),
197 A_ub=np.hstack([side[:, None] * rows.T[coord], -np.ones((len(coord), 1))]),
198 b_ub=-(side * r0[coord] + offset),
199 bounds=[(None, None)] * m + [(0.0, None)] * (k - m + 1),
200 method="highs",
201 )
202 mult = np.concatenate([lp.x[:m], np.maximum(lp.x[m:k], 0.0)])
203 worst = float(np.max(side * (r0 + rows.T @ mult)[coord] + offset, initial=0.0))
204 feasibility = np.concatenate(
205 [
206 np.abs(a @ beta - b),
207 np.maximum(g @ beta - h, 0.0),
208 np.maximum(beta - upper, 0.0),
209 np.maximum(lower - beta, 0.0),
210 ]
211 )
212 # With X^T y = 0 there is no scale to be relative to; the violation is then absolute.
213 return max(worst, float(feasibility.max(initial=0.0))) / (float(np.abs(xty).max()) or 1.0)
216def _relaxation_direction(
217 a: NDArray[np.float64],
218 g: NDArray[np.float64],
219 h: NDArray[np.float64],
220 lower: NDArray[np.float64],
221 upper: NDArray[np.float64],
222) -> NDArray[np.float64]:
223 """A generic point ``d`` whose image ``A d`` relaxes ``A beta = 0`` (module docstring).
225 Each coefficient gets a pseudo-random magnitude in ``[0.5, 1.5]`` and a sign its bounds
226 allow, so ``A d`` is generic and the relaxed start a unique vertex. ``d`` is then scaled
227 so that ``G_r d <= 1/2`` on the homogeneous rows, which keeps ``eps d`` strictly inside
228 their relaxation ``g_r beta <= eps``; every other constraint has room of order one.
229 """
230 rng = np.random.default_rng(0)
231 n = a.shape[1]
232 sign = np.where(rng.random(n) < 0.5, -1.0, 1.0)
233 sign = np.where(upper > 0, np.where(lower < 0, sign, 1.0), np.where(lower < 0, -1.0, 0.0))
234 d: NDArray[np.float64] = sign * rng.uniform(0.5, 1.5, n)
235 reach = float(np.max(g[h == 0] @ d, initial=0.0))
236 return d * min(1.0, 0.5 / reach) if reach > 0 else d
239def _resolve_homogeneous(
240 gram: NDArray[np.float64],
241 sigma: NDArray[np.float64],
242 xty: NDArray[np.float64],
243 legs: NDArray[np.float64],
244 cap: NDArray[np.float64],
245 a: NDArray[np.float64],
246 b: NDArray[np.float64],
247 g: NDArray[np.float64],
248 h: NDArray[np.float64],
249 lower: NDArray[np.float64],
250 upper: NDArray[np.float64],
251) -> list[Knot]:
252 """The exact knots with homogeneous rows ``h_r = 0`` or ``A beta = 0``, from two relaxed traces.
254 Each relaxation of :data:`RELAXATIONS` is tried in turn until one gives a path that
255 passes both checks. An error of the CLA at the first relaxation is the problem's own
256 (infeasible rows, say) and is raised as it is; at a later one it means the relaxation
257 is too small to start from, and the problem is declined.
259 Raises:
260 DegenerateProblemError: If at every relaxation the two relaxed traces take
261 different sequences or the extrapolated path fails its optimality certificate.
262 """
263 h_dir = (h == 0).astype(np.float64)
264 b_dir = a @ _relaxation_direction(a, g, h, lower, upper) if a.shape[0] and not b.any() else np.zeros_like(b)
265 scale = float(np.abs(xty).max()) / max(float(np.diag(gram).max()), 1e-300)
266 q = legs.T @ xty
267 rows = (g, h) if g.shape[0] else (None, None)
269 def relaxed(t: float) -> list[Knot]:
270 return _trace(sigma, q, legs, cap, a, b + t * b_dir, rows[0], None if rows[1] is None else h + t * h_dir)
272 def extrapolated(eps: float) -> list[Knot] | str:
273 """The certified exact knots from the relaxations ``eps`` and ``2 eps``, or why there are none."""
274 once, twice = relaxed(eps), relaxed(2 * eps)
275 if len(once) != len(twice):
276 return (
277 f"relaxed by {eps:.1e} and {2 * eps:.1e} they trace {len(once)} and {len(twice)} knots, "
278 f"so the sequence of active sets depends on the relaxation"
279 )
280 knots = [(max(2 * l1 - l2, 0.0), 2 * b1 - b2) for (l1, b1), (l2, b2) in zip(once, twice, strict=True)]
281 # A segment the relaxed path needed to meet the rows one by one has no length at h_r = 0.
282 floor = 1e-12 * knots[0][0]
283 kept = [knots[0]]
284 for lam, beta in knots[1:]:
285 if kept[-1][0] - lam > floor:
286 kept.append((lam, beta))
287 # The path ends at the least-squares fit, lam = 0, whichever of the coinciding knots was kept.
288 kept[-1] = knots[-1] if kept[-1][0] - knots[-1][0] <= floor else kept[-1]
289 points = kept + [(0.5 * (l1 + l2), 0.5 * (b1 + b2)) for (l1, b1), (l2, b2) in itertools.pairwise(kept)]
290 worst = max(kkt_violation(gram, xty, lam, beta, a, b, g, h, lower, upper) for lam, beta in points)
291 if worst > CERTIFIED:
292 return (
293 f"relaxed by {eps:.1e} the extrapolated path violates the optimality conditions by "
294 f"{worst:.1e} (relative), above {CERTIFIED:g}"
295 )
296 return kept
298 reasons: list[str] = []
299 for relaxation in RELAXATIONS:
300 try:
301 result = extrapolated(relaxation * scale)
302 except ValueError as err:
303 if not reasons:
304 raise
305 reasons.append(f"relaxed by {relaxation * scale:.1e} the CLA cannot start ({err})")
306 break
307 if not isinstance(result, str):
308 return result
309 reasons.append(result)
310 msg = "the homogeneous rows could not be resolved: " + "; ".join(reasons)
311 raise DegenerateProblemError(msg)
314def bounded_path(
315 quad: QuadraticForm,
316 xty: NDArray[np.float64],
317 a: NDArray[np.float64],
318 b: NDArray[np.float64],
319 lower: NDArray[np.float64],
320 upper: NDArray[np.float64],
321 tol: float,
322 g: NDArray[np.float64] | None = None,
323 h: NDArray[np.float64] | None = None,
324) -> list[BreakpointData]:
325 """Trace the LASSO path under ``A beta = b``, ``G beta <= h`` and ``lower <= beta <= upper``.
327 Args:
328 quad: The Gram form ``X^T X`` as a :class:`QuadraticForm`.
329 xty: The linear term ``X^T y``.
330 a: The equality rows ``(m, n)``; ``m`` may be zero.
331 b: Their right-hand side ``(m,)``.
332 lower: Lower bounds, each ``<= 0`` (``-inf`` allowed).
333 upper: Upper bounds, each ``>= 0`` (``inf`` allowed).
334 tol: Coefficients below ``tol`` times the path's scale count as zero in the
335 ``active`` masks.
336 g: Optional inequality rows ``(p, n)`` of ``G beta <= h``.
337 h: Their right-hand side ``(p,)``; a zero entry is a homogeneous row, a negative
338 one excludes ``beta = 0``.
340 Returns:
341 The breakpoints ``(lam, beta, active)`` from the first knot down to the
342 constrained least-squares fit at ``lam = 0``.
344 Raises:
345 InfeasibleProblemError: If the bounds fix every coefficient at zero and
346 ``b`` is nonzero.
347 DegenerateProblemError: If homogeneous rows cannot be resolved (see the module
348 docstring).
349 ValueError: If the CLA cannot trace the problem, e.g. a degenerate or
350 non-unique first vertex (see the module docstring).
351 """
352 n = xty.shape[0]
353 legs, cap = _split(lower, upper)
354 k = legs.shape[1]
355 if k == 0:
356 # Every coefficient is fixed at zero, so the path is that one point, if feasible.
357 if b.any():
358 msg = "the bounds fix beta = 0, which A beta = b with b != 0 excludes"
359 raise InfeasibleProblemError(msg)
360 return [(0.0, np.zeros(n), np.zeros(n, dtype=bool))]
361 # S^T G S through the operator, one leg at a time; k <= 2 n, so this is O(n) matvecs.
362 sigma = legs.T @ np.column_stack([quad.matvec(legs[:, i]) for i in range(k)])
363 homogeneous_rows = g is not None and h is not None and bool(np.any(h == 0))
364 if homogeneous_rows or (a.shape[0] and not b.any()):
365 gram = np.column_stack([quad.matvec(e) for e in np.eye(n)])
366 g_all = np.zeros((0, n)) if g is None else g
367 h_all = np.zeros(0) if h is None else h
368 knots = _resolve_homogeneous(gram, sigma, xty, legs, cap, a, b, g_all, h_all, lower, upper)
369 else:
370 knots = _trace(sigma, legs.T @ xty, legs, cap, a, b, g, h)
371 scale = max(float(np.abs(beta).max()) for _, beta in knots) or 1.0
373 def support(beta: NDArray[np.float64]) -> NDArray[np.bool_]:
374 return np.abs(beta) > tol * scale
376 # The support on the segment leaving a knot is that of the segment's midpoint.
377 path: list[BreakpointData] = [
378 (lam, beta, support(0.5 * (beta + after))) for (lam, beta), (_, after) in itertools.pairwise(knots)
379 ]
380 lam, beta = knots[-1]
381 path.append((lam, beta, support(beta)))
382 return path