Can the simplex method be used for general monotonically increasing objective functions?A question about the...
Simple image editor tool to draw a simple box/rectangle in an existing image
Can I rely on these GitHub repository files?
The One-Electron Universe postulate is true - what simple change can I make to change the whole universe?
In Star Trek IV, why did the Bounty go back to a time when whales were already rare?
How do ultrasonic sensors differentiate between transmitted and received signals?
Is there an wasy way to program in Tikz something like the one in the image?
Resetting two CD4017 counters simultaneously, only one resets
Is there a problem with hiding "forgot password" until it's needed?
Installing PowerShell on 32-bit Kali OS fails
How can a jailer prevent the Forge Cleric's Artisan's Blessing from being used?
No idea how to draw this using tikz
Can I use my Chinese passport to enter China after I acquired another citizenship?
Can a Gentile theist be saved?
What do you call the infoboxes with text and sometimes images on the side of a page we find in textbooks?
Is there an Impartial Brexit Deal comparison site?
Indicating multiple different modes of speech (fantasy language or telepathy)
Calculating the number of days between 2 dates in Excel
How will losing mobility of one hand affect my career as a programmer?
Lifted its hind leg on or lifted its hind leg towards?
Is exact Kanji stroke length important?
I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?
Stereotypical names
Was the picture area of a CRT a parallelogram (instead of a true rectangle)?
How can I raise concerns with a new DM about XP splitting?
Can the simplex method be used for general monotonically increasing objective functions?
A question about the operation research and simplex methodComputing the Optimal Simplex Tableau for Linear ProgrammingSimplex Method and Unrestricted VariablesMinimisation in Linear ProgrammingCan I minimize this with Simplex Method?Homework - How can I find the solution of a 2 variable simplex in one iteration?Detecting infeasible solutions in the Simplex method in codeCorrectness of the artificial constraint method (dual simplex)Primal-dual correspondence in the simplex methodHow To Use The Simplex Method When Having More Variables Than Constraints
$begingroup$
The simplex method relies on the fact that if you have a linear objective function and linear constraints, the optima must lie on one of the vertices of the simplex formed by the constraints. Let's say now that the objective function is not linear, but monotonically increasing in all the input variables. Let's take an example:
Minimize:
$$e^x+e^y$$
s.t.
$$Avec{x} leq vec{b}$$
Where $vec{x} = (x,y)$ and $A$ is a $n times 2$ matrix.
Can we not say that the optima must still lie on one of the vertices?
optimization linear-programming simplex constraints
asked Mar 14 at 20:59
Rohit PandeyRohit Pandey
1,6331023
$endgroup$
add a comment |
$begingroup$
The simplex method relies on the fact that if you have a linear objective function and linear constraints, the optima must lie on one of the vertices of the simplex formed by the constraints. Let's say now that the objective function is not linear, but monotonically increasing in all the input variables. Let's take an example:
Minimize:
$$e^x+e^y$$
s.t.
$$Avec{x} leq vec{b}$$
Where $vec{x} = (x,y)$ and $A$ is a $n times 2$ matrix.
Can we not say that the optima must still lie on one of the vertices?
optimization linear-programming simplex constraints
asked Mar 14 at 20:59
Rohit PandeyRohit Pandey
1,6331023
$endgroup$
add a comment |
$begingroup$
The simplex method relies on the fact that if you have a linear objective function and linear constraints, the optima must lie on one of the vertices of the simplex formed by the constraints. Let's say now that the objective function is not linear, but monotonically increasing in all the input variables. Let's take an example:
Minimize:
$$e^x+e^y$$
s.t.
$$Avec{x} leq vec{b}$$
Where $vec{x} = (x,y)$ and $A$ is a $n times 2$ matrix.
Can we not say that the optima must still lie on one of the vertices?
optimization linear-programming simplex constraints
asked Mar 14 at 20:59
Rohit PandeyRohit Pandey
1,6331023
$endgroup$
The simplex method relies on the fact that if you have a linear objective function and linear constraints, the optima must lie on one of the vertices of the simplex formed by the constraints. Let's say now that the objective function is not linear, but monotonically increasing in all the input variables. Let's take an example:
Minimize:
$$e^x+e^y$$
s.t.
$$Avec{x} leq vec{b}$$
Where $vec{x} = (x,y)$ and $A$ is a $n times 2$ matrix.
Can we not say that the optima must still lie on one of the vertices?
optimization linear-programming simplex constraints
optimization linear-programming simplex constraints
asked Mar 14 at 20:59
Rohit PandeyRohit Pandey
1,6331023
asked Mar 14 at 20:59
Rohit PandeyRohit Pandey
1,6331023
asked Mar 14 at 20:59
Rohit PandeyRohit Pandey
1,6331023
asked Mar 14 at 20:59
Rohit PandeyRohit Pandey
1,6331023
asked Mar 14 at 20:59
Rohit PandeyRohit Pandey
1,6331023
1,6331023
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
No, we can't. Consider minimizing $e^x + e^y$ subject to $x+y=1$, $x, y ge 0$. The minimum is at $(1/2,1/2)$ which is not a vertex.
The condition you want (for a minimization problem) is that the objective is a concave function.
answered Mar 14 at 21:19
Robert IsraelRobert Israel
329k23217470
$endgroup$
$begingroup$
Okay, so if we have a general concave objective function (not just linear), we can say that the optima must lie on one of the vertices of the simplex (assuming we have a bounded simplex)? And does this mean we can use the simplex method for such problems?
$endgroup$
– Rohit Pandey
Mar 14 at 21:22
$begingroup$
Yes and no. The reason there isn't a simplex method is basically that local information at one vertex (shadow prices etc) doesn't tell you what will happen at a neighbouring vertex.
$endgroup$
– Robert Israel
Mar 15 at 1:11
$begingroup$
In fact this kind of problem with a concave quadratic objective is known to be NP-complete, in contrast to linear programming which can be solved in polynomial time (though not by the simplex method).
$endgroup$
– Robert Israel
Mar 15 at 1:24
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%2f3148499%2fcan-the-simplex-method-be-used-for-general-monotonically-increasing-objective-fu%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$
No, we can't. Consider minimizing $e^x + e^y$ subject to $x+y=1$, $x, y ge 0$. The minimum is at $(1/2,1/2)$ which is not a vertex.
The condition you want (for a minimization problem) is that the objective is a concave function.
answered Mar 14 at 21:19
Robert IsraelRobert Israel
329k23217470
$endgroup$
$begingroup$
Okay, so if we have a general concave objective function (not just linear), we can say that the optima must lie on one of the vertices of the simplex (assuming we have a bounded simplex)? And does this mean we can use the simplex method for such problems?
$endgroup$
– Rohit Pandey
Mar 14 at 21:22
$begingroup$
Yes and no. The reason there isn't a simplex method is basically that local information at one vertex (shadow prices etc) doesn't tell you what will happen at a neighbouring vertex.
$endgroup$
– Robert Israel
Mar 15 at 1:11
$begingroup$
In fact this kind of problem with a concave quadratic objective is known to be NP-complete, in contrast to linear programming which can be solved in polynomial time (though not by the simplex method).
$endgroup$
– Robert Israel
Mar 15 at 1:24
add a comment |
$begingroup$
No, we can't. Consider minimizing $e^x + e^y$ subject to $x+y=1$, $x, y ge 0$. The minimum is at $(1/2,1/2)$ which is not a vertex.
The condition you want (for a minimization problem) is that the objective is a concave function.
answered Mar 14 at 21:19
Robert IsraelRobert Israel
329k23217470
$endgroup$
$begingroup$
Okay, so if we have a general concave objective function (not just linear), we can say that the optima must lie on one of the vertices of the simplex (assuming we have a bounded simplex)? And does this mean we can use the simplex method for such problems?
$endgroup$
– Rohit Pandey
Mar 14 at 21:22
$begingroup$
Yes and no. The reason there isn't a simplex method is basically that local information at one vertex (shadow prices etc) doesn't tell you what will happen at a neighbouring vertex.
$endgroup$
– Robert Israel
Mar 15 at 1:11
$begingroup$
In fact this kind of problem with a concave quadratic objective is known to be NP-complete, in contrast to linear programming which can be solved in polynomial time (though not by the simplex method).
$endgroup$
– Robert Israel
Mar 15 at 1:24
add a comment |
$begingroup$
No, we can't. Consider minimizing $e^x + e^y$ subject to $x+y=1$, $x, y ge 0$. The minimum is at $(1/2,1/2)$ which is not a vertex.
The condition you want (for a minimization problem) is that the objective is a concave function.
answered Mar 14 at 21:19
Robert IsraelRobert Israel
329k23217470
$endgroup$
No, we can't. Consider minimizing $e^x + e^y$ subject to $x+y=1$, $x, y ge 0$. The minimum is at $(1/2,1/2)$ which is not a vertex.
The condition you want (for a minimization problem) is that the objective is a concave function.
answered Mar 14 at 21:19
Robert IsraelRobert Israel
329k23217470
answered Mar 14 at 21:19
Robert IsraelRobert Israel
329k23217470
answered Mar 14 at 21:19
Robert IsraelRobert Israel
329k23217470
answered Mar 14 at 21:19
Robert IsraelRobert Israel
329k23217470
329k23217470
$begingroup$
Okay, so if we have a general concave objective function (not just linear), we can say that the optima must lie on one of the vertices of the simplex (assuming we have a bounded simplex)? And does this mean we can use the simplex method for such problems?
$endgroup$
– Rohit Pandey
Mar 14 at 21:22
$begingroup$
Yes and no. The reason there isn't a simplex method is basically that local information at one vertex (shadow prices etc) doesn't tell you what will happen at a neighbouring vertex.
$endgroup$
– Robert Israel
Mar 15 at 1:11
$begingroup$
In fact this kind of problem with a concave quadratic objective is known to be NP-complete, in contrast to linear programming which can be solved in polynomial time (though not by the simplex method).
$endgroup$
– Robert Israel
Mar 15 at 1:24
add a comment |
$begingroup$
Okay, so if we have a general concave objective function (not just linear), we can say that the optima must lie on one of the vertices of the simplex (assuming we have a bounded simplex)? And does this mean we can use the simplex method for such problems?
$endgroup$
– Rohit Pandey
Mar 14 at 21:22
$begingroup$
Yes and no. The reason there isn't a simplex method is basically that local information at one vertex (shadow prices etc) doesn't tell you what will happen at a neighbouring vertex.
$endgroup$
– Robert Israel
Mar 15 at 1:11
$begingroup$
In fact this kind of problem with a concave quadratic objective is known to be NP-complete, in contrast to linear programming which can be solved in polynomial time (though not by the simplex method).
$endgroup$
– Robert Israel
Mar 15 at 1:24
$begingroup$
Okay, so if we have a general concave objective function (not just linear), we can say that the optima must lie on one of the vertices of the simplex (assuming we have a bounded simplex)? And does this mean we can use the simplex method for such problems?
$endgroup$
– Rohit Pandey
Mar 14 at 21:22
$begingroup$
Okay, so if we have a general concave objective function (not just linear), we can say that the optima must lie on one of the vertices of the simplex (assuming we have a bounded simplex)? And does this mean we can use the simplex method for such problems?
$endgroup$
– Rohit Pandey
Mar 14 at 21:22
$begingroup$
Yes and no. The reason there isn't a simplex method is basically that local information at one vertex (shadow prices etc) doesn't tell you what will happen at a neighbouring vertex.
$endgroup$
– Robert Israel
Mar 15 at 1:11
$begingroup$
Yes and no. The reason there isn't a simplex method is basically that local information at one vertex (shadow prices etc) doesn't tell you what will happen at a neighbouring vertex.
$endgroup$
– Robert Israel
Mar 15 at 1:11
$begingroup$
In fact this kind of problem with a concave quadratic objective is known to be NP-complete, in contrast to linear programming which can be solved in polynomial time (though not by the simplex method).
$endgroup$
– Robert Israel
Mar 15 at 1:24
$begingroup$
In fact this kind of problem with a concave quadratic objective is known to be NP-complete, in contrast to linear programming which can be solved in polynomial time (though not by the simplex method).
$endgroup$
– Robert Israel
Mar 15 at 1:24
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%2f3148499%2fcan-the-simplex-method-be-used-for-general-monotonically-increasing-objective-fu%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
