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
« 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.
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"""
12from __future__ import annotations
14from typing import NamedTuple
16import numpy as np
17from numpy.typing import NDArray
19from .errors import DegenerateProblemError, NumericalError
20from .operators import RCOND_FLOOR, QuadraticForm, bordered_solve, cross
21from .types import TurningPoint
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.
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.
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.
49 Returns:
50 ``(at_upper, at_lower, free_in, fixed_weights)``.
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)
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)
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
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.
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.
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``.
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
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 )
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
165 gamma = cov.matvec(r_alpha) + c.T @ nu_alpha - q
166 delta = cov.matvec(r_beta) + c.T @ nu_beta - mean
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]
178class Segment(NamedTuple):
179 """The affine critical-line segment valid at one turning point.
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.
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 """
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]
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.
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.
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.
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)
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``.
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.
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.
287 Returns:
288 The :class:`Segment` valid below ``state``.
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 )