QuadProg

class QuadProg

Bases: pybind11_object

This class provides a solver for Quadratic Programs.

The cost function is written under the form \(\min ||\mathbf{Q}\mathbf{x} - \mathbf{r}||^2\) .

If a cost function is written under the canonical form \(\min \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}\) then fromCanonicalCost() can be used to retrieve Q and r from H and c.

Equality constraints are solved through projection into the kernel.

Inequality constraints are solved with active sets.

In order to be used sequentially, the decomposition of the equality constraint may be stored. The last active set is always stored and used to warm start the next call.

Warning

The solvers are only available if c++11 or higher is activated during build. Configure ViSP using cmake -DUSE_CXX_STANDARD=11.

Methods

__init__

fromCanonicalCost

Changes a canonical quadratic cost \(\min \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}\) to the formulation used by this class \(\min ||\mathbf{Q}\mathbf{x} - \mathbf{r}||^2\) .

resetActiveSet

Resets the active set that was found by a previous call to solveQP() or solveQPi() , if any.

setEqualityConstraint

Saves internally the column reduction of the passed equality constraint:

solveQP

Solves a Quadratic Program under equality and inequality constraints.

solveQPe

Solves a Quadratic Program under previously stored equality constraints ( setEqualityConstraint() )

solveQPeStatic

Solves a Quadratic Program under equality constraints.

solveQPi

Solves a Quadratic Program under inequality constraints

Inherited Methods

Operators

__doc__

__init__

__module__

Attributes

__annotations__

__init__(*args, **kwargs)
static fromCanonicalCost(H: visp._visp.core.Matrix, c: visp._visp.core.ColVector, Q: visp._visp.core.Matrix, r: visp._visp.core.ColVector, tol: float = 1e-6) → None

Changes a canonical quadratic cost \(\min \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}\) to the formulation used by this class \(\min ||\mathbf{Q}\mathbf{x} - \mathbf{r}||^2\) .

Computes \((\mathbf{Q}, \mathbf{r})\) such that \(\mathbf{H} = \mathbf{Q}^T\mathbf{Q}\) and \(\mathbf{c} = -\mathbf{Q}^T\mathbf{r}\) .

Warning

This method is only available if the Gnu Scientific Library (GSL) is detected as a third party library.

Here is an example:

\(\begin{array}{lll} \mathbf{x} = & \arg\min & 2x_1^2 + x_2^2 + x_1x_2 + x_1 + x_2\\& \text{s.t.}& x_1 + x_2 = 1 \end{array} \Leftrightarrow \begin{array}{lll} \mathbf{x} = & \arg\min & \frac{1}{2}\mathbf{x}^T\left[\begin{array}{cc}4 & 1 \\1 & 2\end{array}\right]\mathbf{x} + [1~1]\mathbf{x}\\& \text{s.t.}& [1~1]\mathbf{x} = 1 \end{array}\)

#include <visp3/core/vpLinProg.h>

int main()
{
  vpMatrix H(2,2), A(1,2);
  vpColVector c(2), b(1);

  H[0][0] = 4;
  H[0][1] = H[1][0] = 1;
  H[1][1] = 2;
  c[0] = c[1] = 1;
  A[0][0] = A[0][1] = 1;
  b[0] = 1;

  vpMatrix Q;vpColVector r;
  vpQuadProg::fromCanonicalCost(H, c, Q, r);

  vpColVector x;
  vpQuadProg::solveQPe(Q, r, A, b, x);
  std::cout << x.t() << std::endl;  // prints (0.25 0.75)
}
Parameters:
H: visp._visp.core.Matrix

canonical symmetric positive cost matrix (dimension n x n)

c: visp._visp.core.ColVector

canonical cost vector (dimension n)

Q: visp._visp.core.Matrix

custom cost matrix (dimension rank(H) x n)

r: visp._visp.core.ColVector

custom cost vector (dimension rank(H))

tol: float = 1e-6

tolerance to test ranks

resetActiveSet(self) → None

