pycvxset.Polytope

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

Bases: object

Polytope class.

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

  1. (A, b) for a polytope in halfspace representation (H-rep) \(\{x\ |\ Ax \leq b\}\),

  2. (A, b, Ae, be) for a polytope in halfspace representation (H-rep) with equality constraints \(\{x\ |\ Ax \leq b, A_e x = b_e\}\),

  3. V for a polytope in vertex representation (V-rep)\(\text{ConvexHull}(v_i)\) where \(v_i\) are rows of matrix V,

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

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

  6. dim for an empty Polytope of dimension dim (no argument generates a zero-dimensional empty Polytope),

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

  • V (array_like, optional) – List of vertices of the polytope (V-Rep). The list must be 2-dimensional with vertices arranged row-wise and the polytope dimension determined by the column count.

  • A (array_like, optional) – Inequality coefficient vectors (H-Rep). The vectors are stacked vertically with the polytope dimension determined by the column count. When A is provided, b must also be provided.

  • b (array_like, optional) – Inequality constants (H-Rep). The constants are expected to be in a 1D numpy array. When b is provided, A must also be provided.

  • Ae (array_like) – Equality coefficient vectors (H-Rep). The vectors are stacked vertically with matching number of columns as A. When Ae is provided, A, b, and be must also be provided.

  • be (array_like) – Equality coefficient constants (H-Rep). The constants are expected to be in a 1D numpy array. When be is provided, A, b, and Ae must also be provided.

  • lb (array_like, optional) – Lower bounds of the axis-aligned cuboid. Must be 1D array, and the polytope 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.

  • c (array_like, optional) – Center of the axis-aligned cuboid. Must be 1D array, and the polytope dimension is determined by number of elements in c. When c is provided, h 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.

Raises:
  • ValueError – When arguments provided is not one of [(A, b), (A, b, Ae, be), (lb, ub), (c, h), V, dim, NOTHING]

  • ValueError – Errors raised by issues with (A, b) and (Ae, be) — mismatch in dimensions, not convertible to appropriately-dimensioned numpy arrays, incompatible systems (A, b) and (Ae, be) etc.

  • ValueError – Errors raised by issues with V — not convertible to a 2-D numpy array, etc.

  • ValueError – Errors raised by issues with lb, ub — mismatch in dimensions, not convertible to 1D numpy arrays, etc.

  • ValueError – Errors raised by issues with c, h — mismatch in dimensions, not convertible to 1D numpy arrays, etc.

  • ValueError – Polytope is not bounded in any direction. We use a sufficient condition for speed, and therefore the detection may not be exhaustive.

  • ValueError – Polytope is not bounded in some directions. We use a sufficient condition for speed, and therefore the detection may not be exhaustive.

  • UserWarning – If some rows are removed from (A, b) due to all zeros in A or np.inf in b | (Ae, be) when all zeros in Ae and be.

__init__(**kwargs)[source]

Constructor for Polytope class.

Methods

__init__(**kwargs)

Constructor for Polytope class.

affine_map(M)

Compute the matrix times set.

chebyshev_centering()

Computes a ball with the largest radius that fits within the polytope.

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 polytope.

contains(Q)

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

copy()

Create a copy of the polytope

deflate_rectangle(set_to_be_centered)

Compute the rectangle with the smallest volume that contains the given set.

determine_H_rep()

Determine the halfspace representation from a given vertex representation of the polytope.

determine_V_rep()

Determine the vertex representation from a given halfspace representation of the polytope.

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([point_type])

Compute a point in the interior of the polytope.

intersection(Q)

Intersect the polytope \(\mathcal{P}\) with another polytope \(\mathcal{Q}\).

intersection_under_inverse_affine_map(Q, R)

Compute the intersection of constrained zonotope under an inverse affine map

intersection_with_affine_set(Ae, be)

Intersect the polytope with an affine set.

intersection_with_halfspaces(A, b)

Intersect the polytope with a collection of halfspaces.

inverse_affine_map_under_invertible_matrix(M)

Compute the set times matrix, the inverse affine map of the set under an invertible matrix M.

maximum_volume_inscribing_ellipsoid()

Compute the maximum volume ellipsoid that fits within the given polytope.

minimize(x, objective_to_minimize, cvxpy_args)

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

minimize_H_rep()

Remove any redundant inequalities from the halfspace representation of the polytope using cdd.

minimize_V_rep([prefer_qhull_over_cdd])

Remove any redundant vertices from the vertex representation of the polytope.

minimum_volume_circumscribing_ellipsoid()

Compute the minimum volume ellipsoid that covers the given polytope (also known as Lowner-John Ellipsoid).

minimum_volume_circumscribing_rectangle()

Compute the minimum volume circumscribing rectangle for a given polytope

minus(Q)

Implement - operation (Pontryagin difference when Q is a polytope, translation by -Q when Q is a point)

normalize()

Normalize a H-Rep such that each row of A has unit \(\ell_2\)-norm.

plot([ax, patch_args, vertex_args, ...])

Plot a 2D or 3D polytope.

plot2d([ax, patch_args, vertex_args, ...])

Plot a 2D polytope using matplotlib's add_patch(Polygon()).

plot3d([ax, patch_args, vertex_args, ...])

Plot a 3D polytope using matplotlib's Line3DCollection.

plus(Q)

Add a point or a set to the polytope

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.

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.

volume()

Compute the volume of the polytope using QHull

Attributes

A

Inequality coefficient vectors A for the polytope \(\{Ax \leq b, A_e x = b_e\}\).

Ae

Equality coefficient vectors Ae for the polytope \(\{Ax \leq b, A_e x = b_e\}\).

H

Inequality constraints in halfspace representation H=[A, b] for the polytope \(\{Ax \leq b, A_e x = b_e\}\).

He

Equality constraints in halfspace representation He=[Ae, be] for the polytope \(\{Ax \leq b, A_e x = b_e\}\).

V

Vertex representation (V) where the polytope is given by \(\text{ConvexHull}(v_i)\) with \(v_i\) as the rows of \(V=[v_1;v_2;\ldots;v_{n_vertices}]\).

b

Inequality constants b for the polytope \(\{Ax \leq b, A_e x = b_e\}\).

be

Equality constants be for the polytope \(\{Ax \leq b, A_e x = b_e\}\).

cvxpy_args_lp

CVXPY arguments in use when solving a linear program

cvxpy_args_sdp

CVXPY arguments in use when solving a semi-definite program

cvxpy_args_socp

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

dim

Dimension of the polytope.

in_H_rep

Check if the polytope have a halfspace representation (H-Rep).

in_V_rep

Check if the polytope have a vertex representation (V-Rep).

is_bounded

Check if the polytope is bounded.

is_empty

Check if the polytope is empty.

is_full_dimensional

Check if the affine dimension of the polytope is the same as the polytope dimension

n_equalities

Number of linear equality constraints used to define the polytope \(\{Ax \leq b, A_e x = b_e\}\)

n_halfspaces

Number of halfspaces used to define the polytope \(\{Ax \leq b, A_e x = b_e\}\)

n_vertices

Number of vertices