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

95.38

/qpsolvers/solvers/quadprog_.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/>.

"""
Solver interface for `quadprog <https://github.com/quadprog/quadprog>`__.

quadprog is a C implementation of the Goldfarb-Idnani dual algorithm
[Goldfarb1983]_. It works best on well-conditioned dense problems.
"""

import warnings
from typing import Optional, Tuple

import numpy as np
from numpy import hstack, vstack
from quadprog import solve_qp

from ..conversions import linear_from_box_inequalities, split_dual_linear_box
from ..exceptions import ProblemError
from ..problem import Problem
from ..solution import Solution


def quadprog_solve_problem(
    problem: Problem,
    initvals: Optional[np.ndarray] = None,
    verbose: bool = False,
    **kwargs,
) -> Solution:
    """
    Solve a quadratic program using `quadprog
    <https://pypi.python.org/pypi/quadprog/>`_.

    Parameters
    ----------
    problem :
        Quadratic program to solve.
    initvals :
        Warm-start guess vector (not used).
    verbose :
        Set to `True` to print out extra information.

    Returns
    -------
    :
        Solution to the QP, if found, otherwise ``None``.

    Raises
    ------
    ProblemError :
        If the problem is ill-formed in some way, for instance if some matrices
        are not dense.

    Note
    ----
    The quadprog solver only considers the lower entries of :math:`P`,
    therefore it will use a different cost than the one intended if a
    non-symmetric matrix is provided.

    Notes
    -----
    All other keyword arguments are forwarded to the quadprog solver. For
    instance, you can call ``quadprog_solve_qp(P, q, G, h, factorized=True)``.
    See the solver documentation for details.
    """
    P, q, G, h, A, b, lb, ub = problem.unpack()
    if initvals is not None and verbose:
        warnings.warn("warm-start values are ignored by quadprog")
    if lb is not None or ub is not None:
        G, h = linear_from_box_inequalities(G, h, lb, ub, use_sparse=False)
    qp_G = P
    qp_a = -q
    qp_C: Optional[np.ndarray] = None
    qp_b: Optional[np.ndarray] = None
    if A is not None and b is not None:
        if G is not None and h is not None:
            qp_C = -vstack([A, G]).T
            qp_b = -hstack([b, h])
        else:
            qp_C = -A.T
            qp_b = -b
        meq = A.shape[0]
    else:  # no equality constraint
        if G is not None and h is not None:
            qp_C = -G.T
            qp_b = -h
        meq = 0

    try:
        x, obj, xu, iterations, y, iact = solve_qp(
            qp_G, qp_a, qp_C, qp_b, meq, **kwargs
        )
    except TypeError as error:
        if problem.has_sparse:
            raise ProblemError("problem has sparse matrices") from error
        raise ProblemError(str(error)) from error
    except ValueError as error:
        error_message = str(error)
        if "matrix G is not positive definite" in error_message:
            # quadprog writes G the cost matrix that we write P in this package
            raise ValueError("matrix P is not positive definite") from error
        if "no solution" in error_message:
            return Solution(problem)
        warnings.warn(f"quadprog raised a ValueError: {error_message}")
        return Solution(problem)

    solution = Solution(problem)
    solution.x = x
    solution.obj = obj

    z, ys, z_box = __convert_dual_multipliers(y, meq, lb, ub)
    solution.y = ys
    solution.z = z
    solution.z_box = z_box

    solution.extras = {
        "iact": iact,
        "iterations": iterations,
        "xu": xu,
    }
    return solution


def __convert_dual_multipliers(
    y: np.ndarray,
    meq: int,
    lb: Optional[np.ndarray],
    ub: Optional[np.ndarray],
) -> Tuple[Optional[np.ndarray], Optional[np.ndarray], Optional[np.ndarray]]:
    """
    Convert dual multipliers from quadprog to qpsolvers QP formulation.

    Parameters
    ----------
    y :
        Dual multipliers from quadprog.
    n :
        Number of optimization variables.
    m :
        Number of (in)equality constraints.
    meq :
        Number of equality constraints.
    lb :
        Lower bound vector for box inequalities, if any.
    ub :
        Upper bound vector for box inequalities, if any.

    Returns
    -------
    :
        Tuple of dual multipliers :code:`z, ys, z_box` corresponding
        respectively to linear inequalities, linear equalities, and box
        inequalities.

    Raises
    ------
    ProblemError :
        If the problem is ill-formed in some way, for instance if some matrices
        are not dense.
    """
    z, ys, z_box = None, None, None
    if meq > 0:
        ys = y[:meq]
    z, z_box = split_dual_linear_box(y[meq:], lb, ub)
    return z, ys, z_box


