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

129 statements  

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

1"""Leverage (gross-exposure) constraints ``||w||_1 <= c`` via a signed lift. 

2 

3The 1-norm is not linear in ``w``, but it is polyhedral: splitting each weight into 

4a long and a short leg, ``w_i = u_i - v_i`` with ``u_i, v_i >= 0``, turns 

5``||w||_1 <= c`` into the single linear row ``sum(u) + sum(v) <= c``. The lifted 

6problem is a CLA over the legs with one extra inequality row, and every other 

7constraint carries over by substituting ``w = P x``, where ``P`` maps each leg to 

8its asset with sign ``+1`` (long) or ``-1`` (short). 

9 

10Only an asset whose box straddles zero (``lower < 0 < upper``) needs two legs. A 

11long-only asset (``lower >= 0``) keeps one ``+1`` leg and a short-only asset 

12(``upper <= 0``) one ``-1`` leg, so a long-only problem is not enlarged at all. 

13 

14The lifted covariance ``P.T Sigma P`` is singular (the direction that raises both 

15legs of one asset is flat), but it only enters the solve through its free block, 

16and that block is a signed principal submatrix of ``Sigma`` as long as no asset has 

17both legs free. :class:`SignedLift` exposes it through the ``QuadraticForm`` 

18interface without forming ``P.T Sigma P``, so structured backends keep their 

19advantage. Both legs are never free together on the traced path: while one leg is 

20off its lower bound, the other leg's multiplier equals twice the leverage row's 

21multiplier, which is non-negative, so the other leg can only become free at the 

22same ``lambda`` as the row releases. :func:`mask_leg_events` drops that 

23competing leg event so the row release wins the tie. 

24 

25Under ``Sigma = X^T X`` and ``mu = X^T y`` the capped program is the constrained 

26LASSO read as a portfolio: its budget-indexed path is the LASSO path, and the tilt 

27sweep traced here is that path rescaled (Schmelzer and Hastie, arXiv:2609.25704, 

28Theorem 1 and Corollary 2). See :mod:`cvxcla.lasso`. 

29""" 

30 

31from __future__ import annotations 

32 

33from dataclasses import dataclass 

34 

35import numpy as np 

36from numpy.typing import NDArray 

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

38 

39from .operators import QuadraticForm 

40from .types import TurningPoint 

41 

42 

43def _scale_rows(sign: NDArray[np.float64], v: NDArray[np.float64]) -> NDArray[np.float64]: 

44 """Multiply the rows of a vector or a column-stacked matrix by ``sign``.""" 

45 result: NDArray[np.float64] = sign[:, None] * v if v.ndim == 2 else sign * v 

46 return result 

47 

48 

49class SignedLift(QuadraticForm): 

50 """The lifted quadratic form ``P.T @ base @ P`` of a signed leg-to-asset map. 

51 

52 Leg ``k`` belongs to asset ``asset[k]`` with sign ``sign[k]``, so 

53 ``(P x)_i = sum_{k: asset[k] = i} sign[k] x_k``. Products are routed through 

54 the ``base`` operator on the distinct assets involved; a free-block solve is a 

55 signed solve on the base's principal block and is only defined while no asset 

56 has two legs in the free set. 

57 

58 Attributes: 

59 base: The covariance over the assets. 

60 asset: The asset each leg belongs to (length = number of legs). 

61 sign: ``+1`` for a long leg, ``-1`` for a short leg. 

62 """ 

63 

64 def __init__(self, base: QuadraticForm, asset: NDArray[np.intp], sign: NDArray[np.float64]) -> None: 

65 """Wrap ``base`` with the leg map ``(asset, sign)``.""" 

66 self.base = base 

67 self.asset = asset 

68 self.sign = sign 

69 

70 @property 

71 def n(self) -> int: 

72 """Number of legs.""" 

73 return int(self.asset.shape[0]) 

74 

75 def matvec(self, x: NDArray[np.float64]) -> NDArray[np.float64]: 

76 """Return ``P.T @ base @ P @ x``. 

77 

78 The legs are summed onto their assets, one full ``base`` product is taken, 

79 and the result is spread back onto the legs -- no ``np.unique`` over the 

80 legs, as the general :meth:`block_matvec` needs. 

81 """ 

82 x = np.asarray(x, dtype=np.float64) 

83 collapsed = np.zeros((self.base.n, *x.shape[1:])) 

84 np.add.at(collapsed, self.asset, _scale_rows(self.sign, x)) 

