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"

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, [e-mail]