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

1"""The LASSO under coefficient bounds, equality rows ``A beta = b`` and rows ``G beta <= h``, as one CLA. 

2 

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. 

11 

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 

15 

16 min 1/2 ||y - X beta||^2 + lam ||beta||_1 s.t. A beta = b, G beta <= h, l <= beta <= u 

17 

18is, up to a constant, the CLA program 

19 

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 

22 

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. 

32 

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. 

46 

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. 

54 

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""" 

62 

63from __future__ import annotations 

64 

65import itertools 

66 

67import numpy as np 

68from numpy.typing import NDArray 

69from scipy.optimize import linprog # type: ignore[import-untyped] 

70 

71from ._lasso_cla import BreakpointData 

72from .cla import CLA 

73from .errors import CLAError, DegenerateProblemError, InfeasibleProblemError 

74from .operators import QuadraticForm 

75 

76 

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``. 

79 

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] 

86 

87 

88#: One knot of the path as ``(lam, beta)``. 

89Knot = tuple[float, NDArray[np.float64]] 

90 

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) 

97 

98#: The largest optimality violation, relative to ``||X^T y||_inf``, at which an 

99#: extrapolated path is accepted. 

100CERTIFIED = 1e-9 

101 

102 

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)] 

134 

135 

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``. 

149 

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. 

158 

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. 

170 

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) 

214 

215 

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). 

224 

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 

237 

238 

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. 

253 

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. 

258 

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) 

268 

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) 

271 

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 

297 

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) 

312 

313 

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``. 

326 

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``. 

339 

340 Returns: 

341 The breakpoints ``(lam, beta, active)`` from the first knot down to the 

342 constrained least-squares fit at ``lam = 0``. 

343 

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 

372 

373 def support(beta: NDArray[np.float64]) -> NDArray[np.bool_]: 

374 return np.abs(beta) > tol * scale 

375 

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