85 return _scale_rows(self.sign, np.asarray(self.base.matvec(collapsed))[self.asset]) 

86 

87 def block_matvec(self, rows: object, cols: object, v: NDArray[np.float64]) -> NDArray[np.float64]: 

88 """Return the ``(rows, cols)`` block of the lifted form applied to ``v``. 

89 

90 The column legs are first summed onto their distinct assets (both legs of 

91 one asset collapse to a single signed entry), the base block product is 

92 taken over distinct assets, and the result is spread back onto the row legs. 

93 """ 

94 rows = np.asarray(rows, dtype=np.intp) 

95 cols = np.asarray(cols, dtype=np.intp) 

96 col_assets, col_inverse = np.unique(self.asset[cols], return_inverse=True) 

97 collapsed = np.zeros((col_assets.shape[0], *v.shape[1:])) 

98 np.add.at(collapsed, col_inverse, _scale_rows(self.sign[cols], np.asarray(v, dtype=np.float64))) 

99 row_assets, row_inverse = np.unique(self.asset[rows], return_inverse=True) 

100 product = np.asarray(self.base.block_matvec(row_assets, col_assets, collapsed)) 

101 return _scale_rows(self.sign[rows], product[row_inverse]) 

102 

103 def solve_free(self, free: object, rhs: NDArray[np.float64]) -> NDArray[np.float64]: 

104 """Solve on the free block, a signed principal block of ``base``. 

105 

106 Raises: 

107 numpy.linalg.LinAlgError: If an asset has both legs in ``free``, which 

108 makes the block singular. 

109 """ 

110 free = np.asarray(free, dtype=np.intp) 

111 assets = self.asset[free] 

112 if np.unique(assets).size != assets.size: 

113 msg = "both legs of an asset are free, so the lifted free block is singular" 

114 raise np.linalg.LinAlgError(msg) 

115 sign = self.sign[free] 

116 return _scale_rows(sign, np.asarray(self.base.solve_free(assets, _scale_rows(sign, rhs)))) 

117 

118 def rcond_free(self, free: object) -> float: 

119 """Reciprocal condition number of the free block (``0`` if an asset has both legs free). 

120 

121 Flipping signs leaves the spectrum unchanged, so this is the base's 

122 conditioning of the distinct free assets. 

123 """ 

124 assets = self.asset[np.asarray(free, dtype=np.intp)] 

125 if np.unique(assets).size != assets.size: 

126 return 0.0 

127 return float(self.base.rcond_free(assets)) 

128 

129 

130@dataclass(frozen=True) 

131class LeverageLift: 

132 """The signed leg structure of a leverage-constrained problem. 

133 

134 Attributes: 

135 asset: The asset each leg belongs to. 

136 sign: ``+1`` for a long leg, ``-1`` for a short leg. 

137 partner: For a leg of a two-legged asset, the index of its other leg; 

138 ``-1`` for the single leg of a long-only or short-only asset. 

139 lower: Lower bounds of the legs. 

140 upper: Upper bounds of the legs. 

141 """ 

142 

143 asset: NDArray[np.intp] 

144 sign: NDArray[np.float64] 

145 partner: NDArray[np.intp] 

146 lower: NDArray[np.float64] 

147 upper: NDArray[np.float64] 

148 

149 @classmethod 

150 def from_bounds(cls, lower: NDArray[np.float64], upper: NDArray[np.float64]) -> LeverageLift: 

151 """Build the legs from the asset box ``lower <= w <= upper``. 

152 

153 An asset with ``lower >= 0`` gets one long leg on ``[lower, upper]``; one 

154 with ``upper <= 0`` gets one short leg on ``[-upper, -lower]``; one with 

155 ``lower < 0 < upper`` gets a long leg on ``[0, upper]`` and a short leg on 

156 ``[0, -lower]``, stored next to each other. 

157 """ 

158 asset: list[int] = [] 

159 sign: list[float] = [] 

160 leg_lower: list[float] = [] 

161 leg_upper: list[float] = [] 

162 partner: list[int] = [] 

163 for i, (lo, up) in enumerate(zip(lower.tolist(), upper.tolist(), strict=True)): 

164 if lo >= 0.0: 

165 asset.append(i) 

166 sign.append(1.0) 

167 leg_lower.append(lo) 

168 leg_upper.append(up) 

169 partner.append(-1) 

170 elif up <= 0.0: 

171 asset.append(i) 

172 sign.append(-1.0) 

173 leg_lower.append(-up) 

174 leg_upper.append(-lo) 

175 partner.append(-1) 

176 else: 

