Skip to main content Link Menu Expand (external link) Document Search Copy Copied

Problem Formulation

PIQP expects QP of the form

\[\begin{aligned} \min_{x} \quad & \frac{1}{2} x^\top P x + c^\top x \\ \text {s.t.}\quad & Ax=b, \\ & Gx \leq h, \\ & x_{lb} \leq x \leq x_{ub} \end{aligned}\]

with primal decision variables \(x \in \mathbb{R}^n\), matrices \(P\in \mathbb{S}_+^n\), \(A \in \mathbb{R}^{p \times n}\), \(G \in \mathbb{R}^{m \times n}\), and vectors \(c \in \mathbb{R}^n\), \(b \in \mathbb{R}^p\), \(h \in \mathbb{R}^m\), \(x_{lb} \in \mathbb{R}^n\), and \(x_{ub} \in \mathbb{R}^n\).

PIQP can handle infinite box constraints well, i.e. when elements of \(x_{lb}\) or \(x_{ub}\) are \(-\infty\) or \(\infty\), respectively. On the contrary, infinite values in the general inequalities \(Gx \leq h = \pm \infty\) can cause problems. PIQP internally disables them by setting the corresponding rows in \(G\) to zero (sparsity structure is preserved). For best performance, consider removing the corresponding constraints from the problem formulation directly.

Example QP

In the following the C++ interface of PIQP will be introduced using the following example QP problem:

\[\begin{aligned} \min_{x} \quad & \frac{1}{2} x^\top \begin{bmatrix} 6 & 0 \\ 0 & 4 \end{bmatrix} x + \begin{bmatrix} -1 \\ -4 \end{bmatrix}^\top x \\ \text {s.t.}\quad & \begin{bmatrix} 1 & -2 \end{bmatrix} x = 1, \\ & \begin{bmatrix} 1 & -1 \\ 2 & 0 \end{bmatrix} x \leq \begin{bmatrix} 0.2 \\ -1 \end{bmatrix}, \\ & -1 \leq x_1 \leq 1. \end{aligned}\]

Problem Data

PIQP supports dense and sparse problem formulations. For small and dense problems the dense interface is preferred since vectorized instructions and cache locality can be exploited more efficiently, but for sparse problems the sparse interface and result in significant speedups.

To use the Python interface of PIQP import the following packages:

import piqp
import numpy as np
from scipy import sparse

scipy is only needed if the sparse interface is used.

We can then define the problem data as

P = np.array([[6, 0], [0, 4]], dtype=np.float64)
c = np.array([-1, -4], dtype=np.float64)
A = np.array([[1, -2]], dtype=np.float64)
b = np.array([1], dtype=np.float64)
G = np.array([[1, -1], [2, 0]], dtype=np.float64)
h = np.array([0.2, -1], dtype=np.float64)
x_lb = np.array([-1, -np.inf], dtype=np.float64)
x_ub = np.array([1, np.inf], dtype=np.float64)

For the sparse interface \(P\), \(A\), and \(G\) have to be in compressed sparse column (CSC) format.

P = sparse.csc_matrix([[6, 0], [0, 4]], dtype=np.float64)
A = sparse.csc_matrix([[1, -2]], dtype=np.float64)
G = sparse.csc_matrix([[1, -1], [2, 0]], dtype=np.float64)

Solver Instantiation

You can instantiate a solver object using

// for dense problems
solver = piqp.DenseSolver()
// or for sparse problems
solver = piqp.SparseSolver()

Settings

Settings can be directly set on the solver object:

solver.settings.verbose = True
solver.settings.compute_timings = True

In this example we enable the verbose output and internal timings. The full set of configuration options can be found here.

Solving the Problem

We can now set up the problem using

solver.setup(P, c, A, b, G, h, x_lb, x_ub)

Every variable except P and c are optional and None may be passed.

The data is internally copied, and the solver initializes all internal data structures.

Now, the problem can be solver using

status = solver.solve()

Status code

Status Code Value Description
PIQP_SOLVED 1 Solver solved problem up to given tolerance.
PIQP_MAX_ITER_REACHED -1 Iteration limit was reached.
PIQP_PRIMAL_INFEASIBLE -2 The problem is primal infeasible.
PIQP_DUAL_INFEASIBLE -3 The problem is dual infeasible.
PIQP_NUMERICS -8 Numerical error occurred during solving.
PIQP_UNSOLVED -9 The problem is unsolved, i.e., solve was never called.
PIQP_INVALID_SETTINGS -10 Invalid settings were provided to the solver.

Extracting the Result

The result of the optimization can be obtained from the solver.result object. More specifically, the most important information includes

  • solver.result.x: primal solution
  • solver.result.y: dual solution of equality constraints
  • solver.result.z: dual solution of inequality constraints
  • solver.result.z_lb: dual solution of lower bound box constraints
  • solver.result.z_ub: dual solution of upper bound box constraints
  • solver.result.info.primal_obj: primal objective value
  • solver.result.info.run_time: total runtime

Timing information like solver.result.info.run_time is only measured if solver.settings.compute_timings is set to true.

Efficient Problem Updates

Instead of creating a new solver object everytime it’s possible to update the problem directly using

solver.update(P, c, A, b, G, h, x_lb, x_ub)

with a subsequent call to

status = solver.solve()

This allows the solver to internally reuse memory and factorizations speeding up subsequent solves. Similar to the setup function, all parameters are optional and None may be passed instead.

Note the dimension and sparsity pattern of the problem are not allowed to change when calling the update function.