pycvxset.ConstrainedZonotope

class pycvxset.ConstrainedZonotope(**kwargs)[source]

Bases: object

Constrained zonotope class

Constrained zonotope defines a polytope in the working dimension \(\mathbb{R}^n\) as an affine transformation of a polytope defined in latent space \(B_\infty(A_e, b_e)\subset \mathbb{R}^{N_C}\). Here, \(B_\infty(A_e, b_e)\) is defined as the intersection of a unit \(\ell_\infty\)-norm ball and a collection of \(M_C\) linear constraints \(\{\xi\in\mathbb{R}^{N_C}|A_e \xi = b_e\}.\)

Formally, a constrained zonotope is defined as follows,

\[\mathcal{C} = \{G \xi + c\ |\ \xi \in B_\infty(A_e, b_e)\} \subset \mathbb{R}^n,\]

where

\[B_\infty(A_e, b_e)= \{\xi\ |\ \| \xi \|_\infty \leq 1, A_e \xi = b_e\} \subset \mathbb{R}^{N_C},\]

with \(G\in\mathbb{R}^{n\times N_C}\), \(c\in\mathbb{R}^{n}\), \(A_e\in\mathbb{R}^{M_C\times N_C}\), and \(b\in\mathbb{R}^{M_C}\).

A constrained zonotope provide an alternative and equivalent representation of any convex and compact polytope. Furthermore, a constrained zonotope admits closed-form expressions for several set manipulations that can often be accomplished without invoking any optimization solvers. See [SDGR16] [RK22] [VWD24] for more details.

A zonotope is a special class of constrained zonotopes, and are defined as

\[\mathcal{Z} = \{G \xi + c\ |\ \|\xi\|_\infty \leq 1\} \subset \mathbb{R}^n.\]

In other words, a zonotope is a constrained zonotope with no equality constraints in the latent dimension space. In ConstrainedZonotope, we model zonotopes by having (Ae,be) be empty (n_equalities is zero).

Constrained zonotope object construction admits one of the following combinations (as keyword arguments):

  1. dim for an empty constrained zonotope of dimension dim,

  2. (G, c, Ae, be) for a constrained zonotope,

  3. (G, c) for a zonotope,

  4. (lb, ub) for a zonotope equivalent to an axis-aligned cuboid with appropriate bounds \(\{x\ |\ lb\leq x \leq ub\}\), and

  5. (c, h) for a zonotope equivalent to an axis-aligned cuboid centered at c with specified scalar/vector half-sides \(h\), \(\{x\ |\ \forall i\in\{1,2,...,n\}, |x_i - c_i| \leq h_i\}\).

  6. (c=p, G=None) for a zonotope equivalent to a single point p,

  7. P for a constrained zonotope equivalent to the pycvxset.Polytope.Polytope object P,

Parameters:

  • dim (int, optional) – Dimension of the empty constrained zonotope. If NOTHING is provided, dim=0 is assumed.

  • c (array_like, optional) – Affine transformation translation vector. Must be 1D array, and the constrained zonotope dimension is determined by number of elements in c. When c is provided, either (G) or (G, Ae, be) or (h) must be provided additionally. When h is provided, c is the centroid of the resulting zonotope.

  • G (array_like) – Affine transformation matrix. The vectors are stacked vertically with matching number of rows as c. When G is provided, (c, Ae, be) OR (c) must also be provided. To define a constrained zonotope with a single point, set c to the point AND G to None (do not set (Ae, be) or set them to (None, None)).

  • Ae (array_like) – Equality coefficient vectors. The vectors are stacked vertically with matching number of columns as G. When Ae is provided, (G, c, be) must also be provided.

  • be (array_like) – Equality coefficient constants. The constants are expected to be in a 1D numpy array. When be is provided, (G, c, Ae) must also be provided.

  • lb (array_like, optional) – Lower bounds of the axis-aligned cuboid. Must be 1D array, and the constrained zonotope dimension is determined by number of elements in lb. When lb is provided, ub must also be provided.

  • ub (array_like, optional) – Upper bounds of the axis-aligned cuboid. Must be 1D array of length as same as lb. When ub is provided, lb must also be provided.

  • h (array_like, optional) – Half-side length of the axis-aligned cuboid. Can be a scalar or a vector of length as same as c. When h is provided, c must also be provided.

  • polytope (Polytope, optional) – Polytope to use to construct constrained zonotope.

