Linear Projection

Principle

Computing the projection of a convex set bounded by linear equalities and inequalities is a particular case of Recursive Projection. Indeed, in this case \(x \in P\) can be directly written as:

\[\begin{split}A x &\leq b \\ C x &= d\end{split}\]

And thus, finding extremal points amounts to solving Linear Programs (LP). Denoting the affine projection onto a smaller space by \(y = E x + f\) (same convention as Stéphane Caron), finding extremal points corresponding to a direction \(\delta\) is done by solving:

\[\begin{split}max & \qquad \delta^T (E x + f)\\ s.t. & \qquad A x \leq b\\ & \qquad C x = d\end{split}\]

A specific class is shown below.

Example of usage

The following example (contained in hypercube.py) shows how to project a 6D hypercube in 3D, resulting in a cube:

import stabilipy as stab
import numpy as np

if __name__ == '__main__':

   A = np.vstack((np.eye(6), -np.eye(6)))
   b = np.ones(12,)

   linear_proj = stab.LinearProjection(3, A, b, None, None)
   linear_proj.compute(stab.Mode.precision, solver='cdd', epsilon=1e-3)

Important notes:

  • You need to specify the dimension you are projecting onto
  • If you do not specify the projection operator \(E, f\), it will default to projecting on the first dimension dimensions.

Class API

class stabilipy.LinearProjection(dimension, A, b, C, d, E=None, f=None)

Recursively compute the projection of a linear set: \(A x \leq b, C x = d\) onto \(y = E x + f\)

Create a linear projection problem.

Parameters:
  • dimension (int) – Dimension on which to project
  • A (np.array(nrineq, dim)) – Linear inequality matrix
  • b (np.array(nrineq,)) – Linear inequality RHS
  • C (np.array(nreq, dim)) – Linear equality matrix
  • d (np.array(nreq,)) – Linear equality RHS
  • E (np.array(dimension, dim)) – Projection matrix
  • f (np.array(dimension,)) – Projection offset