Resets the active set that was found by a previous call to solveQP() or solveQPi() , if any.

setEqualityConstraint(self, A: visp._visp.core.Matrix, b: visp._visp.core.ColVector, tol: float = 1e-6) → bool

Saves internally the column reduction of the passed equality constraint:

Note

See solveQPi() , solveQP()

Parameters:
A: visp._visp.core.Matrix

equality matrix (dimension m x n)

b: visp._visp.core.ColVector

equality vector (dimension m)

tol: float = 1e-6

tolerance to test the ranks

Returns:

True if \(\mathbf{A}\mathbf{x} = \mathbf{b}\) has a solution.

solveQP(self, Q: visp._visp.core.Matrix, r: visp._visp.core.ColVector, A: visp._visp.core.Matrix, b: visp._visp.core.ColVector, C: visp._visp.core.Matrix, d: visp._visp.core.ColVector, x: visp._visp.core.ColVector, tol: float = 1e-6) → bool

Solves a Quadratic Program under equality and inequality constraints.

If the equality constraints \((\mathbf{A}, \mathbf{b})\) are the same between two calls, it is more efficient to use setEqualityConstraint() and solveQPi() .

Here is an example:

\(\begin{array}{lll} \mathbf{x} = & \arg\min & (x_1-1)^2 + x_2^2 \\& \text{s.t.}& x_1 + x_2 = 1 \\& \text{s.t.} & x_2 \geq 1\end{array}\)

#include <visp3/core/vpLinProg.h>

int main()
{
  vpMatrix Q(2,2), A(1,2), C(1,2);
  vpColVector r(2), b(1), d(1);

  Q[0][0] = Q[1][1] = 1;    r[0] = 1;
  A[0][0] = A[0][1] = 1;    b[0] = 1;
  C[0][1] = -1; d[0] = -1;

  vpColVector x;
  vpQuadProg qp;

  qp.solveQP(Q, r, A, b, C, d, x);
  std::cout << x.t() << std::endl;  // prints (0 1)
}

Note

See resetActiveSet()

Parameters:
Q: visp._visp.core.Matrix

cost matrix (dimension c x n)

r: visp._visp.core.ColVector

cost vector (dimension c)

A: visp._visp.core.Matrix

equality matrix (dimension m x n)

b: visp._visp.core.ColVector

equality vector (dimension m)

C: visp._visp.core.Matrix

inequality matrix (dimension p x n)

d: visp._visp.core.ColVector

inequality vector (dimension p)

x: visp._visp.core.ColVector

solution (dimension n)

tol: float = 1e-6

tolerance to test the ranks

Returns:

True if the solution was found.

solveQPe(self, Q: visp._visp.core.Matrix, r: visp._visp.core.ColVector, x: visp._visp.core.ColVector, tol: float = 1e-6) → bool

Solves a Quadratic Program under previously stored equality constraints ( setEqualityConstraint() )

Here is an example where the two following QPs are solved:

\(\begin{array}{lll} \mathbf{x} = & \arg\min & x_1^2 + x_2^2 \\& \text{s.t.}& x_1 + x_2 = 1\end{array}\)

\(\begin{array}{lll} \mathbf{x} = & \arg\min & (x_1-1)^2 + x_2^2 \\& \text{s.t.}& x_1 + x_2 = 1\end{array}\)

#include <visp3/core/vpLinProg.h>

int main()
{
  vpMatrix Q(2,2), A(1,2);
  vpColVector r(2), b(1);

  Q[0][0] = Q[1][1] = 1;
  A[0][0] = A[0][1] = b[0] = 1;

  vpQuadProg qp;
  qp.setEqualityConstraint(A, b);
  vpColVector x;

  // solve x_1^2 + x_2^2
  qp.solveQPe(Q, r, x);
  std::cout << x.t() << std::endl;  // prints (0.5 0.5)

  // solve (x_1-1)^2 + x_2^2
  r[0] = 1;
  qp.solveQPe(Q, r, x);
  std::cout << x.t() << std::endl;  // prints (1 0)
}

