3822948223

Build Type

github

Committed by GitHub

Commit Message

Merge 797177457 into 777bddb92

Pull Request Pull Request #145: Sparse box inequality conversions

Run Details

63 of 63 new or added lines in 9 files covered. (100.0%)

1709 of 1950 relevant lines covered (87.64%)

0.88 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.3

/qpsolvers/problem.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Copyright (C) 2016-2022 Stéphane Caron and the qpsolvers contributors.
#
# This file is part of qpsolvers.
#
# qpsolvers is free software: you can redistribute it and/or modify it under
# the terms of the GNU Lesser General Public License as published by the Free
# Software Foundation, either version 3 of the License, or (at your option) any
# later version.
#
# qpsolvers is distributed in the hope that it will be useful, but WITHOUT ANY
# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
# A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
# details.
#
# You should have received a copy of the GNU Lesser General Public License
# along with qpsolvers. If not, see <http://www.gnu.org/licenses/>.

"""
Model for a quadratic program.
"""

import warnings
from typing import Optional, Tuple, Union

import numpy as np
import scipy.sparse as spa

from .conversions import linear_from_box_inequalities


class Problem:

    """
    Model for a quadratic program defined as:

    .. math::

        \\begin{split}\\begin{array}{ll}
            \\underset{x}{\\mbox{minimize}} &
                \\frac{1}{2} x^T P x + q^T x \\\\
            \\mbox{subject to}
                & G x \\leq h                \\\\
                & A x = b                    \\\\
                & lb \\leq x \\leq ub
        \\end{array}\\end{split}

    This class provides sanity checks and metrics such as the condition number
    of a problem.

    Attributes
    ----------
    P :
        Symmetric cost matrix (most solvers require it to be definite
        as well).
    q :
        Cost vector.
    G :
        Linear inequality matrix.
    h :
        Linear inequality vector.
    A :
        Linear equality matrix.
    b :
        Linear equality vector.
    lb :
        Lower bound constraint vector.
    ub :
        Upper bound constraint vector.
    """

    P: Union[np.ndarray, spa.csc_matrix]
    q: np.ndarray
    G: Optional[Union[np.ndarray, spa.csc_matrix]] = None
    h: Optional[np.ndarray] = None
    A: Optional[Union[np.ndarray, spa.csc_matrix]] = None
    b: Optional[np.ndarray] = None
    lb: Optional[np.ndarray] = None
    ub: Optional[np.ndarray] = None

    def __init__(
        self,
        P: Union[np.ndarray, spa.csc_matrix],
        q: np.ndarray,
        G: Optional[Union[np.ndarray, spa.csc_matrix]] = None,
        h: Optional[np.ndarray] = None,
        A: Optional[Union[np.ndarray, spa.csc_matrix]] = None,
        b: Optional[np.ndarray] = None,
        lb: Optional[np.ndarray] = None,
        ub: Optional[np.ndarray] = None,
    ) -> None:
        if isinstance(A, np.ndarray) and A.ndim == 1:
            A = A.reshape((1, A.shape[0]))
        if isinstance(G, np.ndarray) and G.ndim == 1:
            G = G.reshape((1, G.shape[0]))
        self.P = P
        self.q = q
        self.G = G
        self.h = h
        self.A = A
        self.b = b
        self.lb = lb
        self.ub = ub

    @property
    def has_sparse(self) -> bool:
        """
        Check whether the problem has sparse matrices.

        Returns
        -------
        :
            True if at least one of the :math:`P`, :math:`G` or :math:`A`
            matrices is sparse.
        """
        sparse_types = (spa.csc_matrix, spa.dia_matrix)
        return (
            isinstance(self.P, sparse_types)
            or isinstance(self.G, sparse_types)
            or isinstance(self.A, sparse_types)
        )

    def unpack(
        self,
    ) -> Tuple[
        Union[np.ndarray, spa.csc_matrix],
        np.ndarray,
        Optional[Union[np.ndarray, spa.csc_matrix]],
        Optional[np.ndarray],
        Optional[Union[np.ndarray, spa.csc_matrix]],
        Optional[np.ndarray],
        Optional[np.ndarray],
        Optional[np.ndarray],
    ]:
        """
        Get problem matrices as a tuple.

        Returns
        -------
        :
            Tuple ``(P, q, G, h, A, b, lb, ub)`` of problem matrices.
        """
        return (
            self.P,
            self.q,
            self.G,
            self.h,
            self.A,
            self.b,
            self.lb,
            self.ub,
        )

    def check_constraints(self):
        """
        Check that problem constraints are properly specified.

        Raises
        ------
        ValueError
            If the constraints are not properly defined.
        """
        if self.G is None and self.h is not None:
            raise ValueError("incomplete inequality constraint (missing h)")
        if self.G is not None and self.h is None:
            raise ValueError("incomplete inequality constraint (missing G)")
        if self.A is None and self.b is not None:
            raise ValueError("incomplete equality constraint (missing b)")
        if self.A is not None and self.b is None:
            raise ValueError("incomplete equality constraint (missing A)")

    def cond(self):
        """
        Compute the condition number of the symmetric matrix representing the
        problem data:

        .. math::

            M =
            \\begin{bmatrix}
                P & G^T & A^T \\\\
                G & 0   & 0   \\\\
                A & 0   & 0
            \\end{bmatrix}

        Returns
        -------
        :
            Condition number of the problem.

        Notes
        -----
        Having a low condition number (say, less than 1e10) condition number is
        strongly tied to the capacity of numerical solvers to solve a problem.
        This is the motivation for preconditioning, as detailed for instance in
        Section 5 of [Stellato2020]_.
        """
        if self.has_sparse:
            warnings.warn("The cond() function is for dense problems")
        P, A = self.P, self.A
        G, _ = linear_from_box_inequalities(
            self.G, self.h, self.lb, self.ub, use_sparse=False
        )
        if G is None and A is None:
            M = P
        elif A is None:  # G is not None
            M = np.vstack(
                [
                    np.hstack([P, G.T]),
                    np.hstack([G, np.zeros((G.shape[0], G.shape[0]))]),
                ]
            )
        else:  # G is not None and A is not None
            M = np.vstack(
                [
                    np.hstack([P, G.T, A.T]),
                    np.hstack(
                        [
                            G,
                            np.zeros((G.shape[0], G.shape[0])),
                            np.zeros((G.shape[0], A.shape[0])),
                        ]
                    ),
                    np.hstack(
                        [
                            A,
                            np.zeros((A.shape[0], G.shape[0])),
                            np.zeros((A.shape[0], A.shape[0])),
                        ]
                    ),
                ]
            )
        return np.linalg.cond(M)

