3766519599

Build # 3766519599

Build Type

github

Committed by GitHub

Commit Message

Merge b7a5eac77 into 3da662916

Pull Request Pull Request #139: Only throw qpsolvers-owned exceptions

Run Details

49 of 49 new or added lines in 14 files covered. (100.0%)

1701 of 1909 relevant lines covered (89.1%)

0.89 hits per line

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

98.39

/qpsolvers/solvers/cvxopt_.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 `CVXOPT <https://cvxopt.org/>`__.

CVXOPT is a free software package for convex optimization in Python. Its main
purpose is to make the development of software for convex optimization
applications straightforward by building on Python’s extensive standard library
and on the strengths of Python as a high-level programming language. If you are
using CVXOPT in some academic work, consider citing the corresponding report
[Vandenberghe2010]_.
"""

import warnings
from typing import Dict, Optional, Union

import cvxopt
import numpy as np
import scipy.sparse as spa
from cvxopt.solvers import qp

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

cvxopt.solvers.options["show_progress"] = False  # disable verbose output


def __to_cvxopt(
    M: Union[np.ndarray, spa.csc_matrix]
) -> Union[cvxopt.matrix, cvxopt.spmatrix]:
    """
    Convert matrix to CVXOPT format.

    Parameters
    ----------
    M :
        Matrix in NumPy or CVXOPT format.

    Returns
    -------
    :
        Matrix in CVXOPT format.
    """
    if isinstance(M, np.ndarray):
        return cvxopt.matrix(M)
    coo = M.tocoo()
    return cvxopt.spmatrix(
        coo.data.tolist(), coo.row.tolist(), coo.col.tolist(), size=M.shape
    )


def cvxopt_solve_problem(
    problem: Problem,
    solver: Optional[str] = None,
    initvals: Optional[np.ndarray] = None,
    verbose: bool = False,
    **kwargs,
) -> Solution:
    """
    Solve a quadratic program using `CVXOPT <http://cvxopt.org/>`_.

    Parameters
    ----------
    problem :
        Quadratic program to solve.
    solver :
        Set to 'mosek' to run MOSEK rather than CVXOPT.
    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 CVXOPT rank assumption is not satisfied.

    SolverError
        If CVXOPT failed with an error.

    Note
    ----
    .. _CVXOPT rank assumptions:

    **Rank assumptions:** CVXOPT 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. See the "Rank assumptions" paragraph in
    the report `The CVXOPT linear and quadratic cone program solvers
    <http://www.ee.ucla.edu/~vandenbe/publications/coneprog.pdf>`_ for details.

    Notes
    -----
    CVXOPT only considers the lower entries of `P`, therefore it will use a
    different cost than the one intended if a non-symmetric matrix is provided.

    Keyword arguments are forwarded as options to CVXOPT. For instance, we can
    call ``cvxopt_solve_qp(P, q, G, h, u, abstol=1e-4, reltol=1e-4)``. CVXOPT
    options include the following:

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

       * - Name
         - Description
       * - ``abstol``
         - Absolute tolerance on the duality gap.
       * - ``reltol``
         - Relative tolerance on the duality gap.
       * - ``feastol``
         - Tolerance on feasibility conditions, that is, on the primal
           residual.
       * - ``refinement``
         - Number of iterative refinement steps when solving KKT equations

    Check out `Algorithm Parameters
    <https://cvxopt.org/userguide/coneprog.html#algorithm-parameters>`_ section
    of the solver documentation for details and default values of all solver
    parameters. See also [tolerances]_ for a primer on the duality gap, primal
    and dual residuals.
    """
    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)

    args = [__to_cvxopt(P), __to_cvxopt(q)]
    constraints = {"G": None, "h": None, "A": None, "b": None}
    if G is not None and h is not None:
        constraints["G"] = __to_cvxopt(G)
        constraints["h"] = __to_cvxopt(h)
    if A is not None and b is not None:
        constraints["A"] = __to_cvxopt(A)
        constraints["b"] = __to_cvxopt(b)
    initvals_dict: Optional[Dict[str, cvxopt.matrix]] = None
    if initvals is not None:
        initvals_dict = {"x": __to_cvxopt(initvals)}

    kwargs["show_progress"] = verbose
    original_options = cvxopt.solvers.options
    cvxopt.solvers.options = kwargs
    try:
        res = qp(*args, solver=solver, initvals=initvals_dict, **constraints)
    except ValueError as exception:
        error = str(exception)
        if "Rank(A)" in error:
            raise ProblemError(error) from exception
        raise SolverError(error) from exception
    cvxopt.solvers.options = original_options

    solution = Solution(problem)
    if "optimal" not in res["status"]:
        return solution
    solution.x = np.array(res["x"]).reshape((q.shape[0],))
    if b is not None:
        solution.y = np.array(res["y"]).reshape((b.shape[0],))
    if h is not None:
        z_cvx = np.array(res["z"]).reshape((h.shape[0],))
        z, z_box = split_dual_linear_box(z_cvx, lb, ub)
        solution.z = z
        solution.z_box = z_box
    solution.obj = res["primal objective"]
    solution.extras = res
    return solution


def cvxopt_solve_qp(
    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,
    solver: Optional[str] = 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 `CVXOPT <http://cvxopt.org/>`_.

    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 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 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.
    solver :
        Set to 'mosek' to run MOSEK rather than CVXOPT.
    initvals :
        Warm-start guess vector.
    verbose :
        Set to `True` to print out extra information.

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

    Raises
    ------
    ProblemError
        If the CVXOPT rank assumption is not satisfied.

    SolverError
        If CVXOPT failed with an error.
    """
    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 = cvxopt_solve_problem(
        problem, solver, 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 `CVXOPT <https://cvxopt.org/>`__.
23
24	CVXOPT is a free software package for convex optimization in Python. Its main
25	purpose is to make the development of software for convex optimization
26	applications straightforward by building on Python’s extensive standard library
27	and on the strengths of Python as a high-level programming language. If you are
28	using CVXOPT in some academic work, consider citing the corresponding report
29	[Vandenberghe2010]_.
30	"""
31
32	import warnings	1✔
33	from typing import Dict, Optional, Union	1✔
34
35	import cvxopt	1✔
36	import numpy as np	1✔
37	import scipy.sparse as spa	1✔
38	from cvxopt.solvers import qp	1✔
39
40	from ..conversions import linear_from_box_inequalities, split_dual_linear_box	1✔
41	from ..exceptions import ProblemError, SolverError	1✔
42	from ..problem import Problem	1✔
43	from ..solution import Solution	1✔
44
45	cvxopt.solvers.options["show_progress"] = False # disable verbose output	1✔
46
47
48	def __to_cvxopt(	1✔
49	M: Union[np.ndarray, spa.csc_matrix]
50	) -> Union[cvxopt.matrix, cvxopt.spmatrix]:
51	"""
52	Convert matrix to CVXOPT format.
53
54	Parameters
55	----------
56	M :
57	Matrix in NumPy or CVXOPT format.
58
59	Returns
60	-------
61	:
62	Matrix in CVXOPT format.
63	"""
64	if isinstance(M, np.ndarray):	1✔
65	return cvxopt.matrix(M)	1✔
66	coo = M.tocoo()	1✔
67	return cvxopt.spmatrix(	1✔
68	coo.data.tolist(), coo.row.tolist(), coo.col.tolist(), size=M.shape
69	)
70
71
72	def cvxopt_solve_problem(	1✔
73	problem: Problem,
74	solver: Optional[str] = None,
75	initvals: Optional[np.ndarray] = None,
76	verbose: bool = False,
77	**kwargs,
78	) -> Solution:
79	"""
80	Solve a quadratic program using `CVXOPT <http://cvxopt.org/>`_.
81
82	Parameters
83	----------
84	problem :
85	Quadratic program to solve.
86	solver :
87	Set to 'mosek' to run MOSEK rather than CVXOPT.
88	initvals :
89	Warm-start guess vector.
90	verbose :
91	Set to `True` to print out extra information.
92
93	Returns
94	-------
95	:
96	Solution to the QP, if found, otherwise ``None``.
97
98	Raises
99	------
100	ProblemError
101	If the CVXOPT rank assumption is not satisfied.
102
103	SolverError
104	If CVXOPT failed with an error.
105
106	Note
107	----
108	.. _CVXOPT rank assumptions:
109
110	Rank assumptions: CVXOPT requires the QP matrices to satisfy the
111
112	.. math::
113
114	\\begin{split}\\begin{array}{cc}
115	\\mathrm{rank}(A) = p
116	&
117	\\mathrm{rank}([P\\ A^T\\ G^T]) = n
118	\\end{array}\\end{split}
119
120	where :math:`p` is the number of rows of :math:`A` and :math:`n` is the
121	number of optimization variables. See the "Rank assumptions" paragraph in
122	the report `The CVXOPT linear and quadratic cone program solvers
123	<http://www.ee.ucla.edu/~vandenbe/publications/coneprog.pdf>`_ for details.
124
125	Notes
126	-----
127	CVXOPT only considers the lower entries of `P`, therefore it will use a
128	different cost than the one intended if a non-symmetric matrix is provided.
129
130	Keyword arguments are forwarded as options to CVXOPT. For instance, we can
131	call ``cvxopt_solve_qp(P, q, G, h, u, abstol=1e-4, reltol=1e-4)``. CVXOPT
132	options include the following:
133
134	.. list-table::
135	:widths: 30 70
136	:header-rows: 1
137
138	* - Name
139	- Description
140	* - ``abstol``
141	- Absolute tolerance on the duality gap.
142	* - ``reltol``
143	- Relative tolerance on the duality gap.
144	* - ``feastol``
145	- Tolerance on feasibility conditions, that is, on the primal
146	residual.
147	* - ``refinement``
148	- Number of iterative refinement steps when solving KKT equations
149
150	Check out `Algorithm Parameters
151	<https://cvxopt.org/userguide/coneprog.html#algorithm-parameters>`_ section
152	of the solver documentation for details and default values of all solver
153	parameters. See also [tolerances]_ for a primer on the duality gap, primal
154	and dual residuals.
155	"""
156	P, q, G, h, A, b, lb, ub = problem.unpack()	1✔
157	if lb is not None or ub is not None:	1✔
158	G, h = linear_from_box_inequalities(G, h, lb, ub)	1✔
159
160	args = [__to_cvxopt(P), __to_cvxopt(q)]	1✔
161	constraints = {"G": None, "h": None, "A": None, "b": None}	1✔
162	if G is not None and h is not None:	1✔
163	constraints["G"] = __to_cvxopt(G)	1✔
164	constraints["h"] = __to_cvxopt(h)	1✔
165	if A is not None and b is not None:	1✔
166	constraints["A"] = __to_cvxopt(A)	1✔
167	constraints["b"] = __to_cvxopt(b)	1✔
168	initvals_dict: Optional[Dict[str, cvxopt.matrix]] = None	1✔
169	if initvals is not None:	1✔
170	initvals_dict = {"x": __to_cvxopt(initvals)}	1✔
171
172	kwargs["show_progress"] = verbose	1✔
173	original_options = cvxopt.solvers.options	1✔
174	cvxopt.solvers.options = kwargs	1✔
175	try:	1✔
176	res = qp(args, solver=solver, initvals=initvals_dict, *constraints)	1✔
177	except ValueError as exception:	1✔
178	error = str(exception)	1✔
179	if "Rank(A)" in error:	1✔
180	raise ProblemError(error) from exception	1✔
181	raise SolverError(error) from exception	×
182	cvxopt.solvers.options = original_options	1✔
183
184	solution = Solution(problem)	1✔
185	if "optimal" not in res["status"]:	1✔
186	return solution	1✔
187	solution.x = np.array(res["x"]).reshape((q.shape[0],))	1✔
188	if b is not None:	1✔
189	solution.y = np.array(res["y"]).reshape((b.shape[0],))	1✔
190	if h is not None:	1✔
191	z_cvx = np.array(res["z"]).reshape((h.shape[0],))	1✔
192	z, z_box = split_dual_linear_box(z_cvx, lb, ub)	1✔
193	solution.z = z	1✔
194	solution.z_box = z_box	1✔
195	solution.obj = res["primal objective"]	1✔
196	solution.extras = res	1✔
197	return solution	1✔
198
199
200	def cvxopt_solve_qp(	1✔
201	P: Union[np.ndarray, spa.csc_matrix],
202	q: np.ndarray,
203	G: Optional[Union[np.ndarray, spa.csc_matrix]] = None,
204	h: Optional[np.ndarray] = None,
205	A: Optional[Union[np.ndarray, spa.csc_matrix]] = None,
206	b: Optional[np.ndarray] = None,
207	lb: Optional[np.ndarray] = None,
208	ub: Optional[np.ndarray] = None,
209	solver: Optional[str] = None,
210	initvals: Optional[np.ndarray] = None,
211	verbose: bool = False,
212	**kwargs,
213	) -> Optional[np.ndarray]:
214	"""
215	Solve a Quadratic Program defined as:
216
217	.. math::
218
219	\\begin{split}\\begin{array}{ll}
220	\\underset{x}{\\mbox{minimize}} &
221	\\frac{1}{2} x^T P x + q^T x \\\\
222	\\mbox{subject to}
223	& G x \\leq h \\\\
224	& A x = b \\\\
225	& lb \\leq x \\leq ub
226	\\end{array}\\end{split}
227
228	using `CVXOPT <http://cvxopt.org/>`_.
229
230	Parameters
231	----------
232	P :
233	Symmetric cost matrix. Together with :math:`A` and :math:`G`, it should
234	satisfy :math:`\\mathrm{rank}([P\\ A^T\\ G^T]) = n`, see the rank
235	assumptions below.
236	q :
237	Cost vector.
238	G :
239	Linear inequality matrix. Together with :math:`P` and :math:`A`, it
240	should satisfy :math:`\\mathrm{rank}([P\\ A^T\\ G^T]) = n`, see the
241	rank assumptions below.
242	h :
243	Linear inequality vector.
244	A :
245	Linear equality constraint matrix. It needs to be full row rank, and
246	together with :math:`P` and :math:`G` satisfy
247	:math:`\\mathrm{rank}([P\\ A^T\\ G^T]) = n`. See the rank assumptions
248	below.
249	b :
250	Linear equality constraint vector.
251	lb :
252	Lower bound constraint vector.
253	ub :
254	Upper bound constraint vector.
255	solver :
256	Set to 'mosek' to run MOSEK rather than CVXOPT.
257	initvals :
258	Warm-start guess vector.
259	verbose :
260	Set to `True` to print out extra information.
261
262	Returns
263	-------
264	:
265	Primal solution to the QP, if found, otherwise ``None``.
266
267	Raises
268	------
269	ProblemError
270	If the CVXOPT rank assumption is not satisfied.
271
272	SolverError
273	If CVXOPT failed with an error.
274	"""
275	warnings.warn(	1✔
276	"The return type of this function will change "
277	"to qpsolvers.Solution in qpsolvers v3.0",
278	DeprecationWarning,
279	stacklevel=2,
280	)
281	problem = Problem(P, q, G, h, A, b, lb, ub)	1✔
282	solution = cvxopt_solve_problem(	1✔
283	problem, solver, initvals, verbose, **kwargs
284	)
285	return solution.x	1✔

stephane-caron / qpsolvers / 3766519599

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