Raises:

  • ValueError – (G, c) is not compatible.

  • ValueError – (G, c, Ae, be) is not compatible.

  • ValueError – (lb, ub) is not valid

  • ValueError – (c, h) is not valid

  • ValueError – Provided polytope is not bounded.

  • UserWarning – When a row with all zeros in Ae and be.

__init__(**kwargs)[source]

Constructor for ConstrainedZonotope class

Methods

__init__(**kwargs)

Constructor for ConstrainedZonotope class

affine_map(M)

Multiply a matrix or a scalar with a constrained zonotope

approximate_pontryagin_difference(norm_type, ...)

Approximate Pontryagin difference between a constrained zonotope and an affine transformation of a unit-norm ball.

cartesian_product(sequence_Q)

Generate the Cartesian product of a set \(\mathcal{Q}\) (or a list of mathcal{Q}) with \(\mathcal{P}\).

chebyshev_centering()

Computes a ball with the largest radius that fits within the constrained zonotope.

closest_point(points[, p])

Wrapper for project() to compute the point in the convex set closest to the given point.

containment_constraints(x[, flatten_order])

Get CVXPY constraints for containment of x (a cvxpy.Variable) in a constrained zonotope.

contains(Q[, verbose, time_limit])

Check containment of a set \(\mathcal{Q}\) (could be a polytope or a constrained zonotope), or a collection of points \(Q \in \mathbb{R}^{n_Q \times \mathcal{P}.\text{dim}}\) in the given constrained zonotope.

copy()

Get a copy of the constrained zonotope

distance(points[, p])

Wrapper for project() to compute distance of a point to a convex set.

extreme(eta)

Wrapper for support() to compute the extreme point.

interior_point()

Compute an interior point of the constrained zonotope.

intersection(Q)

Compute the intersection of constrained zonotope with another constrained zonotope or polytope.

intersection_under_inverse_affine_map(Y, R)

Compute the intersection of constrained zonotope with another constrained zonotope under an inverse affine map

intersection_with_affine_set(Ae, be)

Compute the intersection of a constrained zonotope with an affine set.

intersection_with_halfspaces(A, b)

Compute the intersection of a constrained zonotope with a collection of halfspaces (polyhedron).

inverse_affine_map_under_invertible_matrix(M)

Compute the inverse affine map of a constrained zonotope for a given matrix M.

maximum_volume_inscribing_ellipsoid()

Compute the maximum volume ellipsoid that fits within the given constrained zonotope.

minimize(x, objective_to_minimize, cvxpy_args)

Solve a convex program with CVXPY objective subject to containment constraints.

minimum_volume_circumscribing_rectangle()

Compute the minimum volume circumscribing rectangle for a set.

minus(Q)

Implement - operation: Pontryagin difference with a constrained zonotope minuend

plot([method, ax, direction_vectors, ...])

Plot a polytopic approximation of the set.

plus(Q)

Add a point or a set Q to a constrained zonotope (Minkowski sum).

polytopic_inner_approximation([...])

Compute a polytopic inner-approximation of a given set via ray shooting.

polytopic_outer_approximation([...])

Compute a polytopic outer-approximation of a given set via ray shooting.

project(x[, p])

Project a point or a collection of points on to a set.

projection(project_away_dims)

Orthogonal projection of a set \(\mathcal{P}\) after removing some user-specified dimensions.

remove_redundancies()

Remove any redundancies in the equality system using pycddlib and other geometric properties

slice(dims, constants)

Slice a set restricting certain dimensions to constants.

slice_then_projection(dims, constants)

Wrapper for slice() and projection().

support(eta)

Evaluates the support function and support vector of a set.

Attributes

Ae

Equality coefficient vectors Ae for the constrained zonotope.

G

Affine transformation matrix G for the constrained zonotope.

He

Equality constraints He=[Ae, be] for the constrained zonotope.

be

Equality constants be for the constrained zonotope.

c

Affine transformation vector c for the constrained zonotope.

cvxpy_args_lp

CVXPY arguments in use when solving a linear program

cvxpy_args_socp

CVXPY arguments in use when solving a second-order cone program

dim

Dimension of the constrained zonotope.

is_bounded

Check if the constrained zonotope is bounded (which is always True)

is_empty

Check if the constrained zonotope is empty

is_full_dimensional

Check if the affine dimension of the constrained zonotope is the same as the constrained zonotope dimension

is_singleton

Check if the constrained zonotope is a singleton

is_zonotope

Check if the constrained zonotope is a zonotope

latent_dim

Latent dimension of the constrained zonotope.

n_equalities

Number of equality constraints used when defining the constrained zonotope.