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.