1	#!/usr/bin/env python
2	# -- coding: utf-8 --
3	#
4	# Copyright (C) 2016-2022 Stéphane Caron and the qpsolvers contributors.
5	#
6	# This file is part of qpsolvers.
7	#
8	# qpsolvers is free software: you can redistribute it and/or modify it under
9	# the terms of the GNU Lesser General Public License as published by the Free
10	# Software Foundation, either version 3 of the License, or (at your option) any
11	# later version.
12	#
13	# qpsolvers is distributed in the hope that it will be useful, but WITHOUT ANY
14	# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
15	# A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
16	# details.
17	#
18	# You should have received a copy of the GNU Lesser General Public License
19	# along with qpsolvers. If not, see <http://www.gnu.org/licenses/>.
20
21	"""	1✔
22	Model for a quadratic program.
23	"""
24
25	import warnings	1✔
26	from typing import Optional, Tuple, Union	1✔
27
28	import numpy as np	1✔
29	import scipy.sparse as spa	1✔
30
31	from .conversions import linear_from_box_inequalities	1✔
32
33
34	class Problem:	1✔
35
36	"""
37	Model for a quadratic program defined as:
38
39	.. math::
40
41	\\begin{split}\\begin{array}{ll}
42	\\underset{x}{\\mbox{minimize}} &
43	\\frac{1}{2} x^T P x + q^T x \\\\
44	\\mbox{subject to}
45	& G x \\leq h \\\\
46	& A x = b \\\\
47	& lb \\leq x \\leq ub
48	\\end{array}\\end{split}
49
50	This class provides sanity checks and metrics such as the condition number
51	of a problem.
52
53	Attributes
54	----------
55	P :
56	Symmetric cost matrix (most solvers require it to be definite
57	as well).
58	q :
59	Cost vector.
60	G :
61	Linear inequality matrix.
62	h :
63	Linear inequality vector.
64	A :
65	Linear equality matrix.
66	b :
67	Linear equality vector.
68	lb :
69	Lower bound constraint vector.
70	ub :
71	Upper bound constraint vector.
72	"""
73
74	P: Union[np.ndarray, spa.csc_matrix]	1✔
75	q: np.ndarray	1✔
76	G: Optional[Union[np.ndarray, spa.csc_matrix]] = None	1✔
77	h: Optional[np.ndarray] = None	1✔
78	A: Optional[Union[np.ndarray, spa.csc_matrix]] = None	1✔
79	b: Optional[np.ndarray] = None	1✔
80	lb: Optional[np.ndarray] = None	1✔
81	ub: Optional[np.ndarray] = None	1✔
82
83	def __init__(	1✔
84	self,
85	P: Union[np.ndarray, spa.csc_matrix],
86	q: np.ndarray,
87	G: Optional[Union[np.ndarray, spa.csc_matrix]] = None,
88	h: Optional[np.ndarray] = None,
89	A: Optional[Union[np.ndarray, spa.csc_matrix]] = None,
90	b: Optional[np.ndarray] = None,
91	lb: Optional[np.ndarray] = None,
92	ub: Optional[np.ndarray] = None,
93	) -> None:
94	if isinstance(A, np.ndarray) and A.ndim == 1:	1✔
95	A = A.reshape((1, A.shape[0]))	1✔
96	if isinstance(G, np.ndarray) and G.ndim == 1:	1✔
97	G = G.reshape((1, G.shape[0]))	1✔
98	self.P = P	1✔
99	self.q = q	1✔
100	self.G = G	1✔
101	self.h = h	1✔
102	self.A = A	1✔
103	self.b = b	1✔
104	self.lb = lb	1✔
105	self.ub = ub	1✔
106
107	@property	1✔
108	def has_sparse(self) -> bool:	1✔
109	"""
110	Check whether the problem has sparse matrices.
111
112	Returns
113	-------
114	:
115	True if at least one of the :math:`P`, :math:`G` or :math:`A`
116	matrices is sparse.
117	"""
118	sparse_types = (spa.csc_matrix, spa.dia_matrix)	1✔
119	return (	1✔
120	isinstance(self.P, sparse_types)
121	or isinstance(self.G, sparse_types)
122	or isinstance(self.A, sparse_types)
123	)
124
125	def unpack(	1✔
126	self,
127	) -> Tuple[
128	Union[np.ndarray, spa.csc_matrix],
129	np.ndarray,
130	Optional[Union[np.ndarray, spa.csc_matrix]],
131	Optional[np.ndarray],
132	Optional[Union[np.ndarray, spa.csc_matrix]],
133	Optional[np.ndarray],
134	Optional[np.ndarray],
135	Optional[np.ndarray],
136	]:
137	"""
138	Get problem matrices as a tuple.
139
140	Returns
141	-------
142	:
143	Tuple ``(P, q, G, h, A, b, lb, ub)`` of problem matrices.
144	"""
145	return (	1✔
146	self.P,
147	self.q,
148	self.G,
149	self.h,
150	self.A,
151	self.b,
152	self.lb,
153	self.ub,
154	)
155
156	def check_constraints(self):	1✔
157	"""
158	Check that problem constraints are properly specified.
159
160	Raises
161	------
162	ValueError
163	If the constraints are not properly defined.
164	"""
165	if self.G is None and self.h is not None:	1✔
166	raise ValueError("incomplete inequality constraint (missing h)")	1✔
167	if self.G is not None and self.h is None:	1✔
168	raise ValueError("incomplete inequality constraint (missing G)")	1✔
169	if self.A is None and self.b is not None:	1✔
170	raise ValueError("incomplete equality constraint (missing b)")	1✔
171	if self.A is not None and self.b is None:	1✔
172	raise ValueError("incomplete equality constraint (missing A)")	1✔
173
174	def cond(self):	1✔
175	"""
176	Compute the condition number of the symmetric matrix representing the
177	problem data:
178
179	.. math::
180
181	M =
182	\\begin{bmatrix}
183	P & G^T & A^T \\\\
184	G & 0 & 0 \\\\
185	A & 0 & 0
186	\\end{bmatrix}
187
188	Returns
189	-------
190	:
191	Condition number of the problem.
192
193	Notes
194	-----
195	Having a low condition number (say, less than 1e10) condition number is
196	strongly tied to the capacity of numerical solvers to solve a problem.
197	This is the motivation for preconditioning, as detailed for instance in
198	Section 5 of [Stellato2020]_.
199	"""
200	if self.has_sparse:	1✔
201	warnings.warn("The cond() function is for dense problems")	×
202	P, A = self.P, self.A	1✔
203	G, _ = linear_from_box_inequalities(	1✔
204	self.G, self.h, self.lb, self.ub, use_sparse=False
205	)
206	if G is None and A is None:	1✔
207	M = P	1✔
208	elif A is None: # G is not None	1✔
209	M = np.vstack(	×
210	[
211	np.hstack([P, G.T]),
212	np.hstack([G, np.zeros((G.shape[0], G.shape[0]))]),
213	]
214	)
215	else: # G is not None and A is not None
216	M = np.vstack(	1✔
217	[
218	np.hstack([P, G.T, A.T]),
219	np.hstack(
220	[
221	G,
222	np.zeros((G.shape[0], G.shape[0])),
223	np.zeros((G.shape[0], A.shape[0])),
224	]
225	),
226	np.hstack(
227	[
228	A,
229	np.zeros((A.shape[0], G.shape[0])),
230	np.zeros((A.shape[0], A.shape[0])),
231	]
232	),
233	]
234	)
235	return np.linalg.cond(M)	1✔

stephane-caron / qpsolvers / 3822948223

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous