Coverage for src/cvxcla/_kkt.py: 100%
36 statements
« prev ^ index » next coverage.py v7.15.4, created at 2026-08-11 09:58 +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
14import numpy as np
15from numpy.typing import NDArray
17from .operators import QuadraticForm, bordered_solve, cross
20def active_set(
21 free: NDArray[np.bool_],
22 weights: NDArray[np.float64],
23 lower: NDArray[np.float64],
24 upper: NDArray[np.float64],
25 tol: float,
26) -> tuple[NDArray[np.bool_], NDArray[np.bool_], NDArray[np.bool_], NDArray[np.float64]]:
27 """Identify the active set at a turning point and the weights pinned to bounds.
29 A blocked asset sitting (to tolerance) on a bound is held fixed there and
30 excluded from the reduced KKT solve; every other asset is *in*. Returns the
31 upper-bound mask, the lower-bound mask, the in-set mask, and the full-length
32 vector of weights fixed at their bounds.
34 Args:
35 free: Boolean mask of the assets free at the turning point.
36 weights: The turning point's weight vector.
37 lower: Per-asset lower bounds.
38 upper: Per-asset upper bounds.
39 tol: Tolerance for classifying a weight as sitting on a bound.
41 Returns:
42 ``(at_upper, at_lower, free_in, fixed_weights)``.
44 Raises:
45 RuntimeError: If every asset is blocked, which makes the reduced system
46 singular.
47 """
48 blocked = ~free
49 if np.all(blocked):
50 msg = "All variables cannot be blocked"
51 raise RuntimeError(msg)
53 at_upper = blocked & (np.abs(weights - upper) <= tol) # pragma: no mutate
54 at_lower = blocked & (np.abs(weights - lower) <= tol) # pragma: no mutate
55 free_in = ~(at_upper | at_lower)
57 fixed_weights = np.zeros(len(weights))
58 fixed_weights[at_upper] = upper[at_upper]
59 fixed_weights[at_lower] = lower[at_lower]
60 return at_upper, at_lower, free_in, fixed_weights
63def solve_kkt(
64 cov: QuadraticForm,
65 mean: NDArray[np.float64],
66 a: NDArray[np.float64],
67 b: NDArray[np.float64],
68 g: NDArray[np.float64],
69 h: NDArray[np.float64],
70 free_in: NDArray[np.bool_],
71 fixed_weights: NDArray[np.float64],
72 active_ineq: NDArray[np.bool_],
73) -> tuple[
74 NDArray[np.float64],
75 NDArray[np.float64],
76 NDArray[np.float64],
77 NDArray[np.float64],
78 NDArray[np.float64],
79 NDArray[np.float64],
80]:
81 """Solve the reduced KKT system for the current critical-line segment.
83 Block elimination over the *stacked* constraint matrix ``C = [A ; G_S]``,
84 where ``G_S`` are the currently-active inequality rows held at equality.
85 Because an active inequality row enters the stationarity/feasibility system
86 exactly as an equality row does, the same elimination handles both: a
87 multi-right-hand-side solve against the free covariance block ``Sigma_FF``
88 (via the backend, so structured covariances never materialise an
89 ``n x n`` matrix) feeds an ``(m + |S|) x (m + |S|)`` Schur complement
90 ``C_F Sigma_FF^{-1} C_F.T``. With no active inequality rows this is the
91 plain equality solve.
93 Args:
94 cov: The covariance as a ``QuadraticForm`` backend.
95 mean: Vector of expected returns.
96 a: Equality-constraint matrix ``A`` of ``A w = b``.
97 b: Equality-constraint right-hand side ``b``.
98 g: Inequality-constraint matrix ``G`` of ``G w <= h`` (``(p, n)``).
99 h: Inequality-constraint right-hand side ``h`` (length ``p``).
100 free_in: Boolean mask of the assets in the reduced solve.
101 fixed_weights: Full-length weights of the assets held at their bounds.
102 active_ineq: Boolean mask (length ``p``) of the active inequality rows.
104 Returns:
105 ``(r_alpha, r_beta, gamma, delta, eta_alpha, eta_beta)``: the affine
106 segment ``w(lam) = r_alpha + lam * r_beta``, the box-multiplier
107 gradients ``gamma``/``delta`` that drive the leave-a-bound events, and
108 the affine inequality multipliers ``eta_alpha + lam * eta_beta``
109 (length ``p``, non-zero only on active rows) that drive the
110 release-a-row events.
111 """
112 m = a.shape[0]
113 ns = len(mean)
114 p = g.shape[0]
115 out = ~free_in
116 # Stack the active inequality rows beneath the equality rows; the active
117 # rows are held at equality (g_i w = h_i), so C/d is the equality system
118 # of the reduced QP at this vertex.
119 c = np.vstack([a, g[active_ineq]])
120 d = np.concatenate([b, h[active_ineq]])
121 c_free = c[:, free_in]
123 # The reduced KKT system is the shared bordered solve: the constant system
124 # carries the blocked-weight shift -Sigma_FB w_B and the reduced constraint
125 # right-hand side d - C_B w_B; the slope system carries the mean with a zero
126 # constraint right-hand side (A r_beta = 0).
127 x_alpha, x_beta, nu_alpha, nu_beta = bordered_solve(
128 cov,
129 free_in,
130 c_free,
131 -cross(cov, free_in, fixed_weights),
132 mean[free_in],
133 d - c[:, out] @ fixed_weights[out],
134 np.zeros(c.shape[0]),
135 )
137 r_alpha = fixed_weights.copy()
138 r_alpha[free_in] = x_alpha
139 r_beta = np.zeros(ns)
140 r_beta[free_in] = x_beta
142 gamma = cov.matvec(r_alpha) + c.T @ nu_alpha
143 delta = cov.matvec(r_beta) + c.T @ nu_beta - mean
145 # The tail of the stacked multiplier is the inequality multiplier eta(lam)
146 # = eta_alpha + lam eta_beta, scattered back to full length p (zero on the
147 # inactive rows, which have no release event).
148 eta_alpha = np.zeros(p)
149 eta_beta = np.zeros(p)
150 eta_alpha[active_ineq] = nu_alpha[m:]
151 eta_beta[active_ineq] = nu_beta[m:]
152 return r_alpha, r_beta, gamma, delta, eta_alpha, eta_beta