Developer notes#

Adding a new solver#

Let’s imagine we want to add a new solver called AwesomeQP. The solver keyword, the string passed via the solver keyword argument, is the lowercase version of the vernacular name of a QP solver. For our imaginary solver, the keyword is therefore "awesomeqp".

The process to add AwesomeQP to qpsolvers goes as follows:

  1. Create a new file qpsolvers/solvers/awesomeqp_.py (named after the solver keyword, with a trailing underscore)

  2. Implement in this file a function awesomeqp_solve_problem that returns a Solution

  3. Implement in the same file a function awesomeqp_solve_qp to connect it to the historical API, typically as follows:

def awesomeqp_solve_qp(P, q, G, h, A, b, lb, ub, initvals=None, verbose=False, **kwargs):
) -> Optional[np.ndarray]:
    r"""Solve a quadratic program using AwesomeQP.

    [document parameters and return values here]
    """
    problem = Problem(P, q, G, h, A, b, lb, ub)
    solution = awesomeqp_solve_problem(
        problem, initvals, verbose, backend, **kwargs
    )
    return solution.x if solution.found else None

  1. Define the two function prototypes for awesomeqp_solve_problem and awesomeqp_solve_qp in qpsolvers/solvers/__init__.py:

# AwesomeQP
# ========

awesome_solve_qp: Optional[
    Callable[
        [
            ndarray,
            ndarray,
            Optional[ndarray],
            Optional[ndarray],
            Optional[ndarray],
            Optional[ndarray],
            Optional[ndarray],
            Optional[str],
            bool,
        ],
        Optional[ndarray],
    ]
] = None

Note

The prototype needs to match the actual function. You can check its correctness by running tox -e py in the repository.

  1. Below the prototype, import the function into the solve_function dictionary:

try:
    from .awesomeqp_ import awesomeqp_solve_qp

    solve_function["awesomeqp"] = awesomeqp_solve_qp
    available_solvers.append("awesomeqp")
    # dense_solvers.append("awesomeqp")   if applicable
    # sparse_solvers.append("awesomeqp")  if applicable
except ImportError:
    pass

  1. Append the solver identifier to dense_solvers or sparse_solvers, if applicable

  2. Import awesomeqp_solve_qp from qpsolvers/__init__.py and add it to __all__

  3. Add the solver to doc/src/supported-solvers.rst

  4. Add the solver to the Solvers section of the README

  5. Assuming AwesomeQP is distributed on PyPI, add it to the [testenv] and [testenv:coverage] environments of tox.ini for unit testing

  6. Assuming AwesomeQP is distributed on Conda or PyPI, add it to the list of dependencies in doc/environment.yml

  7. Log the new solver as an addition in the changelog

  8. If you are a new contributor, feel free to add your name to CITATION.cff.

Problem conversions#

Convert problems from and to standard QP form.

qpsolvers.conversions.combine_linear_box_inequalities(G, h, lb, ub, n, use_csc)#

Combine linear and box inequalities into double-sided linear format.

Input format:

\[\begin{split}\begin{split}\begin{array}{ll} G x & \leq h \\ lb & \leq x \leq ub \end{array}\end{split}\end{split}\]

Output format:

\[l \leq C \leq u\]
Parameters:

  • G – Linear inequality constraint matrix. Must be two-dimensional.

  • h – Linear inequality constraint vector.

  • lb – Lower bound constraint vector.

  • ub – Upper bound constraint vector.

  • n (int) – Number of optimization variables.

  • use_csc (bool) – If True, use sparse rather than dense matrices.

Returns:

Linear inequality matrix \(C\) and vectors \(u\), \(l\). The two vector will contain \(\pm\infty\) values on coordinates where there is no corresponding constraint.

Raises:

ProblemError – If the inequality matrix and vector are not consistent.

qpsolvers.conversions.ensure_sparse_matrices(P, G, A)#

Make sure problem matrices are sparse.

Parameters:

  • P (Union[ndarray, csc_matrix]) – Cost matrix.

  • G (Union[ndarray, csc_matrix, None]) – Inequality constraint matrix, if any.

  • A (Union[ndarray, csc_matrix, None]) – Equality constraint matrix, if any.

Return type:

Tuple[csc_matrix, Optional[csc_matrix], Optional[csc_matrix]]

Returns:

Tuple of all three matrices as sparse matrices.

qpsolvers.conversions.linear_from_box_inequalities(G, h, lb, ub, use_sparse)#

Append lower or upper bound vectors to inequality constraints.

Parameters:

  • G (Union[ndarray, csc_matrix, None]) – Linear inequality matrix.

  • h (Optional[ndarray]) – Linear inequality vector.

  • lb (Optional[ndarray]) – Lower bound constraint vector.

  • ub (Optional[ndarray]) – Upper bound constraint vector.

  • use_sparse (bool) – Use sparse matrices if true, dense matrices otherwise.

Return type:

Tuple[Union[ndarray, csc_matrix, None], Optional[ndarray]]

Returns:

  • G (np.ndarray, spa.csc_matrix or None) – Updated linear inequality matrix.

  • h (np.ndarray or None) – Updated linear inequality vector.

qpsolvers.conversions.socp_from_qp(P, q, G, h)#

Convert a quadratic program to a second-order cone program.

The quadratic program is defined by:

\[\begin{split}\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 \end{array}\end{split}\end{split}\]

The equivalent second-order cone program is:

\[\begin{split}\begin{split}\begin{array}{ll} \underset{x}{\mbox{minimize}} & c^T_s y \\ \mbox{subject to} & G_s y \leq_{\cal K} h_s \end{array}\end{split}\end{split}\]

This function is adapted from ecosqp.m in the ecos-matlab repository. See the documentation in that script for details on this reformulation.

Parameters:

  • P (ndarray) – Primal quadratic cost matrix.

  • q (ndarray) – Primal quadratic cost vector.

  • G (Optional[ndarray]) – Linear inequality constraint matrix.

  • h (Optional[ndarray]) – Linear inequality constraint vector.

Return type:

Tuple[ndarray, ndarray, ndarray, Dict[str, Any]]

Returns:

  • c_socp (array) – SOCP cost vector.

  • G_socp (array) – SOCP inequality matrix.

  • h_socp (array) – SOCP inequality vector.

  • dims (dict) – Dimension dictionary used by SOCP solvers, where dims["l"] is the number of inequality constraints.

Raises:

ValueError : – If the cost matrix is not positive definite.

qpsolvers.conversions.split_dual_linear_box(z_stacked, lb, ub)#

Separate linear and box multipliers from a stacked dual vector.

This function assumes linear and box inequalities were combined using qpsolvers.conversions.linear_from_box_inequalities().

Parameters:

  • z_stacked (ndarray) – Stacked vector of dual multipliers.

  • lb (Optional[ndarray]) – Lower bound constraint vector.

  • ub (Optional[ndarray]) – Upper bound constraint vector.

Return type:

Tuple[Optional[ndarray], Optional[ndarray]]

Returns:

Pair z, z_box of linear and box multipliers. Both can be empty arrays if there is no corresponding constraint.

Testing locally#

To run all CI checks locally, go to the repository folder and run

tox -e py

This will run linters and unit tests.