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

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

2 

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""" 

8 

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. 

13 

14from typing import NamedTuple 

15 

16import numpy as np 

17 

18 

19def _calculate_vsmall() -> float: 

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

21 

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. 

25 

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 

34 

35 

36VSMALL = _calculate_vsmall() 

37 

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

39_EMPTY = np.zeros(0) 

40 

41 

42class Solution(NamedTuple): 

43 """The outcome of a quadratic program. 

44 

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. 

47 

48 Attributes: 

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

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

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

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

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

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

55 constraints. 

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

57 """ 

58 

59 x: np.ndarray 

60 f: float 

61 xu: np.ndarray 

62 iterations: np.ndarray 

63 lagrangian: np.ndarray 

64 iact: np.ndarray 

65 

66 

67class _WarmEntry(NamedTuple): 

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

69 

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

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

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

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

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

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

76 it by dropping the negative ones before resuming. 

77 

78 Attributes: 

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

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

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

82 nact: Size of the active set. 

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

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

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

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

87 """ 

88 

89 J: np.ndarray 

90 R: np.ndarray 

91 iact: np.ndarray 

92 nact: int 

93 xv: np.ndarray 

94 uv: np.ndarray 

95 obj: float 

96 xu: np.ndarray