177 k = len(asset) 

178 asset += [i, i] 

179 sign += [1.0, -1.0] 

180 leg_lower += [0.0, 0.0] 

181 leg_upper += [up, -lo] 

182 partner += [k + 1, k] 

183 return cls( 

184 asset=np.array(asset, dtype=np.intp), 

185 sign=np.array(sign), 

186 partner=np.array(partner, dtype=np.intp), 

187 lower=np.array(leg_lower), 

188 upper=np.array(leg_upper), 

189 ) 

190 

191 def columns(self, matrix: NDArray[np.float64]) -> NDArray[np.float64]: 

192 """Return ``matrix @ P``: each asset column copied onto its legs with the leg's sign.""" 

193 result: NDArray[np.float64] = matrix[:, self.asset] * self.sign 

194 return result 

195 

196 def to_assets(self, x: NDArray[np.float64], n: int) -> NDArray[np.float64]: 

197 """Return the asset weights ``P @ x`` of the leg weights ``x``.""" 

198 weights = np.zeros(n) 

199 np.add.at(weights, self.asset, self.sign * x) 

200 return weights 

201 

202 def any_leg(self, mask: NDArray[np.bool_], n: int) -> NDArray[np.bool_]: 

203 """Return, per asset, whether any of its legs is set in ``mask``.""" 

204 return np.bincount(self.asset, weights=mask.astype(np.float64), minlength=n) > 0 

205 

206 def with_cap( 

207 self, g: NDArray[np.float64], h: NDArray[np.float64], cap: float | None 

208 ) -> tuple[NDArray[np.float64], NDArray[np.float64]]: 

209 """Return the lifted ``G P``, ``h`` with the gross-exposure row ``sum(x) <= cap`` appended. 

210 

211 ``cap=None`` maps the rows without appending the cap (a cap already 

212 resolved into tightened bounds). 

213 """ 

214 lifted = self.columns(g) 

215 if cap is None: 

216 return lifted, h 

217 return np.vstack([lifted, np.ones((1, self.asset.shape[0]))]), np.append(h, cap) 

218 

219 def to_turning_point(self, tp: TurningPoint, n: int, p: int) -> TurningPoint: 

220 """Map a lifted turning point back to the ``n`` asset weights and the first ``p`` rows. 

221 

222 The lifted equality rows are the original rows in leg columns, so ``nu`` is 

223 unchanged; ``eta`` keeps the first ``p`` rows and drops the gross-exposure cap. 

224 """ 

225 return TurningPoint( 

226 lamb=tp.lamb, 

227 weights=self.to_assets(tp.weights, n), 

228 free=self.any_leg(tp.free, n), 

229 active_ineq=tp.active_ineq[:p], 

230 nu=tp.nu, 

231 eta=tp.eta[:p], 

232 ) 

233 

234 def net(self, x: NDArray[np.float64]) -> NDArray[np.float64]: 

235 """Net out overlapping legs: subtract ``min(u_i, v_i)`` from both legs of each asset. 

236 

237 The asset weights are unchanged and the gross exposure can only fall, so 

238 every constraint that held for ``x`` still holds. 

239 """ 

240 paired = self.partner >= 0 

241 overlap = np.zeros_like(x) 

242 overlap[paired] = np.minimum(x[paired], x[self.partner[paired]]) 

243 return x - overlap 

244 

245 

246def mask_leg_events( 

247 box: NDArray[np.float64], partner: NDArray[np.intp], at_lower: NDArray[np.bool_] 

248) -> NDArray[np.float64]: 

249 """Drop the leave-a-bound events of a leg whose partner is off its lower bound. 

250 

251 While one leg of an asset is free (or at its upper bound), the other leg's 

252 multiplier is twice the leverage row's multiplier, so it reaches zero only 

253 exactly when the row releases. Freeing that leg would put both legs in the free 

254 set and make the lifted free block singular; the row release is the event that 

255 must fire, so the leg's leave events (columns 2 and 3) are removed. 

256 

257 Args: 

258 box: The ``(legs, 4)`` box-event matrix. 

259 partner: The partner leg of every leg (``-1`` for none). 

260 at_lower: Mask of the legs held at their lower bound. 

261 

262 Returns: 

263 A copy of ``box`` with the suppressed events set to ``-inf``. 

264 """ 

265 paired = partner >= 0 

266 suppress = np.zeros(partner.shape[0], dtype=bool) 

267 suppress[paired] = ~at_lower[partner[paired]] 

268 box = box.copy() 

