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

10.0

/qpsolvers/solvers/qpswift_.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 `qpSWIFT <https://github.com/qpSWIFT/qpSWIFT>`__.

qpSWIFT is a light-weight sparse Quadratic Programming solver targeted for
embedded and robotic applications. It employs Primal-Dual Interior Point method
with Mehrotra Predictor corrector step and Nesterov Todd scaling. For solving
the linear system of equations, sparse LDL' factorization is used along with
approximate minimum degree heuristic to minimize fill-in of the factorizations.
If you use qpSWIFT in your research, consider citing the corresponding paper
[Pandala2019]_.
"""

import warnings
from typing import Optional

import numpy as np
import qpSWIFT

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


def qpswift_solve_problem(
    problem: Problem,
    initvals: Optional[np.ndarray] = None,
    verbose: bool = False,
    **kwargs,
) -> Solution:
    """
    Solve a quadratic program using `qpSWIFT
    <https://github.com/qpSWIFT/qpSWIFT>`__.

    Note
    ----
    This solver does not handle problems without inequality constraints.

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

    Returns
    -------
    :
        Solution returned by the solver.

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

    Note
    ----
    **Rank assumptions:** qpSWIFT requires the QP matrices to satisfy the

    .. math::

        \\begin{split}\\begin{array}{cc}
        \\mathrm{rank}(A) = p
        &
        \\mathrm{rank}([P\\ A^T\\ G^T]) = n
        \\end{array}\\end{split}

    where :math:`p` is the number of rows of :math:`A` and :math:`n` is the
    number of optimization variables. This is the same requirement as
    :func:`cvxopt_solve_qp`, however qpSWIFT does not perform rank checks as it
    prioritizes performance. If the solver fails on your problem, try running
    CVXOPT on it for rank checks.

    Notes
    -----
    All other keyword arguments are forwarded as options to the qpSWIFT solver.
    For instance, you can call ``qpswift_solve_qp(P, q, G, h, ABSTOL=1e-5)``.
    See the solver documentation for details.

    For a quick overview, the solver accepts the following settings:

    .. list-table::
       :widths: 30 70
       :header-rows: 1

       * - Name
         - Effect
       * - MAXITER
         - Maximum number of iterations needed.
       * - ABSTOL
         - Absolute tolerance on the duality gap. See *e.g.* [tolerances]_ for
           a primer on the duality gap and solver tolerances.
       * - RELTOL
         - Relative tolerance on the residuals :math:`r_x = P x + G^T z + q`
           (dual residual), :math:`r_y = A x - b` (primal residual on equality
           constraints) and :math:`r_z = h - G x - s` (primal residual on
           inequality constraints). See equation (21) in [Pandala2019]_.
       * - SIGMA
         - Maximum centering allowed.

    If a verbose output shows that the maximum number of iterations is reached,
    check e.g. (1) the rank of your equality constraint matrix and (2) that
    your inequality constraint matrix does not have zero rows.

    As qpSWIFT does not sanity check its inputs, it should be used with a
    little more care than the other solvers. For instance, make sure you don't
    have zero rows in your input matrices, as it can `make the solver
    numerically unstable <https://github.com/qpSWIFT/qpSWIFT/issues/3>`_.
    """
    if problem.has_sparse:
        raise ProblemError(
            "problem has sparse matrices "
            "but qpSWIFT only works with dense ones"
        )
    if initvals is not None:
        print("qpSWIFT: warm-start values are ignored by wrapper")
    P, q, G, h, A, b, lb, ub = problem.unpack()
    if lb is not None or ub is not None:
        G, h = linear_from_box_inequalities(G, h, lb, ub, use_sparse=False)
    result: dict = {}
    kwargs.update(
        {
            "OUTPUT": 2,  # include "sol", "basicInfo" and "advInfo"
            "VERBOSE": 1 if verbose else 0,
        }
    )

    try:
        if G is not None and h is not None:
            if A is not None and b is not None:
                result = qpSWIFT.run(q, h, P, G, A, b, kwargs)
            else:  # no equality constraint
                result = qpSWIFT.run(q, h, P, G, opts=kwargs)
        else:  # no inequality constraint
            # See https://github.com/qpSWIFT/qpSWIFT/issues/2
            raise ProblemError("problem has no inequality constraint")
    except TypeError as error:
        if problem.has_sparse:
            raise ProblemError("problem has sparse matrices") from error
        raise ProblemError(str(error)) from error

    basic_info = result["basicInfo"]
    adv_info = result["advInfo"]

    solution = Solution(problem)
    solution.extras["basicInfo"] = basic_info
    solution.extras["advInfo"] = adv_info
    solution.obj = adv_info["fval"]
    exit_flag = basic_info["ExitFlag"]
    if exit_flag != 0:
        return solution
    solution.x = result["sol"]
    if A is not None:
        solution.y = adv_info["y"]
    z, z_box = split_dual_linear_box(adv_info["z"], lb, ub)
    solution.z = z
    solution.z_box = z_box
    return solution


def qpswift_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 `qpSWIFT <https://github.com/qpSWIFT/qpSWIFT>`__.

    Note
    ----
    This solver does not handle problems without inequality constraints yet.

    Parameters
    ----------
    P :
        Symmetric cost matrix. Together with :math:`A` and :math:`G`, it should
        satisfy :math:`\\mathrm{rank}([P\\ A^T\\ G^T]) = n`, see the rank
        assumptions below.
    q :
        Cost vector.
    G :
        Linear inequality constraint matrix. Together with :math:`P` and
        :math:`A`, it should satisfy :math:`\\mathrm{rank}([P\\ A^T\\ G^T]) =
        n`, see the rank assumptions below.
    h :
        Linear inequality constraint vector.
    A :
        Linear equality constraint matrix. It needs to be full row rank, and
        together with :math:`P` and :math:`G` satisfy
        :math:`\\mathrm{rank}([P\\ A^T\\ G^T]) = n`. See the rank assumptions
        below.
    b :
        Linear equality constraint vector.
    lb :
        Lower bound constraint vector.
    ub :
        Upper bound constraint vector.
    initvals :
        Warm-start guess vector.
    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 or the problem has no inequality constraint.

    Note
    ----
    .. _qpSWIFT rank assumptions:

    **Rank assumptions:** qpSWIFT requires the QP matrices to satisfy the

    .. math::

        \\begin{split}\\begin{array}{cc}
        \\mathrm{rank}(A) = p
        &
        \\mathrm{rank}([P\\ A^T\\ G^T]) = n
        \\end{array}\\end{split}

    where :math:`p` is the number of rows of :math:`A` and :math:`n` is the
    number of optimization variables. This is the same requirement as
    :func:`cvxopt_solve_qp`, however qpSWIFT does not perform rank checks as it
    prioritizes performance. If the solver fails on your problem, try running
    CVXOPT on it for rank checks.

    Notes
    -----
    All other keyword arguments are forwarded as options to the qpSWIFT solver.
    For instance, you can call ``qpswift_solve_qp(P, q, G, h, ABSTOL=1e-5)``.
    See the solver documentation for details.

    For a quick overview, the solver accepts the following settings:

    .. list-table::
       :widths: 30 70
       :header-rows: 1

       * - Name
         - Effect
       * - MAXITER
         - Maximum number of iterations needed.
       * - ABSTOL
         - Absolute tolerance on the duality gap. See *e.g.* [tolerances]_ for
           a primer on the duality gap and solver tolerances.
       * - RELTOL
         - Relative tolerance on the residuals :math:`r_x = P x + G^T z + q`
           (dual residual), :math:`r_y = A x - b` (primal residual on equality
           constraints) and :math:`r_z = h - G x - s` (primal residual on
           inequality constraints). See equation (21) in [Pandala2019]_.
       * - SIGMA
         - Maximum centering allowed.

    If a verbose output shows that the maximum number of iterations is reached,
    check e.g. (1) the rank of your equality constraint matrix and (2) that
    your inequality constraint matrix does not have zero rows.

    As qpSWIFT does not sanity check its inputs, it should be used with a
    little more care than the other solvers. For instance, make sure you don't
    have zero rows in your input matrices, as it can `make the solver
    numerically unstable <https://github.com/qpSWIFT/qpSWIFT/issues/3>`_.
    """
    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 = qpswift_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 `qpSWIFT <https://github.com/qpSWIFT/qpSWIFT>`__.
