Coverage for src/cvx/quadprog/

1"""The values and records the rest of the package is written in terms of.

3Kept apart from the algorithm because everything depends on them and they

4depend on nothing: giving them their own module is what lets the fast path

5build a :class:`Solution` without importing the solver that normally returns

6one, which would be a cycle.

7"""

9# G, C, R and J are the names used in Goldfarb & Idnani (1983) and in the

10# reference implementation's public signature `solve_qp(G, a, C, b, meq)`.

11# Lowercasing them would obscure the correspondence to the paper, so the

12# pep8-naming rules are waived here, as they are in _solve.py.

14from typing import NamedTuple

16import numpy as np

19def _calculate_vsmall() -> float:

20 """Return an upper bound on the relative precision of the arithmetic.

22 Gleaned from Powell's ZQPCVX routine: double the value until it is large

23 enough to perturb 1.0 when scaled by both 0.1 and 0.2. Computed once at

24 import time.

26 Returns:

27 A small positive number, of the order of the machine epsilon.

28 """

29 vsmall = 1e-60

30 while True:

31 vsmall += vsmall

32 if vsmall * 0.1 + 1.0 > 1.0 and vsmall * 0.2 + 1.0 > 1.0:

33 return vsmall

36VSMALL = _calculate_vsmall()

38# Returned for the dual step direction while the active set is still empty.

39_EMPTY = np.zeros(0)

42class Solution(NamedTuple):

43 """The outcome of a quadratic program.

45 Iterating over an instance yields the same six values, in the same order, as

46 the tuple returned by ``quadprog.solve_qp``, so it is a drop-in replacement.

48 That ordering is what the example below pins down, on a problem small enough

49 to check by hand: with ``G`` the identity the objective separates into

50 ``x_i**2 / 2 - a_i x_i`` per coordinate, so subject to ``x >= 0`` the answer

51 is ``a`` with its negative entries clipped to zero.

53 >>> import numpy as np

54 >>> from cvx.quadprog import solve_qp

55 >>> solution = solve_qp(np.eye(2), np.array([1.0, -1.0]), np.eye(2), np.zeros(2))

56 >>> x, f, xu, iterations, lagrangian, iact = solution

57 >>> x.tolist()

58 [1.0, 0.0]

59 >>> xu.tolist()

60 [1.0, -1.0]

61 >>> round(f, 12)

62 -0.5

64 Only the second constraint binds, so ``iact`` names it -- 1-based -- and only

65 its multiplier is non-zero. ``iterations`` is a pair, additions then removals,

66 and its first entry counts *outer iterations*: it therefore exceeds the number

67 of constraints that ended up active, one iteration having brought ``x_2`` onto

68 its bound and a final one confirming there was nothing left to add.

70 >>> iact.tolist()

71 [2]

72 >>> lagrangian.tolist()

73 [0.0, 1.0]

74 >>> iterations.tolist()

75 [2, 0]

77 Attributes:

78 x: ``(n,)`` minimiser of the constrained problem.

79 f: Value of the objective at ``x``.

80 xu: ``(n,)`` minimiser of the unconstrained problem, ``G^-1 a``.

81 iterations: ``(2,)`` count of constraints added to the active set (once

82 per outer iteration) and of constraints removed from it.

83 lagrangian: ``(m,)`` Lagrange multipliers, zero for inactive

84 constraints.

85 iact: 1-based indices of the constraints active at the solution.

86 """

88 x: np.ndarray

89 f: float

90 xu: np.ndarray

91 iterations: np.ndarray

92 lagrangian: np.ndarray

93 iact: np.ndarray

96class _WarmEntry(NamedTuple):

97 """A dual-feasible state to resume the iteration from, instead of cold.

99 Every field is what the iteration would itself hold at the top of an outer

100 pass, so resuming is simply not doing the walk that would have produced them.

101 The precondition is the method's own invariant, and it is the caller's to

102 establish: ``xv`` minimises the objective subject to the constraints in

103 ``iact[:nact]`` held as equalities, and ``uv[:nact]`` are its multipliers with

104 every inequality entry non-negative. :class:`~cvx.quadprog.Sweep` establishes

105 it by dropping the negative ones before resuming.

106

107 Attributes:

108 J: Inverse Cholesky factor, updated for the active set.

109 R: Packed triangular factor of the active constraint normals.

110 iact: 1-based active set, first ``nact`` entries valid.

111 nact: Size of the active set.

112 xv: The iterate, minimising over the active set.

113 uv: Multipliers of the active constraints, non-negative on inequalities.

114 obj: Objective value at ``xv``.

115 xu: Unconstrained minimiser, carried through to the Solution.

116 """

117

118 J: np.ndarray

119 R: np.ndarray

120 iact: np.ndarray

121 nact: int

122 xv: np.ndarray

123 uv: np.ndarray

124 obj: float

125 xu: np.ndarray

Coverage for src/cvx/quadprog/_base.py: 100%

26 statements