Mixing
in linear programming, why does the dual have constraints?
$begingroup$
in introduction to linear optimization ($text{p. 142}$), they take the standard form problem:
minimize $c'x$, s.t. $Ax = b$, $xgeq 0$
they relax the constraints and define:
$g(p) = min_{xgeq 0}[c'x + p'(b-Ax)] = p'b + min_{xgeq 0}[(c - p'A)x]$
and then they try to maximize it, with respect to p.
now they note that when $c-p'A<0$ then $min_{xgeq 0}[(c - p'A)x]=-infty$, so to refrain from these p values they phrase the dual problem as:
maximize $p'b$, s.t. $p'Aleq c'$
my question: why is it necessary to put the constraints? why do we care that $min_{xgeq 0}[(c - p'A)x] = -infty$ for some values of p? why can't we just maximize $p'b$, and obviously we won't get the maximum for these $-infty$ p values?
linear-programming duality-theorems
edited Feb 3 at 1:30
LinAlg
10.1k1521
asked Feb 2 at 12:04
ihadannyihadanny
1307
$endgroup$
add a comment |
$begingroup$
in introduction to linear optimization ($text{p. 142}$), they take the standard form problem:
minimize $c'x$, s.t. $Ax = b$, $xgeq 0$
they relax the constraints and define:
$g(p) = min_{xgeq 0}[c'x + p'(b-Ax)] = p'b + min_{xgeq 0}[(c - p'A)x]$
and then they try to maximize it, with respect to p.
now they note that when $c-p'A<0$ then $min_{xgeq 0}[(c - p'A)x]=-infty$, so to refrain from these p values they phrase the dual problem as:
maximize $p'b$, s.t. $p'Aleq c'$
my question: why is it necessary to put the constraints? why do we care that $min_{xgeq 0}[(c - p'A)x] = -infty$ for some values of p? why can't we just maximize $p'b$, and obviously we won't get the maximum for these $-infty$ p values?
linear-programming duality-theorems
edited Feb 3 at 1:30
LinAlg
10.1k1521
asked Feb 2 at 12:04
ihadannyihadanny
1307
$endgroup$
$begingroup$
So you’re proposing that the dual problem is just $max p’b$ with no constraints?
$endgroup$
– David M.
Feb 2 at 18:56
$begingroup$
@david - yes. I know that this is wrong, but I don't understand why
$endgroup$
– ihadanny
Feb 2 at 22:26
1
$begingroup$
The dual function is not the linear function $g(p)=p’b$, it’s $g(p)=begin{cases}p’b,&p’Aleq{c},\-infty,&text{else}.end{cases}$. Easier to optimize the linear function over a polyhedron, than to optimize the non-linear function over all of $mathbb{R}^m$.
$endgroup$
– David M.
Feb 3 at 15:30
add a comment |
$begingroup$
in introduction to linear optimization ($text{p. 142}$), they take the standard form problem:
minimize $c'x$, s.t. $Ax = b$, $xgeq 0$
they relax the constraints and define:
$g(p) = min_{xgeq 0}[c'x + p'(b-Ax)] = p'b + min_{xgeq 0}[(c - p'A)x]$
and then they try to maximize it, with respect to p.
now they note that when $c-p'A<0$ then $min_{xgeq 0}[(c - p'A)x]=-infty$, so to refrain from these p values they phrase the dual problem as:
maximize $p'b$, s.t. $p'Aleq c'$
my question: why is it necessary to put the constraints? why do we care that $min_{xgeq 0}[(c - p'A)x] = -infty$ for some values of p? why can't we just maximize $p'b$, and obviously we won't get the maximum for these $-infty$ p values?
linear-programming duality-theorems
edited Feb 3 at 1:30
LinAlg
10.1k1521
asked Feb 2 at 12:04
ihadannyihadanny
1307
$endgroup$
in introduction to linear optimization ($text{p. 142}$), they take the standard form problem:
minimize $c'x$, s.t. $Ax = b$, $xgeq 0$
they relax the constraints and define:
$g(p) = min_{xgeq 0}[c'x + p'(b-Ax)] = p'b + min_{xgeq 0}[(c - p'A)x]$
and then they try to maximize it, with respect to p.
now they note that when $c-p'A<0$ then $min_{xgeq 0}[(c - p'A)x]=-infty$, so to refrain from these p values they phrase the dual problem as:
maximize $p'b$, s.t. $p'Aleq c'$
my question: why is it necessary to put the constraints? why do we care that $min_{xgeq 0}[(c - p'A)x] = -infty$ for some values of p? why can't we just maximize $p'b$, and obviously we won't get the maximum for these $-infty$ p values?
linear-programming duality-theorems
linear-programming duality-theorems
edited Feb 3 at 1:30
LinAlg
10.1k1521
asked Feb 2 at 12:04
ihadannyihadanny
1307
edited Feb 3 at 1:30
LinAlg
10.1k1521
asked Feb 2 at 12:04
ihadannyihadanny
1307
edited Feb 3 at 1:30
LinAlg
10.1k1521
edited Feb 3 at 1:30
LinAlg
10.1k1521
edited Feb 3 at 1:30
LinAlg
10.1k1521
10.1k1521
asked Feb 2 at 12:04
ihadannyihadanny
1307
asked Feb 2 at 12:04
ihadannyihadanny
1307
asked Feb 2 at 12:04
ihadannyihadanny
1307
1307
$begingroup$
So you’re proposing that the dual problem is just $max p’b$ with no constraints?
$endgroup$
– David M.
Feb 2 at 18:56
$begingroup$
@david - yes. I know that this is wrong, but I don't understand why
$endgroup$
– ihadanny
Feb 2 at 22:26
1
$begingroup$
The dual function is not the linear function $g(p)=p’b$, it’s $g(p)=begin{cases}p’b,&p’Aleq{c},\-infty,&text{else}.end{cases}$. Easier to optimize the linear function over a polyhedron, than to optimize the non-linear function over all of $mathbb{R}^m$.
$endgroup$
– David M.
Feb 3 at 15:30
add a comment |
$begingroup$
So you’re proposing that the dual problem is just $max p’b$ with no constraints?
$endgroup$
– David M.
Feb 2 at 18:56
$begingroup$
@david - yes. I know that this is wrong, but I don't understand why
$endgroup$
– ihadanny
Feb 2 at 22:26
1
$begingroup$
The dual function is not the linear function $g(p)=p’b$, it’s $g(p)=begin{cases}p’b,&p’Aleq{c},\-infty,&text{else}.end{cases}$. Easier to optimize the linear function over a polyhedron, than to optimize the non-linear function over all of $mathbb{R}^m$.
$endgroup$
– David M.
Feb 3 at 15:30
$begingroup$
So you’re proposing that the dual problem is just $max p’b$ with no constraints?
$endgroup$
– David M.
Feb 2 at 18:56
$begingroup$
So you’re proposing that the dual problem is just $max p’b$ with no constraints?
$endgroup$
– David M.
Feb 2 at 18:56
$begingroup$
@david - yes. I know that this is wrong, but I don't understand why
$endgroup$
– ihadanny
Feb 2 at 22:26
$begingroup$
@david - yes. I know that this is wrong, but I don't understand why
$endgroup$
– ihadanny
Feb 2 at 22:26
1
1
$begingroup$
The dual function is not the linear function $g(p)=p’b$, it’s $g(p)=begin{cases}p’b,&p’Aleq{c},\-infty,&text{else}.end{cases}$. Easier to optimize the linear function over a polyhedron, than to optimize the non-linear function over all of $mathbb{R}^m$.
$endgroup$
– David M.
Feb 3 at 15:30
$begingroup$
The dual function is not the linear function $g(p)=p’b$, it’s $g(p)=begin{cases}p’b,&p’Aleq{c},\-infty,&text{else}.end{cases}$. Easier to optimize the linear function over a polyhedron, than to optimize the non-linear function over all of $mathbb{R}^m$.
$endgroup$
– David M.
Feb 3 at 15:30
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It is not necessary to formulate them as constraints, you can just write the dual problem as:
$max_p p'b + min_{xgeq 0}[(c - p'A)x]$.
However, solving a nested problem is difficult. The maximum cannot occur when $A^T p > c$, so you can restrict your search for a maximizer to the set where $A^T p leq c$. If you define $S = { p : A^T p leq c }$ you seem to propose solving $max_{p in S} p'b$. That is a correct statement of the dual problem.
We still prefer the equivalent formulation $max_{p in mathbb{R}^m} { p'b : A^Tpleq c}$, since it is a linear optimization problem.
answered Feb 3 at 1:51
LinAlgLinAlg
10.1k1521
$endgroup$
$begingroup$
thanks, but I'm missing the point: you're just showing an alternative formulation for the same problem. I'm asking why is it necessary to restrict the search to the set $S$, why can't we just search all over, and take for granted that the maximum won't be outside of S.
$endgroup$
– ihadanny
Feb 3 at 9:59
$begingroup$
@ihadanny it is not necessary at all, like I say in my first sentence you can write the dual problem as one that still has $min_{xgeq 0}$.
$endgroup$
– LinAlg
Feb 3 at 13:22
add a comment |
Your Answer
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%2f3097226%2fin-linear-programming-why-does-the-dual-have-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$
It is not necessary to formulate them as constraints, you can just write the dual problem as:
$max_p p'b + min_{xgeq 0}[(c - p'A)x]$.
However, solving a nested problem is difficult. The maximum cannot occur when $A^T p > c$, so you can restrict your search for a maximizer to the set where $A^T p leq c$. If you define $S = { p : A^T p leq c }$ you seem to propose solving $max_{p in S} p'b$. That is a correct statement of the dual problem.
We still prefer the equivalent formulation $max_{p in mathbb{R}^m} { p'b : A^Tpleq c}$, since it is a linear optimization problem.
answered Feb 3 at 1:51
LinAlgLinAlg
10.1k1521
$endgroup$
$begingroup$
thanks, but I'm missing the point: you're just showing an alternative formulation for the same problem. I'm asking why is it necessary to restrict the search to the set $S$, why can't we just search all over, and take for granted that the maximum won't be outside of S.
$endgroup$
– ihadanny
Feb 3 at 9:59
$begingroup$
@ihadanny it is not necessary at all, like I say in my first sentence you can write the dual problem as one that still has $min_{xgeq 0}$.
$endgroup$
– LinAlg
Feb 3 at 13:22
add a comment |
$begingroup$
It is not necessary to formulate them as constraints, you can just write the dual problem as:
$max_p p'b + min_{xgeq 0}[(c - p'A)x]$.
However, solving a nested problem is difficult. The maximum cannot occur when $A^T p > c$, so you can restrict your search for a maximizer to the set where $A^T p leq c$. If you define $S = { p : A^T p leq c }$ you seem to propose solving $max_{p in S} p'b$. That is a correct statement of the dual problem.
We still prefer the equivalent formulation $max_{p in mathbb{R}^m} { p'b : A^Tpleq c}$, since it is a linear optimization problem.
answered Feb 3 at 1:51
LinAlgLinAlg
10.1k1521
$endgroup$
$begingroup$
thanks, but I'm missing the point: you're just showing an alternative formulation for the same problem. I'm asking why is it necessary to restrict the search to the set $S$, why can't we just search all over, and take for granted that the maximum won't be outside of S.
$endgroup$
– ihadanny
Feb 3 at 9:59
$begingroup$
@ihadanny it is not necessary at all, like I say in my first sentence you can write the dual problem as one that still has $min_{xgeq 0}$.
$endgroup$
– LinAlg
Feb 3 at 13:22
add a comment |
$begingroup$
It is not necessary to formulate them as constraints, you can just write the dual problem as:
$max_p p'b + min_{xgeq 0}[(c - p'A)x]$.
However, solving a nested problem is difficult. The maximum cannot occur when $A^T p > c$, so you can restrict your search for a maximizer to the set where $A^T p leq c$. If you define $S = { p : A^T p leq c }$ you seem to propose solving $max_{p in S} p'b$. That is a correct statement of the dual problem.
We still prefer the equivalent formulation $max_{p in mathbb{R}^m} { p'b : A^Tpleq c}$, since it is a linear optimization problem.
answered Feb 3 at 1:51
LinAlgLinAlg
10.1k1521
$endgroup$
It is not necessary to formulate them as constraints, you can just write the dual problem as:
$max_p p'b + min_{xgeq 0}[(c - p'A)x]$.
However, solving a nested problem is difficult. The maximum cannot occur when $A^T p > c$, so you can restrict your search for a maximizer to the set where $A^T p leq c$. If you define $S = { p : A^T p leq c }$ you seem to propose solving $max_{p in S} p'b$. That is a correct statement of the dual problem.
We still prefer the equivalent formulation $max_{p in mathbb{R}^m} { p'b : A^Tpleq c}$, since it is a linear optimization problem.
answered Feb 3 at 1:51
LinAlgLinAlg
10.1k1521
answered Feb 3 at 1:51
LinAlgLinAlg
10.1k1521
answered Feb 3 at 1:51
LinAlgLinAlg
10.1k1521
answered Feb 3 at 1:51
LinAlgLinAlg
10.1k1521
10.1k1521
$begingroup$
thanks, but I'm missing the point: you're just showing an alternative formulation for the same problem. I'm asking why is it necessary to restrict the search to the set $S$, why can't we just search all over, and take for granted that the maximum won't be outside of S.
$endgroup$
– ihadanny
Feb 3 at 9:59
$begingroup$
@ihadanny it is not necessary at all, like I say in my first sentence you can write the dual problem as one that still has $min_{xgeq 0}$.
$endgroup$
– LinAlg
Feb 3 at 13:22
add a comment |
$begingroup$
thanks, but I'm missing the point: you're just showing an alternative formulation for the same problem. I'm asking why is it necessary to restrict the search to the set $S$, why can't we just search all over, and take for granted that the maximum won't be outside of S.
$endgroup$
– ihadanny
Feb 3 at 9:59
$begingroup$
@ihadanny it is not necessary at all, like I say in my first sentence you can write the dual problem as one that still has $min_{xgeq 0}$.
$endgroup$
– LinAlg
Feb 3 at 13:22
$begingroup$
thanks, but I'm missing the point: you're just showing an alternative formulation for the same problem. I'm asking why is it necessary to restrict the search to the set $S$, why can't we just search all over, and take for granted that the maximum won't be outside of S.
$endgroup$
– ihadanny
Feb 3 at 9:59
$begingroup$
thanks, but I'm missing the point: you're just showing an alternative formulation for the same problem. I'm asking why is it necessary to restrict the search to the set $S$, why can't we just search all over, and take for granted that the maximum won't be outside of S.
$endgroup$
– ihadanny
Feb 3 at 9:59
$begingroup$
@ihadanny it is not necessary at all, like I say in my first sentence you can write the dual problem as one that still has $min_{xgeq 0}$.
$endgroup$
– LinAlg
Feb 3 at 13:22
$begingroup$
@ihadanny it is not necessary at all, like I say in my first sentence you can write the dual problem as one that still has $min_{xgeq 0}$.
$endgroup$
– LinAlg
Feb 3 at 13:22
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%2f3097226%2fin-linear-programming-why-does-the-dual-have-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$
So you’re proposing that the dual problem is just $max p’b$ with no constraints?
$endgroup$
– David M.
Feb 2 at 18:56
$begingroup$
@david - yes. I know that this is wrong, but I don't understand why
$endgroup$
– ihadanny
Feb 2 at 22:26
1
$begingroup$
The dual function is not the linear function $g(p)=p’b$, it’s $g(p)=begin{cases}p’b,&p’Aleq{c},\-infty,&text{else}.end{cases}$. Easier to optimize the linear function over a polyhedron, than to optimize the non-linear function over all of $mathbb{R}^m$.
$endgroup$
– David M.
Feb 3 at 15:30