23
24	qpSWIFT is a light-weight sparse Quadratic Programming solver targeted for
25	embedded and robotic applications. It employs Primal-Dual Interior Point method
26	with Mehrotra Predictor corrector step and Nesterov Todd scaling. For solving
27	the linear system of equations, sparse LDL' factorization is used along with
28	approximate minimum degree heuristic to minimize fill-in of the factorizations.
29	If you use qpSWIFT in your research, consider citing the corresponding paper
30	[Pandala2019]_.
31	"""
32
33	import warnings	1✔
34	from typing import Optional	1✔
35
36	import numpy as np	1✔
37	import qpSWIFT	1✔
38
39	from ..conversions import linear_from_box_inequalities, split_dual_linear_box	×
40	from ..exceptions import ProblemError	×
41	from ..problem import Problem	×
42	from ..solution import Solution	×
43
44
45	def qpswift_solve_problem(	×
46	problem: Problem,
47	initvals: Optional[np.ndarray] = None,
48	verbose: bool = False,
49	**kwargs,
50	) -> Solution:
51	"""
52	Solve a quadratic program using `qpSWIFT
53	<https://github.com/qpSWIFT/qpSWIFT>`__.
54
55	Note
56	----
57	This solver does not handle problems without inequality constraints.
58
59	Parameters
60	----------
61	problem :
62	Quadratic program to solve.
63	initvals :
64	Warm-start guess vector.
65	verbose :
66	Set to `True` to print out extra information.
67
68	Returns
69	-------
70	:
71	Solution returned by the solver.
72
73	Raises
74	------
75	ProblemError :
76	If the problem is ill-formed in some way, for instance if some matrices
77	are not dense or the problem has no inequality constraint.
78
79	Note
80	----
81	Rank assumptions: qpSWIFT requires the QP matrices to satisfy the
82
83	.. math::
84
85	\\begin{split}\\begin{array}{cc}
86	\\mathrm{rank}(A) = p
87	&
88	\\mathrm{rank}([P\\ A^T\\ G^T]) = n
89	\\end{array}\\end{split}
90
91	where :math:`p` is the number of rows of :math:`A` and :math:`n` is the
92	number of optimization variables. This is the same requirement as
93	:func:`cvxopt_solve_qp`, however qpSWIFT does not perform rank checks as it
94	prioritizes performance. If the solver fails on your problem, try running
95	CVXOPT on it for rank checks.
96
97	Notes
98	-----
99	All other keyword arguments are forwarded as options to the qpSWIFT solver.
100	For instance, you can call ``qpswift_solve_qp(P, q, G, h, ABSTOL=1e-5)``.
101	See the solver documentation for details.
102
103	For a quick overview, the solver accepts the following settings:
104
105	.. list-table::
106	:widths: 30 70
107	:header-rows: 1
108
109	* - Name
110	- Effect
111	* - MAXITER
112	- Maximum number of iterations needed.
113	* - ABSTOL
114	- Absolute tolerance on the duality gap. See e.g. [tolerances]_ for
115	a primer on the duality gap and solver tolerances.
116	* - RELTOL
117	- Relative tolerance on the residuals :math:`r_x = P x + G^T z + q`
118	(dual residual), :math:`r_y = A x - b` (primal residual on equality
119	constraints) and :math:`r_z = h - G x - s` (primal residual on
120	inequality constraints). See equation (21) in [Pandala2019]_.
121	* - SIGMA
122	- Maximum centering allowed.
123
124	If a verbose output shows that the maximum number of iterations is reached,
125	check e.g. (1) the rank of your equality constraint matrix and (2) that
126	your inequality constraint matrix does not have zero rows.
127
128	As qpSWIFT does not sanity check its inputs, it should be used with a
129	little more care than the other solvers. For instance, make sure you don't
130	have zero rows in your input matrices, as it can `make the solver
131	numerically unstable <https://github.com/qpSWIFT/qpSWIFT/issues/3>`_.
132	"""
133	if problem.has_sparse:	×
134	raise ProblemError(	×
135	"problem has sparse matrices "
136	"but qpSWIFT only works with dense ones"
137	)
138	if initvals is not None:	×
139	print("qpSWIFT: warm-start values are ignored by wrapper")	×
140	P, q, G, h, A, b, lb, ub = problem.unpack()	×
141	if lb is not None or ub is not None:	×
142	G, h = linear_from_box_inequalities(G, h, lb, ub, use_sparse=False)	×
143	result: dict = {}	×
144	kwargs.update(	×
145	{
146	"OUTPUT": 2, # include "sol", "basicInfo" and "advInfo"
147	"VERBOSE": 1 if verbose else 0,
148	}
149	)
150
151	try:	×
152	if G is not None and h is not None:	×
153	if A is not None and b is not None:	×
154	result = qpSWIFT.run(q, h, P, G, A, b, kwargs)	×
155	else: # no equality constraint
156	result = qpSWIFT.run(q, h, P, G, opts=kwargs)	×
157	else: # no inequality constraint
158	# See https://github.com/qpSWIFT/qpSWIFT/issues/2
159	raise ProblemError("problem has no inequality constraint")	×
160	except TypeError as error:	×
161	if problem.has_sparse:	×
162	raise ProblemError("problem has sparse matrices") from error	×
163	raise ProblemError(str(error)) from error	×
164
165	basic_info = result["basicInfo"]	×
166	adv_info = result["advInfo"]	×
167
168	solution = Solution(problem)	×
169	solution.extras["basicInfo"] = basic_info	×
170	solution.extras["advInfo"] = adv_info	×
171	solution.obj = adv_info["fval"]	×
172	exit_flag = basic_info["ExitFlag"]	×
173	if exit_flag != 0:	×
174	return solution	×
175	solution.x = result["sol"]	×
176	if A is not None:	×
177	solution.y = adv_info["y"]	×
178	z, z_box = split_dual_linear_box(adv_info["z"], lb, ub)	×
179	solution.z = z	×
180	solution.z_box = z_box	×
181	return solution	×
182
183
184	def qpswift_solve_qp(	×
185	P: np.ndarray,
186	q: np.ndarray,
187	G: Optional[np.ndarray] = None,
188	h: Optional[np.ndarray] = None,
189	A: Optional[np.ndarray] = None,
190	b: Optional[np.ndarray] = None,
191	lb: Optional[np.ndarray] = None,
192	ub: Optional[np.ndarray] = None,
193	initvals: Optional[np.ndarray] = None,
194	verbose: bool = False,
195	**kwargs,
196	) -> Optional[np.ndarray]:
197	"""
198	Solve a Quadratic Program defined as:
199
200	.. math::
201
202	\\begin{split}\\begin{array}{ll}
203	\\underset{x}{\\mbox{minimize}} &
204	\\frac{1}{2} x^T P x + q^T x \\\\
205	\\mbox{subject to}
206	& G x \\leq h \\\\
207	& A x = b \\\\
208	& lb \\leq x \\leq ub
209	\\end{array}\\end{split}
210
211	using `qpSWIFT <https://github.com/qpSWIFT/qpSWIFT>`__.
212
213	Note
214	----
215	This solver does not handle problems without inequality constraints yet.
216
217	Parameters
218	----------
219	P :
220	Symmetric cost matrix. Together with :math:`A` and :math:`G`, it should
221	satisfy :math:`\\mathrm{rank}([P\\ A^T\\ G^T]) = n`, see the rank
222	assumptions below.
223	q :
224	Cost vector.
225	G :
226	Linear inequality constraint matrix. Together with :math:`P` and
227	:math:`A`, it should satisfy :math:`\\mathrm{rank}([P\\ A^T\\ G^T]) =
228	n`, see the rank assumptions below.
229	h :
230	Linear inequality constraint vector.
231	A :
232	Linear equality constraint matrix. It needs to be full row rank, and
233	together with :math:`P` and :math:`G` satisfy
234	:math:`\\mathrm{rank}([P\\ A^T\\ G^T]) = n`. See the rank assumptions
235	below.
236	b :
237	Linear equality constraint vector.
238	lb :
239	Lower bound constraint vector.
240	ub :
241	Upper bound constraint vector.
242	initvals :
243	Warm-start guess vector.
244	verbose :
245	Set to `True` to print out extra information.
246
247	Returns
248	-------
249	:
250	Solution to the QP, if found, otherwise ``None``.
251
252	Raises
253	------
254	ProblemError :
255	If the problem is ill-formed in some way, for instance if some matrices
256	are not dense or the problem has no inequality constraint.
257
258	Note
259	----
260	.. _qpSWIFT rank assumptions:
261
262	Rank assumptions: qpSWIFT requires the QP matrices to satisfy the
263
264	.. math::
265
266	\\begin{split}\\begin{array}{cc}
267	\\mathrm{rank}(A) = p
268	&
269	\\mathrm{rank}([P\\ A^T\\ G^T]) = n
270	\\end{array}\\end{split}
271
272	where :math:`p` is the number of rows of :math:`A` and :math:`n` is the
273	number of optimization variables. This is the same requirement as
274	:func:`cvxopt_solve_qp`, however qpSWIFT does not perform rank checks as it
275	prioritizes performance. If the solver fails on your problem, try running
276	CVXOPT on it for rank checks.
277
278	Notes
279	-----
280	All other keyword arguments are forwarded as options to the qpSWIFT solver.
281	For instance, you can call ``qpswift_solve_qp(P, q, G, h, ABSTOL=1e-5)``.
282	See the solver documentation for details.
283
284	For a quick overview, the solver accepts the following settings:
285
286	.. list-table::
287	:widths: 30 70
288	:header-rows: 1
289
290	* - Name
291	- Effect
292	* - MAXITER
293	- Maximum number of iterations needed.
294	* - ABSTOL
295	- Absolute tolerance on the duality gap. See e.g. [tolerances]_ for
296	a primer on the duality gap and solver tolerances.
297	* - RELTOL
298	- Relative tolerance on the residuals :math:`r_x = P x + G^T z + q`
299	(dual residual), :math:`r_y = A x - b` (primal residual on equality
300	constraints) and :math:`r_z = h - G x - s` (primal residual on
301	inequality constraints). See equation (21) in [Pandala2019]_.
302	* - SIGMA
303	- Maximum centering allowed.
304
305	If a verbose output shows that the maximum number of iterations is reached,
306	check e.g. (1) the rank of your equality constraint matrix and (2) that
307	your inequality constraint matrix does not have zero rows.
308
309	As qpSWIFT does not sanity check its inputs, it should be used with a
310	little more care than the other solvers. For instance, make sure you don't
311	have zero rows in your input matrices, as it can `make the solver
312	numerically unstable <https://github.com/qpSWIFT/qpSWIFT/issues/3>`_.
313	"""
314	warnings.warn(	×
315	"The return type of this function will change "
316	"to qpsolvers.Solution in qpsolvers v3.0",
317	DeprecationWarning,
318	stacklevel=2,
319	)
320	problem = Problem(P, q, G, h, A, b, lb, ub)	×
321	solution = qpswift_solve_problem(problem, initvals, verbose, **kwargs)	×
322	return solution.x	×

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