269 box[suppress, 2:] = -np.inf 

270 return box 

271 

272 

273def _gross_lp( 

274 lift: LeverageLift, 

275 a: NDArray[np.float64], 

276 b: NDArray[np.float64], 

277 g: NDArray[np.float64], 

278 h: NDArray[np.float64], 

279 sense: float, 

280) -> tuple[float, NDArray[np.float64]] | None: 

281 """Optimise the gross exposure ``sum(x)`` over the lifted feasible set. 

282 

283 Minimises ``sense * sum(x)`` subject to ``A P x = b``, ``G P x <= h`` and the leg 

284 box, via HiGHS. 

285 

286 Returns: 

287 ``(sum(x), reduced costs of the leg lower bounds)`` at the optimum, or 

288 ``None`` if the linear program has no solution (the caller's own first 

289 vertex then reports the infeasibility). 

290 """ 

291 n_legs = lift.asset.shape[0] 

292 has_ineq = g.shape[0] > 0 

293 result = linprog( 

294 c=np.full(n_legs, sense), 

295 A_eq=lift.columns(a), 

296 b_eq=b, 

297 A_ub=lift.columns(g) if has_ineq else None, 

298 b_ub=h if has_ineq else None, 

299 bounds=list(zip(lift.lower, lift.upper, strict=True)), 

300 method="highs", 

301 ) 

302 if not result.success: 

303 return None 

304 return float(np.sum(result.x)), np.asarray(result.lower.marginals, dtype=np.float64) 

305 

306 

307def tighten_at_minimum_gross( 

308 lower: NDArray[np.float64], 

309 upper: NDArray[np.float64], 

310 a: NDArray[np.float64], 

311 b: NDArray[np.float64], 

312 g: NDArray[np.float64], 

313 h: NDArray[np.float64], 

314 leverage: float, 

315 tol: float, 

316) -> tuple[NDArray[np.float64], NDArray[np.float64], bool]: 

317 """Resolve a cap sitting at the smallest feasible gross exposure. 

318 

319 When ``leverage`` equals ``c_min = min ||w||_1`` over the feasible set, the cap 

320 row is tight at every feasible point and implies a set of zero legs through the 

321 other rows. With a fully-invested budget, ``leverage = 1`` forces every short leg 

322 to zero. Carrying the cap row alongside those rows makes the maximum-return vertex 

323 degenerate: the free set cannot span them all. This is also the one cap at which 

324 Slater's condition fails. 

325 

326 The feasible set is then the optimal face of ``min sum(x)``. By complementary 

327 slackness, a leg whose lower bound carries a positive reduced cost is zero on 

328 that whole face. Pinning it there is therefore exact: the short leg of a split 

329 asset pins ``lower = 0``, and its long leg pins ``upper = 0``. If the cap is 

330 then implied by the tightened box, because ``max sum(x)`` over it is at most 

331 ``leverage``, the row is dropped. 

332 

333 Args: 

334 lower: Asset lower bounds. 

335 upper: Asset upper bounds. 

336 a: Equality-constraint matrix over the assets. 

337 b: Equality-constraint right-hand side. 

338 g: Inequality-constraint matrix over the assets. 

339 h: Inequality-constraint right-hand side. 

340 leverage: The gross-exposure cap ``c``. 

341 tol: Tolerance for comparing the cap with ``c_min`` and for a positive 

342 reduced cost. 

343 

344 Returns: 

345 ``(lower, upper, keep_cap)``: the (possibly tightened) asset bounds and 

346 whether the cap row is still needed. Unchanged bounds and ``True`` when the 

347 cap exceeds ``c_min``. 

348 """ 

349 lift = LeverageLift.from_bounds(lower, upper) 

350 minimum = _gross_lp(lift, a, b, g, h, sense=1.0) 

351 if minimum is None or leverage > minimum[0] + tol * max(1.0, minimum[0]): 

352 return lower, upper, True 

353 

354 pinned = minimum[1] > tol 

355 lower, upper = lower.copy(), upper.copy() 

356 split = lift.partner >= 0 

357 short = split & (lift.sign < 0) & pinned 

358 long = split & (lift.sign > 0) & pinned 

359 lower[lift.asset[short]] = 0.0 

360 upper[lift.asset[long]] = 0.0 

361 

362 maximum = _gross_lp(LeverageLift.from_bounds(lower, upper), a, b, g, h, sense=-1.0) 

363 keep_cap = maximum is None or maximum[0] > leverage + tol * max(1.0, leverage) 

364 return lower, upper, keep_cap