version 1.0.0.0 (2.03 KB) by
Michael Kleder

Convert convex constraint inequalities into a set of vertices; i.e., polygon "vertex enumeration."

15 Downloads

Updated 11 Jul 2005

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

V = 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)

NOTES:

(1) This program emplyes a primal-dual polytope method.

(2) In dimensions higher than 2, duplicate vertices can appear using this method. This program detects duplicates at up to twelve 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.

(5) At least two dimensions are required.

(6) See companion function VERT2CON.

(7) Numerous examples are provided.

(8) ver 1.0: initial version, June 2005

(9) ver 1.1: enhanced redundancy checks, July 2005

(10) Written by Michael Kleder

Michael Kleder (2021). CON2VERT - constraints to vertices (https://www.mathworks.com/matlabcentral/fileexchange/7894-con2vert-constraints-to-vertices), MATLAB Central File Exchange. Retrieved .

Created with
R14SP1

Compatible with any release

**Inspired:**
Analyze N-dimensional Convex Polyhedra, Ellipsoid Method, CON2VERT - constraints to vertices, updated

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

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Stephen BeckerI've made an updated branch of this code at https://www.mathworks.com/matlabcentral/fileexchange/91595-con2vert-constraints-to-vertices-updated which should fix some of the issues. In particular, this new version (1) has a better method to find a strictly feasible point, now using linear programming, and (2) it can now handle equality constraints (via a change-of-variables trick).

@William Warriner, I don't think that fix is right. You don't want the absolute value there, since then it may be Ax>b whereas we want Ax<b. @MattJ, this new version fixes the issues you had with your example: it can now find an interior point, and it won't return those NaNs (those come from points that were not really vertices and should have been eliminated).

Mahmoud HAMANDIIs it possible to provide a reference to the corresponding algorithm?

haitao liuThis code has some errors.

TonyWilliam WarrinerThere appears to be an error in checking for singularities on line 153. It should probably read: if ~all(abs(A*c - b) < tol) for some reasonable tolerance. Changing this line as described fixed an issue with https://www.mathworks.com/matlabcentral/fileexchange/50772-polytope-bounded-voronoi-diagram-in-2d-and-3d. I have also contacted that author.

Kieran WilsonExplanation or any sort of documentation of the algorithm used would be very helpful

Benjamin BauerHello Michael Kleder,

as Reza Jafari before I would like to use your code for my thesis. Would you please send me sufficient information for citation? My mail-address is "bauerb@rhrk.uni-kl.de". Thanks in advance!

Regards,

Benjamin Bauer

Joseph HellewellSergei SavinAli BaradaranReza JafariMichael Kleder,

Thanks for the useful code which your wrote. I used your code for the part of my dissemination and I need to cite your work. Would you please send me the information that I can cite your code? You can send your email to reza.jafari@okstate.edu

Regards,

Reza Jafari

Matt JI want to believe in this tool, but problems with it continue to surface. I will change my rating if we at least get a reference explaining the algorithm that it uses.

As the latest difficulty, CON2VERT fails with this set of data,

A = [0 0 0 -1 2 -1; -1 2 -1 0 0 0;eye(6);-eye(6)];

b=[zeros(2,1); 10*ones(12,1)];

which looks like it should be fine (bounded and solid in R^6), but convhulln chokes on it in line 158.

Part of the problem is again that it cannot find an interior point c in line 151, but it doesn't end there. Even if I override the code and start at Line 158 with my own interior point

c=[ 2.5000 -5.0000 2.5000 1.4286 -4.2857 1.4286].'

I still get some infinite/nan vertices as output,

>> V(end,:)

ans =

NaN -Inf 10.0000 -10.0000 -10.0000 -10.0000

I suspect part of the problem is that Line 167 should be skipped if F is not full rank, but without a reference to the algorithm used, I can't be sure...

Deepanshu VasalCan you give the reference for the algorithm used

Thanks

Matt JWith a little more investigation into the problem, I've discovered that with the A,b data in my previous comment, the call to FMINSEARCH fails to find an initial point c that lies inside the polytope.

The test

if ef ~= 1...

fails to catch this. A better test would probably be

if f>0...

I don't really know what a good fix would be. From what I've read, finding an initial point inside a polytope is a sophisticated problem.

Matt JNot sure if this file is being supported anymore, but there appears to be a problem. The point x=[2.5,3.5,1.8]'

is easily shown to satisfy

A*x<=b for the A,b data below. However, CON2VERT returns vertices that clearly do not enclose this point.

I'm wondering if the issue might be originating at this line

D = A ./ repmat(b,[1 size(A,2)]);

If any of the b(i) are negative, dividing through by b(i) will flip the direction of the corresponding inequality.

A=[1 0 0

0 1 0

0 0 1

-1 0 0

0 -1 0

0 0 -1

-0.387696185212551 -0.295276274520099 0.703237014010810

5.73326513862449 -0.422448628998633 -0.113292931747631

-3.79255233000727 -0.360645958414035 -0.673892379691217

-1.27188203250127 0.544750863219514 -0.791324376598499

-2.30540199426269 -2.50522755054822 -0.291771858420232

0.616578245027929 -0.654271120193835 0.574406987898971

-1.49508806389885 -2.68877782397954 -0.989225453798092

5.34556895341194 -0.717724903518731 0.589944082263178

-3.40485614479472 -0.0653696838939366 -1.37712939370203

-0.884185847288714 0.840027137739613 -1.49456139060931

-1.91770580905014 -2.20995127602812 -0.995008872431042

0.228882059815378 -0.949547394713933 1.27764400190978

-1.10739187868630 -2.39350154945944 -1.69246246780890

1.94071280861722 -0.783094587412668 -0.787185311438849

4.46138310612323 0.122302234220881 -0.904617308346131

3.42786314436180 -2.92767617954685 -0.405064790167863

5.11668689359657 0.231822491195202 -0.687699919646602

4.23817707472564 -3.11122645297817 -1.10251838554572

-2.52067029750601 -0.905396821633549 0.117431996907282

1.48715033574458 -2.14458159213419 0.382120521270985

-3.17597408497934 -1.01491707860787 -0.0994853917922465

2.29746426610842 -2.32813186556550 -0.315333074106875

-1.03351996176143 -3.04997841376774 0.499552518178267

-0.655303787473336 -0.109520256974320 -0.216917388699529

-0.223206031397585 -3.23352868719905 -0.197901077199593

-1.68882374923476 -3.15949867074206 0.282635129478739

-0.810313930363841 0.183550273431316 0.697453595377860

-0.878509818870922 -3.34304894417337 -0.414818465899121];

b=[6

4

2

0

0

0

-0.154147860211922

16.6671436561829

-8.83179250583593

-1.48693603688105

-8.92116339978305

0.423928365940654

-8.95704617639833

16.5129957959710

-8.67764464562401

-1.33278817666913

-8.76701553957113

0.269780505728732

-8.80289831618640

7.83535115034699

15.1802076193019

7.74598025639987

16.2432152902423

7.71009747978459

-7.34485646895489

-0.0893708939471196

-8.40786413989528

-0.125253670562397

-7.43422736290201

-1.06300767094039

-7.47011013951728

-8.49723503384240

0.0358827766152754

-8.53311781045768];

Dave BHi, is there a way to resolve the error:

"??? Error using ==> con2vert at 161

Non-bounding constraints detected. (Consider box constraints on variables.)" ?

mauro RI wish the program could determinate which vertices belong to the same facet.

vilmar nascimentolegal

Gol VGreat! It helped me to do my asssignment!

Sebastian TrimpeThat's what I've been looking for.

No problems.

carlos lworks for me. No problems so far. good job! and thanks.