The shape of a feasible region with equality and inequality constraints
$begingroup$
I was wondering if anyone can help me with this (probably basic) question.
I want to know how the following feasible region looks like if we have thousands of variables. The constraints are linear. The region is convex and closed. Does the region have a scientific or mathematical name and specific properties (especially for finding projections of vectors on this region)?
begin{array}{ll}
& Ax = b \
& Bx le d \
&x ge 0.
end{array}
Thanks a lot for your time and help.
convex-analysis linear-programming constraints
asked Dec 9 '18 at 1:01
Mehrzad Mehrzad
63
$endgroup$
add a comment |
$begingroup$
I was wondering if anyone can help me with this (probably basic) question.
I want to know how the following feasible region looks like if we have thousands of variables. The constraints are linear. The region is convex and closed. Does the region have a scientific or mathematical name and specific properties (especially for finding projections of vectors on this region)?
begin{array}{ll}
& Ax = b \
& Bx le d \
&x ge 0.
end{array}
Thanks a lot for your time and help.
convex-analysis linear-programming constraints
asked Dec 9 '18 at 1:01
Mehrzad Mehrzad
63
$endgroup$
$begingroup$
Welcome to Math.SE! I don't understand what you are asking for specifically. If there are thousands of variables, then it isn't possible to visualize, right? Anyway this would just be a (thousands-dimensional) polyhedron right? Are you referring to LP? en.wikipedia.org/wiki/Linear_programming Any effort that could be put into clarifying this question would be appreciated.
$endgroup$
– Chill2Macht
Dec 9 '18 at 1:10
$begingroup$
Thanks for your reply. I am not familiar with mathematical terms, so I am looking to understand if the region has a special characteristic that I can use to find projections much easier (find an answer to this question math.stackexchange.com/questions/3030617/…).
$endgroup$
– Mehrzad
Dec 9 '18 at 2:06
$begingroup$
As Chill2Macht notes, it’s a polyhedron. Optimizing linear and quadratic objective functions over polyhedra can be done very efficiently, even for thousands of variables. I suspect there is no better way, unless you know more about $A$, $B$, etc.
$endgroup$
– David M.
Dec 12 '18 at 5:10
$begingroup$
Thanks for your answer. Yes. I can solve it using CPLEX, but I need to find this projection over thousands of iterations too, so I am looking for a really fast performing way. In fact, computational time is really important in my case. I know what are A and B, but what specific structure should I look for in A and B? any resource (book, paper or webpage) that explains how the projection becomes easier like multiplying matrices instead of optimization and in which cases (what should be A and B) will really help too. Thanks in advance.
$endgroup$
– Mehrzad
Dec 13 '18 at 0:44
add a comment |
$begingroup$
I was wondering if anyone can help me with this (probably basic) question.
I want to know how the following feasible region looks like if we have thousands of variables. The constraints are linear. The region is convex and closed. Does the region have a scientific or mathematical name and specific properties (especially for finding projections of vectors on this region)?
begin{array}{ll}
& Ax = b \
& Bx le d \
&x ge 0.
end{array}
Thanks a lot for your time and help.
convex-analysis linear-programming constraints
asked Dec 9 '18 at 1:01
Mehrzad Mehrzad
63
$endgroup$
I was wondering if anyone can help me with this (probably basic) question.
I want to know how the following feasible region looks like if we have thousands of variables. The constraints are linear. The region is convex and closed. Does the region have a scientific or mathematical name and specific properties (especially for finding projections of vectors on this region)?
begin{array}{ll}
& Ax = b \
& Bx le d \
&x ge 0.
end{array}
Thanks a lot for your time and help.
convex-analysis linear-programming constraints
convex-analysis linear-programming constraints
asked Dec 9 '18 at 1:01
Mehrzad Mehrzad
63
asked Dec 9 '18 at 1:01
Mehrzad Mehrzad
63
asked Dec 9 '18 at 1:01
Mehrzad Mehrzad
63
asked Dec 9 '18 at 1:01
Mehrzad Mehrzad
63
asked Dec 9 '18 at 1:01
Mehrzad Mehrzad
63
63
$begingroup$
Welcome to Math.SE! I don't understand what you are asking for specifically. If there are thousands of variables, then it isn't possible to visualize, right? Anyway this would just be a (thousands-dimensional) polyhedron right? Are you referring to LP? en.wikipedia.org/wiki/Linear_programming Any effort that could be put into clarifying this question would be appreciated.
$endgroup$
– Chill2Macht
Dec 9 '18 at 1:10
$begingroup$
Thanks for your reply. I am not familiar with mathematical terms, so I am looking to understand if the region has a special characteristic that I can use to find projections much easier (find an answer to this question math.stackexchange.com/questions/3030617/…).
$endgroup$
– Mehrzad
Dec 9 '18 at 2:06
$begingroup$
As Chill2Macht notes, it’s a polyhedron. Optimizing linear and quadratic objective functions over polyhedra can be done very efficiently, even for thousands of variables. I suspect there is no better way, unless you know more about $A$, $B$, etc.
$endgroup$
– David M.
Dec 12 '18 at 5:10
$begingroup$
Thanks for your answer. Yes. I can solve it using CPLEX, but I need to find this projection over thousands of iterations too, so I am looking for a really fast performing way. In fact, computational time is really important in my case. I know what are A and B, but what specific structure should I look for in A and B? any resource (book, paper or webpage) that explains how the projection becomes easier like multiplying matrices instead of optimization and in which cases (what should be A and B) will really help too. Thanks in advance.
$endgroup$
– Mehrzad
Dec 13 '18 at 0:44
add a comment |
$begingroup$
Welcome to Math.SE! I don't understand what you are asking for specifically. If there are thousands of variables, then it isn't possible to visualize, right? Anyway this would just be a (thousands-dimensional) polyhedron right? Are you referring to LP? en.wikipedia.org/wiki/Linear_programming Any effort that could be put into clarifying this question would be appreciated.
$endgroup$
– Chill2Macht
Dec 9 '18 at 1:10
$begingroup$
Thanks for your reply. I am not familiar with mathematical terms, so I am looking to understand if the region has a special characteristic that I can use to find projections much easier (find an answer to this question math.stackexchange.com/questions/3030617/…).
$endgroup$
– Mehrzad
Dec 9 '18 at 2:06
$begingroup$
As Chill2Macht notes, it’s a polyhedron. Optimizing linear and quadratic objective functions over polyhedra can be done very efficiently, even for thousands of variables. I suspect there is no better way, unless you know more about $A$, $B$, etc.
$endgroup$
– David M.
Dec 12 '18 at 5:10
$begingroup$
Thanks for your answer. Yes. I can solve it using CPLEX, but I need to find this projection over thousands of iterations too, so I am looking for a really fast performing way. In fact, computational time is really important in my case. I know what are A and B, but what specific structure should I look for in A and B? any resource (book, paper or webpage) that explains how the projection becomes easier like multiplying matrices instead of optimization and in which cases (what should be A and B) will really help too. Thanks in advance.
$endgroup$
– Mehrzad
Dec 13 '18 at 0:44
$begingroup$
Welcome to Math.SE! I don't understand what you are asking for specifically. If there are thousands of variables, then it isn't possible to visualize, right? Anyway this would just be a (thousands-dimensional) polyhedron right? Are you referring to LP? en.wikipedia.org/wiki/Linear_programming Any effort that could be put into clarifying this question would be appreciated.
$endgroup$
– Chill2Macht
Dec 9 '18 at 1:10
$begingroup$
Welcome to Math.SE! I don't understand what you are asking for specifically. If there are thousands of variables, then it isn't possible to visualize, right? Anyway this would just be a (thousands-dimensional) polyhedron right? Are you referring to LP? en.wikipedia.org/wiki/Linear_programming Any effort that could be put into clarifying this question would be appreciated.
$endgroup$
– Chill2Macht
Dec 9 '18 at 1:10
$begingroup$
Thanks for your reply. I am not familiar with mathematical terms, so I am looking to understand if the region has a special characteristic that I can use to find projections much easier (find an answer to this question math.stackexchange.com/questions/3030617/…).
$endgroup$
– Mehrzad
Dec 9 '18 at 2:06
$begingroup$
Thanks for your reply. I am not familiar with mathematical terms, so I am looking to understand if the region has a special characteristic that I can use to find projections much easier (find an answer to this question math.stackexchange.com/questions/3030617/…).
$endgroup$
– Mehrzad
Dec 9 '18 at 2:06
$begingroup$
As Chill2Macht notes, it’s a polyhedron. Optimizing linear and quadratic objective functions over polyhedra can be done very efficiently, even for thousands of variables. I suspect there is no better way, unless you know more about $A$, $B$, etc.
$endgroup$
– David M.
Dec 12 '18 at 5:10
$begingroup$
As Chill2Macht notes, it’s a polyhedron. Optimizing linear and quadratic objective functions over polyhedra can be done very efficiently, even for thousands of variables. I suspect there is no better way, unless you know more about $A$, $B$, etc.
$endgroup$
– David M.
Dec 12 '18 at 5:10
$begingroup$
Thanks for your answer. Yes. I can solve it using CPLEX, but I need to find this projection over thousands of iterations too, so I am looking for a really fast performing way. In fact, computational time is really important in my case. I know what are A and B, but what specific structure should I look for in A and B? any resource (book, paper or webpage) that explains how the projection becomes easier like multiplying matrices instead of optimization and in which cases (what should be A and B) will really help too. Thanks in advance.
$endgroup$
– Mehrzad
Dec 13 '18 at 0:44
$begingroup$
Thanks for your answer. Yes. I can solve it using CPLEX, but I need to find this projection over thousands of iterations too, so I am looking for a really fast performing way. In fact, computational time is really important in my case. I know what are A and B, but what specific structure should I look for in A and B? any resource (book, paper or webpage) that explains how the projection becomes easier like multiplying matrices instead of optimization and in which cases (what should be A and B) will really help too. Thanks in advance.
$endgroup$
– Mehrzad
Dec 13 '18 at 0:44
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The mathematical name for this region is convex hull.
Now, how does this region look like ? It is not representable if you have thousands of variables, as we cannot see in $4D$ and above. Each variable is a dimension, so you can only draw the region if there are less than $3$ variables.
In $3D$ it would look like this.
answered Dec 9 '18 at 14:28
KuifjeKuifje
7,1302725
$endgroup$
$begingroup$
Thanks a lot for your answer. Does this set include the inner part of the convex hull in this figure "commons.wikimedia.org/wiki/…" or does this set only include the boundaries of this convex hull (since there are equality constraints, and all variables should satisfy some type of equality constraints)?
$endgroup$
– Mehrzad
Dec 9 '18 at 19:27
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031887%2fthe-shape-of-a-feasible-region-with-equality-and-inequality-constraints%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The mathematical name for this region is convex hull.
Now, how does this region look like ? It is not representable if you have thousands of variables, as we cannot see in $4D$ and above. Each variable is a dimension, so you can only draw the region if there are less than $3$ variables.
In $3D$ it would look like this.
answered Dec 9 '18 at 14:28
KuifjeKuifje
7,1302725
$endgroup$
$begingroup$
Thanks a lot for your answer. Does this set include the inner part of the convex hull in this figure "commons.wikimedia.org/wiki/…" or does this set only include the boundaries of this convex hull (since there are equality constraints, and all variables should satisfy some type of equality constraints)?
$endgroup$
– Mehrzad
Dec 9 '18 at 19:27
add a comment |
$begingroup$
The mathematical name for this region is convex hull.
Now, how does this region look like ? It is not representable if you have thousands of variables, as we cannot see in $4D$ and above. Each variable is a dimension, so you can only draw the region if there are less than $3$ variables.
In $3D$ it would look like this.
answered Dec 9 '18 at 14:28
KuifjeKuifje
7,1302725
$endgroup$
$begingroup$
Thanks a lot for your answer. Does this set include the inner part of the convex hull in this figure "commons.wikimedia.org/wiki/…" or does this set only include the boundaries of this convex hull (since there are equality constraints, and all variables should satisfy some type of equality constraints)?
$endgroup$
– Mehrzad
Dec 9 '18 at 19:27
add a comment |
$begingroup$
The mathematical name for this region is convex hull.
Now, how does this region look like ? It is not representable if you have thousands of variables, as we cannot see in $4D$ and above. Each variable is a dimension, so you can only draw the region if there are less than $3$ variables.
In $3D$ it would look like this.
answered Dec 9 '18 at 14:28
KuifjeKuifje
7,1302725
$endgroup$
The mathematical name for this region is convex hull.
Now, how does this region look like ? It is not representable if you have thousands of variables, as we cannot see in $4D$ and above. Each variable is a dimension, so you can only draw the region if there are less than $3$ variables.
In $3D$ it would look like this.
answered Dec 9 '18 at 14:28
KuifjeKuifje
7,1302725
answered Dec 9 '18 at 14:28
KuifjeKuifje
7,1302725
answered Dec 9 '18 at 14:28
KuifjeKuifje
7,1302725
answered Dec 9 '18 at 14:28
KuifjeKuifje
7,1302725
7,1302725
$begingroup$
Thanks a lot for your answer. Does this set include the inner part of the convex hull in this figure "commons.wikimedia.org/wiki/…" or does this set only include the boundaries of this convex hull (since there are equality constraints, and all variables should satisfy some type of equality constraints)?
$endgroup$
– Mehrzad
Dec 9 '18 at 19:27
add a comment |
$begingroup$
Thanks a lot for your answer. Does this set include the inner part of the convex hull in this figure "commons.wikimedia.org/wiki/…" or does this set only include the boundaries of this convex hull (since there are equality constraints, and all variables should satisfy some type of equality constraints)?
$endgroup$
– Mehrzad
Dec 9 '18 at 19:27
$begingroup$
Thanks a lot for your answer. Does this set include the inner part of the convex hull in this figure "commons.wikimedia.org/wiki/…" or does this set only include the boundaries of this convex hull (since there are equality constraints, and all variables should satisfy some type of equality constraints)?
$endgroup$
– Mehrzad
Dec 9 '18 at 19:27
$begingroup$
Thanks a lot for your answer. Does this set include the inner part of the convex hull in this figure "commons.wikimedia.org/wiki/…" or does this set only include the boundaries of this convex hull (since there are equality constraints, and all variables should satisfy some type of equality constraints)?
$endgroup$
– Mehrzad
Dec 9 '18 at 19:27
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031887%2fthe-shape-of-a-feasible-region-with-equality-and-inequality-constraints%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Welcome to Math.SE! I don't understand what you are asking for specifically. If there are thousands of variables, then it isn't possible to visualize, right? Anyway this would just be a (thousands-dimensional) polyhedron right? Are you referring to LP? en.wikipedia.org/wiki/Linear_programming Any effort that could be put into clarifying this question would be appreciated.
$endgroup$
– Chill2Macht
Dec 9 '18 at 1:10
$begingroup$
Thanks for your reply. I am not familiar with mathematical terms, so I am looking to understand if the region has a special characteristic that I can use to find projections much easier (find an answer to this question math.stackexchange.com/questions/3030617/…).
$endgroup$
– Mehrzad
Dec 9 '18 at 2:06
$begingroup$
As Chill2Macht notes, it’s a polyhedron. Optimizing linear and quadratic objective functions over polyhedra can be done very efficiently, even for thousands of variables. I suspect there is no better way, unless you know more about $A$, $B$, etc.
$endgroup$
– David M.
Dec 12 '18 at 5:10
$begingroup$
Thanks for your answer. Yes. I can solve it using CPLEX, but I need to find this projection over thousands of iterations too, so I am looking for a really fast performing way. In fact, computational time is really important in my case. I know what are A and B, but what specific structure should I look for in A and B? any resource (book, paper or webpage) that explains how the projection becomes easier like multiplying matrices instead of optimization and in which cases (what should be A and B) will really help too. Thanks in advance.
$endgroup$
– Mehrzad
Dec 13 '18 at 0:44