def quadprog_solve_qp(
    P: np.ndarray,
    q: np.ndarray,
    G: Optional[np.ndarray] = None,
    h: Optional[np.ndarray] = None,
    A: Optional[np.ndarray] = None,
    b: Optional[np.ndarray] = None,
    lb: Optional[np.ndarray] = None,
    ub: Optional[np.ndarray] = None,
    initvals: Optional[np.ndarray] = None,
    verbose: bool = False,
    **kwargs,
) -> Optional[np.ndarray]:
    """
    Solve 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}

    using `quadprog <https://pypi.python.org/pypi/quadprog/>`_.

    Parameters
    ----------
    P :
        Symmetric cost matrix.
    q :
        Cost vector.
    G :
        Linear inequality constraint matrix.
    h :
        Linear inequality constraint vector.
    A :
        Linear equality constraint matrix.
    b :
        Linear equality constraint vector.
    lb :
        Lower bound constraint vector.
    ub :
        Upper bound constraint vector.
    initvals :
        Warm-start guess vector (not used).
    verbose :
        Set to `True` to print out extra information.

    Returns
    -------
    :
        Primal solution to the QP, if found, otherwise ``None``.
    """
    warnings.warn(
        "The return type of this function will change "
        "to qpsolvers.Solution in qpsolvers v3.0",
        DeprecationWarning,
        stacklevel=2,
    )
    problem = Problem(P, q, G, h, A, b, lb, ub)
    solution = quadprog_solve_problem(problem, initvals, verbose, **kwargs)
    return solution.x

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	Solver interface for `quadprog <https://github.com/quadprog/quadprog>`__.
23
24	quadprog is a C implementation of the Goldfarb-Idnani dual algorithm
25	[Goldfarb1983]_. It works best on well-conditioned dense problems.
26	"""
27
28	import warnings	1✔
29	from typing import Optional, Tuple	1✔
30
31	import numpy as np	1✔
32	from numpy import hstack, vstack	1✔
33	from quadprog import solve_qp	1✔
34
35	from ..conversions import linear_from_box_inequalities, split_dual_linear_box	1✔
36	from ..exceptions import ProblemError	1✔
37	from ..problem import Problem	1✔
38	from ..solution import Solution	1✔
39
40
41	def quadprog_solve_problem(	1✔
42	problem: Problem,
43	initvals: Optional[np.ndarray] = None,
44	verbose: bool = False,
45	**kwargs,
46	) -> Solution:
47	"""
48	Solve a quadratic program using `quadprog
49	<https://pypi.python.org/pypi/quadprog/>`_.
50
51	Parameters
52	----------
53	problem :
54	Quadratic program to solve.
55	initvals :
56	Warm-start guess vector (not used).
57	verbose :
58	Set to `True` to print out extra information.
59
60	Returns
61	-------
62	:
63	Solution to the QP, if found, otherwise ``None``.
64
65	Raises
66	------
67	ProblemError :
68	If the problem is ill-formed in some way, for instance if some matrices
69	are not dense.
70
71	Note
72	----
73	The quadprog solver only considers the lower entries of :math:`P`,
74	therefore it will use a different cost than the one intended if a
75	non-symmetric matrix is provided.
76
77	Notes
78	-----
79	All other keyword arguments are forwarded to the quadprog solver. For
80	instance, you can call ``quadprog_solve_qp(P, q, G, h, factorized=True)``.
81	See the solver documentation for details.
82	"""
83	P, q, G, h, A, b, lb, ub = problem.unpack()	1✔
84	if initvals is not None and verbose:	1✔
85	warnings.warn("warm-start values are ignored by quadprog")	1✔
86	if lb is not None or ub is not None:	1✔
87	G, h = linear_from_box_inequalities(G, h, lb, ub, use_sparse=False)	1✔
88	qp_G = P	1✔
89	qp_a = -q	1✔
90	qp_C: Optional[np.ndarray] = None	1✔
91	qp_b: Optional[np.ndarray] = None	1✔
92	if A is not None and b is not None:	1✔
93	if G is not None and h is not None:	1✔
94	qp_C = -vstack([A, G]).T	1✔
95	qp_b = -hstack([b, h])	1✔
96	else:
97	qp_C = -A.T	1✔
98	qp_b = -b	1✔
99	meq = A.shape[0]	1✔
100	else: # no equality constraint
101	if G is not None and h is not None:	1✔
102	qp_C = -G.T	1✔
103	qp_b = -h	1✔
104	meq = 0	1✔
105
106	try:	1✔
107	x, obj, xu, iterations, y, iact = solve_qp(	1✔
108	qp_G, qp_a, qp_C, qp_b, meq, **kwargs
109	)
110	except TypeError as error:	1✔
111	if problem.has_sparse:	×
112	raise ProblemError("problem has sparse matrices") from error	×
113	raise ProblemError(str(error)) from error	×
114	except ValueError as error:	1✔
115	error_message = str(error)	1✔
116	if "matrix G is not positive definite" in error_message:	1✔
117	# quadprog writes G the cost matrix that we write P in this package
118	raise ValueError("matrix P is not positive definite") from error	1✔
119	if "no solution" in error_message:	1✔
120	return Solution(problem)	1✔
121	warnings.warn(f"quadprog raised a ValueError: {error_message}")	1✔
122	return Solution(problem)	1✔
123
124	solution = Solution(problem)	1✔
125	solution.x = x	1✔
126	solution.obj = obj	1✔
127
128	z, ys, z_box = __convert_dual_multipliers(y, meq, lb, ub)	1✔
129	solution.y = ys	1✔
130	solution.z = z	1✔
131	solution.z_box = z_box	1✔
132
133	solution.extras = {	1✔
134	"iact": iact,
135	"iterations": iterations,
136	"xu": xu,
137	}
138	return solution	1✔
139
140
141	def __convert_dual_multipliers(	1✔
142	y: np.ndarray,
143	meq: int,
144	lb: Optional[np.ndarray],
145	ub: Optional[np.ndarray],
146	) -> Tuple[Optional[np.ndarray], Optional[np.ndarray], Optional[np.ndarray]]:
147	"""
148	Convert dual multipliers from quadprog to qpsolvers QP formulation.
149
150	Parameters
151	----------
152	y :
153	Dual multipliers from quadprog.
154	n :
155	Number of optimization variables.
156	m :
157	Number of (in)equality constraints.
158	meq :
159	Number of equality constraints.
160	lb :
161	Lower bound vector for box inequalities, if any.
162	ub :
163	Upper bound vector for box inequalities, if any.
164
165	Returns
166	-------
167	:
168	Tuple of dual multipliers :code:`z, ys, z_box` corresponding
169	respectively to linear inequalities, linear equalities, and box
170	inequalities.
171
172	Raises
173	------
174	ProblemError :
175	If the problem is ill-formed in some way, for instance if some matrices
176	are not dense.
177	"""
178	z, ys, z_box = None, None, None	1✔
179	if meq > 0:	1✔
180	ys = y[:meq]	1✔
181	z, z_box = split_dual_linear_box(y[meq:], lb, ub)	1✔
182	return z, ys, z_box	1✔
183
184
185	def quadprog_solve_qp(	1✔
186	P: np.ndarray,
187	q: np.ndarray,
188	G: Optional[np.ndarray] = None,
189	h: Optional[np.ndarray] = None,
190	A: Optional[np.ndarray] = None,
191	b: Optional[np.ndarray] = None,
192	lb: Optional[np.ndarray] = None,
193	ub: Optional[np.ndarray] = None,
194	initvals: Optional[np.ndarray] = None,
195	verbose: bool = False,
196	**kwargs,
197	) -> Optional[np.ndarray]:
198	"""
199	Solve a Quadratic Program defined as:
200
201	.. math::
202
203	\\begin{split}\\begin{array}{ll}
204	\\underset{x}{\\mbox{minimize}} &
205	\\frac{1}{2} x^T P x + q^T x \\\\
206	\\mbox{subject to}
207	& G x \\leq h \\\\
208	& A x = b \\\\
209	& lb \\leq x \\leq ub
210	\\end{array}\\end{split}
211
212	using `quadprog <https://pypi.python.org/pypi/quadprog/>`_.
213
214	Parameters
215	----------
216	P :
217	Symmetric cost matrix.
218	q :
219	Cost vector.
220	G :
221	Linear inequality constraint matrix.
222	h :
223	Linear inequality constraint vector.
224	A :
225	Linear equality constraint matrix.
226	b :
227	Linear equality constraint vector.
228	lb :
229	Lower bound constraint vector.
230	ub :
231	Upper bound constraint vector.
232	initvals :
233	Warm-start guess vector (not used).
234	verbose :
235	Set to `True` to print out extra information.
236
237	Returns
238	-------
239	:
240	Primal solution to the QP, if found, otherwise ``None``.
241	"""
242	warnings.warn(	1✔
243	"The return type of this function will change "
244	"to qpsolvers.Solution in qpsolvers v3.0",
245	DeprecationWarning,
246	stacklevel=2,
247	)
248	problem = Problem(P, q, G, h, A, b, lb, ub)	1✔
249	solution = quadprog_solve_problem(problem, initvals, verbose, **kwargs)	1✔
250	return solution.x	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