Note

See setEqualityConstraint() , solveQPe()

Parameters:
Q: visp._visp.core.Matrix

cost matrix (dimension c x n)

r: visp._visp.core.ColVector

cost vector (dimension c)

x: visp._visp.core.ColVector

solution (dimension n)

tol: float = 1e-6

Tolerance.

Returns:

True if the solution was found.

static solveQPeStatic(Q: visp._visp.core.Matrix, r: visp._visp.core.ColVector, A: visp._visp.core.Matrix, b: visp._visp.core.ColVector, x: visp._visp.core.ColVector, tol: float = 1e-6) → bool

Solves a Quadratic Program under equality constraints.

\(\begin{array}{lll} \mathbf{x} = & \arg\min & ||\mathbf{Q}\mathbf{x} - \mathbf{r}||^2 \\& \text{s.t.}& \mathbf{A}\mathbf{x} = \mathbf{b}\end{array}\)

If the equality constraints \((\mathbf{A}, \mathbf{b})\) are the same between two calls, it is more efficient to use setEqualityConstraint() and solveQPe() .

Here is an example:

\(\begin{array}{lll} \mathbf{x} = & \arg\min & (x_1-1)^2 + x_2^2 \\& \text{s.t.}& x_1 + x_2 = 1\end{array}\)

#include <visp3/core/vpLinProg.h>

int main()
{
  vpMatrix Q(2,2), A(1,2);
  vpColVector r(2), b(1);

  Q[0][0] = Q[1][1] = 1;
  r[0] = 1;
  A[0][0] = A[0][1] = b[0] = 1;

  vpColVector x;

  vpQuadProg::solveQPe(Q, r, A, b, x);
  std::cout << x.t() << std::endl;  // prints (1 0)
}

Note

See setEqualityConstraint() , solveQP() , solveQPi()

Parameters:
Q: visp._visp.core.Matrix

cost matrix (dimension c x n)

r: visp._visp.core.ColVector

cost vector (dimension c)

A: visp._visp.core.Matrix

equality matrix (dimension m x n)

b: visp._visp.core.ColVector

equality vector (dimension m)

x: visp._visp.core.ColVector

solution (dimension n)

tol: float = 1e-6

tolerance to test the ranks

Returns:

True if the solution was found.

solveQPi(self, Q: visp._visp.core.Matrix, r: visp._visp.core.ColVector, C: visp._visp.core.Matrix, d: visp._visp.core.ColVector, x: visp._visp.core.ColVector, use_equality: bool = false, tol: float = 1e-6) → bool

Solves a Quadratic Program under inequality constraints

Here is an example:

\(\begin{array}{lll} \mathbf{x} = & \arg\min & (x_1-1)^2 + x_2^2 \\& \text{s.t.}& x_1 + x_2 \leq 1 \\& \text{s.t.} & x_1, x_2 \geq 0\end{array}\)

#include <visp3/core/vpLinProg.h>

int main()
{
  vpMatrix Q(2,2), C(3,2);
  vpColVector r(2), d(1);

  Q[0][0] = Q[1][1] = 1;    r[0] = 1;
  C[0][0] = C[0][1] = 1;    d[0] = 1;
  C[1][0] = C[2][1] = -1;

  vpColVector x;
  vpQuadProg qp;

  qp.solveQPi(Q, r, C, d, x);
  std::cout << x.t() << std::endl;  // prints (1 0)
}
Parameters:
Q: visp._visp.core.Matrix

cost matrix (dimension c x n)

r: visp._visp.core.ColVector

cost vector (dimension c)

C: visp._visp.core.Matrix

inequality matrix (dimension p x n)

d: visp._visp.core.ColVector

inequality vector (dimension p)

x: visp._visp.core.ColVector

solution (dimension n)

use_equality: bool = false

if a previously saved equality constraint ( setEqualityConstraint() ) should be considered

tol: float = 1e-6

tolerance to test the ranks

Returns:

True if the solution was found.