Extreme points of a polyhedral set
9 ビュー (過去 30 日間)
古いコメントを表示
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).
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1128995/image.png)
0 件のコメント
採用された回答
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]
b = [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)
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.
その他の回答 (1 件)
Matt J
2022 年 9 月 19 日
If the polyhedron is bounded, you can use lcon2vert, downloadable from,
0 件のコメント
参考
カテゴリ
Help Center および File Exchange で Matrix Indexing についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!