Extreme points of a polyhedral set

36 ビュー (過去 30 日間)
Arjun M
Arjun M 2022 年 9 月 19 日
コメント済み: Arjun M 2022 年 9 月 20 日
I have a set of inequalities that form a polyhedral set. I want to find the extreme points of this. How do I do this? Also, in the image attached, there are only 4 variables. I would like to scale it up as well if needed (upto around 15). Kindly help.
An image of the constraints is attached. Kindly ignore the * on a few of the RHS values. Also for solvability, assume all b values are more than or equal to 0 (lower bounds).

採用された回答

John D'Errico
John D'Errico 2022 年 9 月 19 日
Was it really necessary to put a picture of the equations into your question, when simple text was just as easy? That means, in order for me to solve your problem as is, I need to retype all of your equations by hand, something I hate to do, as I will always make a mistake. These old eyes always get me in trouble these days.
Anyway, there are surely many ways to solve this. Here is one approach.
First, you would need to formulate the problem in a matrix form, of the form A*x <= b. I would also note that 4 of your "equations" are simply bound constraints.
LB = [0 0 0 0];
UB = [2 2 1 1];
A = [1 1 0 0;1 0 1 0;1 0 0 1;0 1 1 0;0 1 0 1;0 0 1 1;1 0 1 1;0 1 1 1]
A = 8×4
1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1
b = [3 3 2 2 2 1 3 3]'
b = 8×1
3 3 2 2 2 1 3 3
I THINK that represents your equations. Now you need ot recognize that a linear program will find ONE vertex of a simplex. So just use linprog, with different objective vectors.
The problem is, linprog only finds one vertex at a time. So I'll run linprog multiple times, using many different sets of orthogonal vectors for f.
vertices = zeros(0,4);
for iter = 1:10
f44 = orth(rand(4));
opts = optimset('linprog');
opts.Display = 'none';
for i = 1:4
vertices(end+1,:) = linprog(f44(:,i),A,b,[],[],LB,UB,opts);
end
end
At the end, vertices will have more solutions than we need, because some of the vertices will have been found ultiple times. So I'll discard them.
vertices = uniquetol(vertices,1e-12,'ByRows',true)
vertices = 12×4
0 0 0 1.0000 0 0 1.0000 0 0 1.0000 1.0000 0 0 1.5000 0.5000 0.5000 0 2.0000 0 0 1.0000 1.0000 0 1.0000 1.0000 2.0000 0 0 1.5000 1.5000 0.5000 0.5000 2.0000 0 0 0 2.0000 0 1.0000 0
We can see here that 12 solutions were found as vertices. in 4 dimensions, I would expect no more than 2^4=16 solutions, so this seems reasonable.
Note that in 15 dimensions, you may expect on the order of 2^15=32768 vertices.
  2 件のコメント
Arjun M
Arjun M 2022 年 9 月 20 日
Also, why are you iterating it 10 times? Is there a specific reason to that?

サインインしてコメントする。

その他の回答 (1 件)

Matt J
Matt J 2022 年 9 月 19 日
If the polyhedron is bounded, you can use lcon2vert, downloadable from,

カテゴリ

Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by