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

73 statements  

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

1"""Reduced KKT machinery for a Critical Line Algorithm turning point. 

2 

3At each turning point the active set is identified (which box bounds are held, 

4which assets are free) and the reduced KKT system is solved by block elimination 

5to produce the affine critical-line segment ``w(lam) = r_alpha + lam * r_beta``. 

6Both steps are pure functions of the problem data and the active set, so they 

7live here rather than on the ``CLA`` class; the covariance only ever enters 

8through the ``QuadraticForm`` interface, so structured backends never 

9materialise an ``n x n`` matrix. 

10""" 

11 

12from __future__ import annotations 

13 

14from typing import NamedTuple 

15 

16import numpy as np 

17from numpy.typing import NDArray 

18 

19from .errors import DegenerateProblemError, NumericalError 

20from .operators import RCOND_FLOOR, QuadraticForm, bordered_solve, cross 

21from .types import TurningPoint 

22 

23 

24def active_set( 

25 free: NDArray[np.bool_], 

26 weights: NDArray[np.float64], 

27 lower: NDArray[np.float64], 

28 upper: NDArray[np.float64], 

29 tol: float, 

30 allow_empty: bool = False, 

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

32 """Identify the active set at a turning point and the weights pinned to bounds. 

33 

34 A blocked asset sitting (to tolerance) on a bound is held fixed there and 

35 excluded from the reduced KKT solve; every other asset is *in*. Returns the 

36 upper-bound mask, the lower-bound mask, the in-set mask, and the full-length 

37 vector of weights fixed at their bounds. 

38 

39 Args: 

40 free: Boolean mask of the assets free at the turning point. 

41 weights: The turning point's weight vector. 

42 lower: Per-asset lower bounds. 

43 upper: Per-asset upper bounds. 

44 tol: Tolerance for classifying a weight as sitting on a bound. 

45 allow_empty: Accept a turning point with every asset blocked. Only valid 

46 when the reduced system has no constraint rows (no equality rows and 

47 no active inequality rows): the segment is then the vertex itself. 

48 

49 Returns: 

50 ``(at_upper, at_lower, free_in, fixed_weights)``. 

51 

52 Raises: 

53 NumericalError: If every asset is blocked and ``allow_empty`` is not set, 

54 which makes the reduced system singular. 

55 """ 

56 blocked = ~free 

57 if np.all(blocked) and not allow_empty: 

58 msg = "All variables cannot be blocked" 

59 raise NumericalError(msg) 

60 

61 at_upper = blocked & (np.abs(weights - upper) <= tol) # pragma: no mutate 

62 at_lower = blocked & (np.abs(weights - lower) <= tol) # pragma: no mutate 

63 free_in = ~(at_upper | at_lower) 

64 

65 fixed_weights = np.zeros(len(weights)) 

66 fixed_weights[at_upper] = upper[at_upper] 

67 fixed_weights[at_lower] = lower[at_lower] 

68 return at_upper, at_lower, free_in, fixed_weights 

69 

70 

71def solve_kkt( 

72 cov: QuadraticForm, 

73 mean: NDArray[np.float64], 

74 a: NDArray[np.float64], 

75 b: NDArray[np.float64], 

76 g: NDArray[np.float64], 

77 h: NDArray[np.float64], 

78 free_in: NDArray[np.bool_], 

79 fixed_weights: NDArray[np.float64], 

80 active_ineq: NDArray[np.bool_], 

81 linear: NDArray[np.float64] | None = None, 

82 dense: bool = False, 

83) -> tuple[ 

84 NDArray[np.float64], 

85 NDArray[np.float64], 

86 NDArray[np.float64], 

87 NDArray[np.float64], 

88 NDArray[np.float64], 

89 NDArray[np.float64], 

90 NDArray[np.float64], 

91 NDArray[np.float64], 

92]: 

93 """Solve the reduced KKT system for the current critical-line segment. 

94 

95 Block elimination over the *stacked* constraint matrix ``C = [A ; G_S]``, 

96 where ``G_S`` are the currently-active inequality rows held at equality. 

97 Because an active inequality row enters the stationarity/feasibility system 

98 exactly as an equality row does, the same elimination handles both: a 

99 multi-right-hand-side solve against the free covariance block ``Sigma_FF`` 

100 (via the backend, so structured covariances never materialise an 

101 ``n x n`` matrix) feeds an ``(m + |S|) x (m + |S|)`` Schur complement 

102 ``C_F Sigma_FF^{-1} C_F.T``. With no active inequality rows this is the 

103 plain equality solve. 

104 

105 Args: 

106 cov: The covariance as a ``QuadraticForm`` backend. 

107 mean: Vector of expected returns. 

108 a: Equality-constraint matrix ``A`` of ``A w = b``. 

109 b: Equality-constraint right-hand side ``b``. 

110 g: Inequality-constraint matrix ``G`` of ``G w <= h`` (``(p, n)``). 

111 h: Inequality-constraint right-hand side ``h`` (length ``p``). 

112 free_in: Boolean mask of the assets in the reduced solve. 

113 fixed_weights: Full-length weights of the assets held at their bounds. 

114 active_ineq: Boolean mask (length ``p``) of the active inequality rows. 

115 linear: Optional constant linear term ``q`` of the objective 

116 ``w^T Sigma w / 2 - (q + lam mean)^T w``. It enters only the constant 

117 (``lambda``-free) system: one more term on its right-hand side and in 

118 ``gamma``. ``None`` means ``q = 0``. 

119 dense: Solve the bordered system as a whole (see 

120 :func:`cvxcla.operators.bordered_solve`), for a singular ``Sigma_FF``. 

121 

122 Returns: 

123 ``(r_alpha, r_beta, gamma, delta, eta_alpha, eta_beta, nu_alpha, nu_beta)``: 

124 the affine segment ``w(lam) = r_alpha + lam * r_beta``, the box-multiplier 

125 gradients ``gamma``/``delta`` that drive the leave-a-bound events, the 

126 affine inequality multipliers ``eta_alpha + lam * eta_beta`` (length ``p``, 

127 non-zero only on active rows) that drive the release-a-row events, and the 

128 affine equality multipliers ``nu_alpha + lam * nu_beta`` (length ``m``). 

129 Together they satisfy ``Sigma w - q - lam mean + A^T nu + G^T eta = 0`` on 

130 the free assets. 

131 """ 

132 m = a.shape[0] 

133 ns = len(mean) 

134 p = g.shape[0] 

135 out = ~free_in 

136 # Stack the active inequality rows beneath the equality rows; the active 

137 # rows are held at equality (g_i w = h_i), so C/d is the equality system 

138 # of the reduced QP at this vertex. 

139 c = np.vstack([a, g[active_ineq]]) 

140 d = np.concatenate([b, h[active_ineq]]) 

141 c_free = c[:, free_in] 

142 q = np.zeros(ns) if linear is None else linear 

143 

144 # The reduced KKT system is the shared bordered solve: the constant system 

145 # carries the blocked-weight shift -Sigma_FB w_B and the reduced constraint 

146 # right-hand side d - C_B w_B; the slope system carries the mean with a zero 

147 # constraint right-hand side (A r_beta = 0). A linear term q adds q_F to the 

148 # constant system only. 

149 x_alpha, x_beta, nu_alpha, nu_beta = bordered_solve( 

150 cov, 

151 free_in, 

152 c_free, 

153 q[free_in] - cross(cov, free_in, fixed_weights), 

154 mean[free_in], 

155 d - c[:, out] @ fixed_weights[out], 

156 np.zeros(c.shape[0]), 

157 dense=dense, 

158 ) 

159 

160 r_alpha = fixed_weights.copy() 

161 r_alpha[free_in] = x_alpha 

162 r_beta = np.zeros(ns) 

163 r_beta[free_in] = x_beta 

164 

165 gamma = cov.matvec(r_alpha) + c.T @ nu_alpha - q 

166 delta = cov.matvec(r_beta) + c.T @ nu_beta - mean 

167 

168 # The tail of the stacked multiplier is the inequality multiplier eta(lam) 

169 # = eta_alpha + lam eta_beta, scattered back to full length p (zero on the 

170 # inactive rows, which have no release event). 

171 eta_alpha = np.zeros(p) 

172 eta_beta = np.zeros(p) 

173 eta_alpha[active_ineq] = nu_alpha[m:] 

174 eta_beta[active_ineq] = nu_beta[m:] 

175 return r_alpha, r_beta, gamma, delta, eta_alpha, eta_beta, nu_alpha[:m], nu_beta[:m] 

176 

177 

178class Segment(NamedTuple): 

179 """The affine critical-line segment valid at one turning point. 

180 

181 Bundles the affine path ``w(lam) = r_alpha + lam * r_beta``, the multiplier 

182 gradients ``gamma``/``delta`` that drive the leave-a-bound events, and the 

183 active-set masks the event scan needs. This is what ``CLA.segment`` returns 

184 to the generic path tracer. 

185 

186 For general inequality constraints ``G w <= h`` the segment also carries the 

187 affine inequality multipliers ``eta_alpha + lam * eta_beta`` (one entry per 

188 inequality row; meaningful for *active* rows, which release when the 

189 multiplier crosses zero) and the active-row mask ``active_ineq``. The slacks 

190 that drive an *inactive* row becoming active are recomputed from 

191 ``r_alpha``/``r_beta`` directly in :func:`cvxcla._events.ineq_event_ratios`. 

192 The equality multipliers ``nu_alpha + lam * nu_beta`` are carried so the 

193 turning points can record them. 

194 """ 

195 

196 r_alpha: NDArray[np.float64] 

197 r_beta: NDArray[np.float64] 

198 gamma: NDArray[np.float64] 

199 delta: NDArray[np.float64] 

200 at_upper: NDArray[np.bool_] 

201 at_lower: NDArray[np.bool_] 

202 free_in: NDArray[np.bool_] 

203 active_ineq: NDArray[np.bool_] 

204 eta_alpha: NDArray[np.float64] 

205 eta_beta: NDArray[np.float64] 

206 nu_alpha: NDArray[np.float64] 

207 nu_beta: NDArray[np.float64] 

208 

209 

210def guard_active_rows(c: NDArray[np.float64], free_in: NDArray[np.bool_], lamb: float) -> None: 

211 """Refuse a partition whose active rows are linearly dependent on the free set. 

212 

213 The Schur complement ``C_F Sigma_FF^{-1} C_F^T`` of the reduced solve is singular 

214 when ``C_F`` (the equality rows and the active inequality rows, restricted to the 

215 free assets) loses row rank: more active rows than free assets, or rows that 

216 coincide on the free set (several caps binding at once in the same direction). 

217 The partition is then outside the algorithm's domain -- the linear-independence 

218 assumption of its termination argument fails -- and the solve cannot be trusted, 

219 so it is declined here instead of producing an infeasible turning point. The 

220 rows are normalised first, so the test does not depend on their scaling. 

221 

222 Args: 

223 c: The active constraint rows ``[A ; G_active]`` (``(m + |S|) x n``). 

224 free_in: Boolean mask of the assets in the reduced solve. 

225 lamb: The lambda of the turning point, for the diagnosis. 

226 

227 Raises: 

228 DegenerateProblemError: If ``c[:, free_in]`` has fewer columns than rows, or 

229 a reciprocal condition number below the singularity floor. 

230 """ 

231 rows = c.shape[0] 

232 if rows == 0: 

233 return 

234 block = c[:, free_in] 

235 n_free = block.shape[1] 

236 norms = np.linalg.norm(block, axis=1) 

237 if n_free >= rows and np.all(norms > 0): 

238 sv = np.linalg.svd(block / norms[:, None], compute_uv=False) 

239 if sv[-1] >= RCOND_FLOOR * sv[0]: 

240 return 

241 msg = ( 

242 f"The active constraints are linearly dependent on the free set at lambda={lamb:.4g} " 

243 f"({rows} active rows, {n_free} free assets): the reduced KKT system is singular. This " 

244 "happens when several constraints bind at once in the same direction; remove redundant " 

245 "rows or loosen one of the caps." 

246 ) 

247 raise DegenerateProblemError(msg) 

248 

249 

250def critical_segment( 

251 cov: QuadraticForm, 

252 mean: NDArray[np.float64], 

253 a: NDArray[np.float64], 

254 b: NDArray[np.float64], 

255 g: NDArray[np.float64], 

256 h: NDArray[np.float64], 

257 lower: NDArray[np.float64], 

258 upper: NDArray[np.float64], 

259 tol: float, 

260 state: TurningPoint, 

261 linear: NDArray[np.float64] | None = None, 

262 well_conditioned: bool = True, 

263) -> Segment: 

264 """Solve the reduced KKT system for the critical-line segment at ``state``. 

265 

266 Composes :func:`active_set` (which bounds are held at the turning point) with 

267 :func:`solve_kkt` (the block-eliminated reduced solve) and bundles the result 

268 with the masks the event scan needs. 

269 

270 Args: 

271 cov: The covariance as a ``QuadraticForm`` backend. 

272 mean: Vector of expected returns. 

273 a: Equality-constraint matrix ``A`` of ``A w = b``. 

274 b: Equality-constraint right-hand side ``b``. 

275 g: Inequality-constraint matrix ``G`` of ``G w <= h`` (``(p, n)``). 

276 h: Inequality-constraint right-hand side ``h`` (length ``p``). 

277 lower: Per-asset lower bounds. 

278 upper: Per-asset upper bounds. 

279 tol: Tolerance for classifying a weight as sitting on a bound. 

280 state: The turning point the segment starts from. 

281 linear: Optional constant linear term ``q`` (see :func:`solve_kkt`). 

282 well_conditioned: Whether every free block of ``cov`` is known to be 

283 nonsingular (see :func:`cvxcla._checks.well_conditioned`). When it is not, 

284 a free block below the singularity floor is solved through the whole 

285 bordered system. 

286 

287 Returns: 

288 The :class:`Segment` valid below ``state``. 

289 

290 Raises: 

291 DegenerateProblemError: If the active rows do not have full row rank on the 

292 free set (see :func:`guard_active_rows`). 

293 """ 

294 rows = np.vstack([a, g[state.active_ineq]]) 

295 # With no constraint rows an all-blocked vertex is nondegenerate (free count == 

296 # row count == 0): the maximum-return vertex of a box-only problem is one. 

297 at_upper, at_lower, free_in, fixed_weights = active_set( 

298 state.free, state.weights, lower, upper, tol, allow_empty=rows.shape[0] == 0 

299 ) 

300 guard_active_rows(rows, free_in, state.lamb) 

301 dense = not well_conditioned and float(cov.rcond_free(np.flatnonzero(free_in))) < RCOND_FLOOR 

302 r_alpha, r_beta, gamma, delta, eta_alpha, eta_beta, nu_alpha, nu_beta = solve_kkt( 

303 cov, mean, a, b, g, h, free_in, fixed_weights, state.active_ineq, linear, dense 

304 ) 

305 return Segment( 

306 r_alpha, 

307 r_beta, 

308 gamma, 

309 delta, 

310 at_upper, 

311 at_lower, 

312 free_in, 

313 state.active_ineq, 

314 eta_alpha, 

315 eta_beta, 

316 nu_alpha, 

317 nu_beta, 

318 )