CON2VERT - constraints to vertices, updated

Updated version of M. Kleder's '05 CON2VERT. Convert linear inequalities into a set of vertices; i.e., polygon "vertex enumeration"
242 Downloads
Updated 4 May 2021

View License

CON2VERT - convert a convex set of constraint inequalities into the set of vertices at the intersections of those inequalities; i.e., solve the "vertex enumeration" problem. Additionally, identify redundant entries in the list of inequalities.

This is an updated version ("Ver 1.2") of Michael Kleder's 2005 FileExchange "Con2Vert". This new version features improvements, fixes issues, and can handle equality constraints.

V = con2vert(A,b)
[V,nr] = con2vert(A,b)

Converts the polytope (convex polygon, polyhedron, etc.) defined by the system of inequalities A*x <= b into a list of vertices V. Each ROW of V is a vertex. For n variables:
A = m x n matrix, where m >= n (m constraints, n variables)
b = m x 1 vector (m constraints)
V = p x n matrix (p vertices, n variables)
nr = list of the rows in A which are NOT redundant constraints

... = con2vert(A,b,F,d)
also adds the equality constraints F*x = d in addition to A*x <= b
New in ver 1.2

... = con2vert(A,b,F,d,DEBUG)
will give more verbose output. Set F=[] and d=[] if you do not want to include the equality constraints.
New in ver 1.2

NOTES:
(1) This program employs a primal-dual polytope method.
(2) In dimensions higher than 2, redundant vertices can appear using this method. This program detects redundancies at up to 10 digits of precision, then returns the unique vertices.
(3) Non-bounding constraints give erroneous results; therefore, the program detects non-bounding constraints and returns an error. You may wish to implement large "box" constraints on your variables if you need to induce bounding. For example, if x is a person's height in feet, the box constraint -1 <= x <= 1000 would be a reasonable choice to induce boundedness, since no possible solution for x would be prohibited by the bounding box.
(4) This program requires that the feasible region have some finite extent in all dimensions. For example, the feasible region cannot be a line segment in 2-D space, or a plane in 3-D space.
NOTE: this ver 1.2 updated version can handle affine constraints as they are explicit in the Fx == d constraints
(5) At least two dimensions are required.
(6) See companion function VERT2CON.
(7) ver 1.0: initial version, June 2005
(8) ver 1.1: enhanced redundancy checks, July 2005
(9) Written by Michael Kleder

2021 update for ver 1.2:
(10) ver 1.2 handles Fx == d constraints and uses linear programming rather than fminsearch to find strictly feasible point.
Explicitly handling equality constraints is necessary since if you tried to implicitly encode them using Fx <= d and -Fx <= -d then this code would fail since the code requires finding a *strictly* feasible point (e.g., an interior point). By explicitly handling the equality constraints, we only need to find a point in the relative interior.
Almost all the significant computing time is due to convhulln, which is Matlab's wrapper to qhull (see www.qhull.org). As dimensions increase above 10, this rapidly gets slow.
Ver 1.2 programmed by Stephen Becker, May 1 2021, Stephen.Becker@Colorado.edu

Cite As

Stephen Becker (2024). CON2VERT - constraints to vertices, updated (https://www.mathworks.com/matlabcentral/fileexchange/91595-con2vert-constraints-to-vertices-updated), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2021a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Acknowledgements

Inspired by: CON2VERT - constraints to vertices

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.2