Proving a projection based on Farkas Lemma
$begingroup$
In an Integer Programming book, a proof is given for a theorem but i do not understand a certain step:
Theorem: Consider a polyhedron $P := {(x,z) in R^n times R^p: Ax+Bzleq b}$ and let $r^1$,...,$r^q$ be the extreme rays of $C_p$: the cone of $P$. Then, $proj_x(P) = {x in R^n: r^tAx leq r^t forall t = 1,...,q}$
Proof: It suffices to show that for any $x$, $ x notin proj_x(P) $ if and only if $r^tAx>r^tb$ for some $t = 1,...,q$. By definition $ x notin proj_x(P) $ if and only if the system $Bz <b-Ax$ is infeasible.
I get it until here
Proof (cont):
By Farkas Lemma, the latter system is infeasible if and only if there exists a vector $u in C_p$ such that $uAx geq ub$
Here is where i am lost. How do they come to this based on Farkas Lemma?
Farkas lemma:
Given matrix $A$ and vector $b$, exactly one of the following statements is true:
$exists x$ such that $Ax=b$ and $x geq 0$
$exists y$ such that $y^TA geq 0^T$ and $y^Tb < 0$
Definition Cone:
The cone of $P={(x,z) in R^n times R^p: Ax +Bz leq b}$ is $C_P = {u in R^m: uB=0, u geq 0}$
polyhedra projection
asked Jan 18 at 21:49
user3053216user3053216
13111
$endgroup$
add a comment |
$begingroup$
In an Integer Programming book, a proof is given for a theorem but i do not understand a certain step:
Theorem: Consider a polyhedron $P := {(x,z) in R^n times R^p: Ax+Bzleq b}$ and let $r^1$,...,$r^q$ be the extreme rays of $C_p$: the cone of $P$. Then, $proj_x(P) = {x in R^n: r^tAx leq r^t forall t = 1,...,q}$
Proof: It suffices to show that for any $x$, $ x notin proj_x(P) $ if and only if $r^tAx>r^tb$ for some $t = 1,...,q$. By definition $ x notin proj_x(P) $ if and only if the system $Bz <b-Ax$ is infeasible.
I get it until here
Proof (cont):
By Farkas Lemma, the latter system is infeasible if and only if there exists a vector $u in C_p$ such that $uAx geq ub$
Here is where i am lost. How do they come to this based on Farkas Lemma?
Farkas lemma:
Given matrix $A$ and vector $b$, exactly one of the following statements is true:
$exists x$ such that $Ax=b$ and $x geq 0$
$exists y$ such that $y^TA geq 0^T$ and $y^Tb < 0$
Definition Cone:
The cone of $P={(x,z) in R^n times R^p: Ax +Bz leq b}$ is $C_P = {u in R^m: uB=0, u geq 0}$
polyhedra projection
asked Jan 18 at 21:49
user3053216user3053216
13111
$endgroup$
$begingroup$
Is this referring to the same question as math.stackexchange.com/questions/2968085/…? They look similar but the $R$'s are $R_+$'s and there is a $V$ instead of $C_p.$ What's the cone of $P$?
$endgroup$
– Dap
Jan 21 at 6:55
$begingroup$
@Dap It is based on theory I found while looking for an answer to that question. Not sure if it is 100% the same. Anyway, i added the definition of the cone.
$endgroup$
– user3053216
Jan 21 at 9:21
add a comment |
$begingroup$
In an Integer Programming book, a proof is given for a theorem but i do not understand a certain step:
Theorem: Consider a polyhedron $P := {(x,z) in R^n times R^p: Ax+Bzleq b}$ and let $r^1$,...,$r^q$ be the extreme rays of $C_p$: the cone of $P$. Then, $proj_x(P) = {x in R^n: r^tAx leq r^t forall t = 1,...,q}$
Proof: It suffices to show that for any $x$, $ x notin proj_x(P) $ if and only if $r^tAx>r^tb$ for some $t = 1,...,q$. By definition $ x notin proj_x(P) $ if and only if the system $Bz <b-Ax$ is infeasible.
I get it until here
Proof (cont):
By Farkas Lemma, the latter system is infeasible if and only if there exists a vector $u in C_p$ such that $uAx geq ub$
Here is where i am lost. How do they come to this based on Farkas Lemma?
Farkas lemma:
Given matrix $A$ and vector $b$, exactly one of the following statements is true:
$exists x$ such that $Ax=b$ and $x geq 0$
$exists y$ such that $y^TA geq 0^T$ and $y^Tb < 0$
Definition Cone:
The cone of $P={(x,z) in R^n times R^p: Ax +Bz leq b}$ is $C_P = {u in R^m: uB=0, u geq 0}$
polyhedra projection
asked Jan 18 at 21:49
user3053216user3053216
13111
$endgroup$
In an Integer Programming book, a proof is given for a theorem but i do not understand a certain step:
Theorem: Consider a polyhedron $P := {(x,z) in R^n times R^p: Ax+Bzleq b}$ and let $r^1$,...,$r^q$ be the extreme rays of $C_p$: the cone of $P$. Then, $proj_x(P) = {x in R^n: r^tAx leq r^t forall t = 1,...,q}$
Proof: It suffices to show that for any $x$, $ x notin proj_x(P) $ if and only if $r^tAx>r^tb$ for some $t = 1,...,q$. By definition $ x notin proj_x(P) $ if and only if the system $Bz <b-Ax$ is infeasible.
I get it until here
Proof (cont):
By Farkas Lemma, the latter system is infeasible if and only if there exists a vector $u in C_p$ such that $uAx geq ub$
Here is where i am lost. How do they come to this based on Farkas Lemma?
Farkas lemma:
Given matrix $A$ and vector $b$, exactly one of the following statements is true:
$exists x$ such that $Ax=b$ and $x geq 0$
$exists y$ such that $y^TA geq 0^T$ and $y^Tb < 0$
Definition Cone:
The cone of $P={(x,z) in R^n times R^p: Ax +Bz leq b}$ is $C_P = {u in R^m: uB=0, u geq 0}$
polyhedra projection
polyhedra projection
asked Jan 18 at 21:49
user3053216user3053216
13111
asked Jan 18 at 21:49
user3053216user3053216
13111
edited Jan 21 at 10:34
user3053216
asked Jan 18 at 21:49
user3053216user3053216
13111
asked Jan 18 at 21:49
user3053216user3053216
13111
asked Jan 18 at 21:49
user3053216user3053216
13111
13111
$begingroup$
Is this referring to the same question as math.stackexchange.com/questions/2968085/…? They look similar but the $R$'s are $R_+$'s and there is a $V$ instead of $C_p.$ What's the cone of $P$?
$endgroup$
– Dap
Jan 21 at 6:55
$begingroup$
@Dap It is based on theory I found while looking for an answer to that question. Not sure if it is 100% the same. Anyway, i added the definition of the cone.
$endgroup$
– user3053216
Jan 21 at 9:21
add a comment |
$begingroup$
Is this referring to the same question as math.stackexchange.com/questions/2968085/…? They look similar but the $R$'s are $R_+$'s and there is a $V$ instead of $C_p.$ What's the cone of $P$?
$endgroup$
– Dap
Jan 21 at 6:55
$begingroup$
@Dap It is based on theory I found while looking for an answer to that question. Not sure if it is 100% the same. Anyway, i added the definition of the cone.
$endgroup$
– user3053216
Jan 21 at 9:21
$begingroup$
Is this referring to the same question as math.stackexchange.com/questions/2968085/…? They look similar but the $R$'s are $R_+$'s and there is a $V$ instead of $C_p.$ What's the cone of $P$?
$endgroup$
– Dap
Jan 21 at 6:55
$begingroup$
Is this referring to the same question as math.stackexchange.com/questions/2968085/…? They look similar but the $R$'s are $R_+$'s and there is a $V$ instead of $C_p.$ What's the cone of $P$?
$endgroup$
– Dap
Jan 21 at 6:55
$begingroup$
@Dap It is based on theory I found while looking for an answer to that question. Not sure if it is 100% the same. Anyway, i added the definition of the cone.
$endgroup$
– user3053216
Jan 21 at 9:21
$begingroup$
@Dap It is based on theory I found while looking for an answer to that question. Not sure if it is 100% the same. Anyway, i added the definition of the cone.
$endgroup$
– user3053216
Jan 21 at 9:21
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$xnotinmathrm{proj}_x(P)$ if and only if the system $Bzleq b-Ax$ is infeasible.
The statement you want follows from one of the generalized forms of Farkas' lemma. In particular Theorem 3.6 in "Integer Programming" by Conforti et al says that exactly one of these holds:
$exists y$ such that $Byleq f$
$exists u$ such that $uf< 0$ and $uB=0,$ $ugeq 0$
Substituting in $z$ and $b-Ax$ for $y$ and $f$ gives what you want.
To prove the generalization from the basic version of Farkas' lemma, add slack variables $w$ to convert the system to an equality, and split $y$ into positive and negative parts:
$$exists y^+,y^-,wtext{ such that }By-By+w=ftext{ and }y^+,y^-,wgeq 0$$
or in block matrix form:
$$exists y^+,y^-,wtext{ such that }begin{pmatrix}B&-B&Iend{pmatrix}begin{pmatrix}y^+\y^-\wend{pmatrix}=ftext{ and }y,y',wgeq 0$$
By Farkas' lemma this system is infeasible if and only if:
$$exists utext{ such that }ubegin{pmatrix}B&-B&Iend{pmatrix}geq 0text{ and }uf<0$$
i.e.
$$exists utext{ such that }uB=0text{ and }ugeq 0text{ and }uf<0.$$
answered Jan 23 at 5:56
DapDap
20.2k842
$endgroup$
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%2f3078797%2fproving-a-projection-based-on-farkas-lemma%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$
$xnotinmathrm{proj}_x(P)$ if and only if the system $Bzleq b-Ax$ is infeasible.
The statement you want follows from one of the generalized forms of Farkas' lemma. In particular Theorem 3.6 in "Integer Programming" by Conforti et al says that exactly one of these holds:
$exists y$ such that $Byleq f$
$exists u$ such that $uf< 0$ and $uB=0,$ $ugeq 0$
Substituting in $z$ and $b-Ax$ for $y$ and $f$ gives what you want.
To prove the generalization from the basic version of Farkas' lemma, add slack variables $w$ to convert the system to an equality, and split $y$ into positive and negative parts:
$$exists y^+,y^-,wtext{ such that }By-By+w=ftext{ and }y^+,y^-,wgeq 0$$
or in block matrix form:
$$exists y^+,y^-,wtext{ such that }begin{pmatrix}B&-B&Iend{pmatrix}begin{pmatrix}y^+\y^-\wend{pmatrix}=ftext{ and }y,y',wgeq 0$$
By Farkas' lemma this system is infeasible if and only if:
$$exists utext{ such that }ubegin{pmatrix}B&-B&Iend{pmatrix}geq 0text{ and }uf<0$$
i.e.
$$exists utext{ such that }uB=0text{ and }ugeq 0text{ and }uf<0.$$
answered Jan 23 at 5:56
DapDap
20.2k842
$endgroup$
add a comment |
$begingroup$
$xnotinmathrm{proj}_x(P)$ if and only if the system $Bzleq b-Ax$ is infeasible.
The statement you want follows from one of the generalized forms of Farkas' lemma. In particular Theorem 3.6 in "Integer Programming" by Conforti et al says that exactly one of these holds:
$exists y$ such that $Byleq f$
$exists u$ such that $uf< 0$ and $uB=0,$ $ugeq 0$
Substituting in $z$ and $b-Ax$ for $y$ and $f$ gives what you want.
To prove the generalization from the basic version of Farkas' lemma, add slack variables $w$ to convert the system to an equality, and split $y$ into positive and negative parts:
$$exists y^+,y^-,wtext{ such that }By-By+w=ftext{ and }y^+,y^-,wgeq 0$$
or in block matrix form:
$$exists y^+,y^-,wtext{ such that }begin{pmatrix}B&-B&Iend{pmatrix}begin{pmatrix}y^+\y^-\wend{pmatrix}=ftext{ and }y,y',wgeq 0$$
By Farkas' lemma this system is infeasible if and only if:
$$exists utext{ such that }ubegin{pmatrix}B&-B&Iend{pmatrix}geq 0text{ and }uf<0$$
i.e.
$$exists utext{ such that }uB=0text{ and }ugeq 0text{ and }uf<0.$$
answered Jan 23 at 5:56
DapDap
20.2k842
$endgroup$
add a comment |
$begingroup$
$xnotinmathrm{proj}_x(P)$ if and only if the system $Bzleq b-Ax$ is infeasible.
The statement you want follows from one of the generalized forms of Farkas' lemma. In particular Theorem 3.6 in "Integer Programming" by Conforti et al says that exactly one of these holds:
$exists y$ such that $Byleq f$
$exists u$ such that $uf< 0$ and $uB=0,$ $ugeq 0$
Substituting in $z$ and $b-Ax$ for $y$ and $f$ gives what you want.
To prove the generalization from the basic version of Farkas' lemma, add slack variables $w$ to convert the system to an equality, and split $y$ into positive and negative parts:
$$exists y^+,y^-,wtext{ such that }By-By+w=ftext{ and }y^+,y^-,wgeq 0$$
or in block matrix form:
$$exists y^+,y^-,wtext{ such that }begin{pmatrix}B&-B&Iend{pmatrix}begin{pmatrix}y^+\y^-\wend{pmatrix}=ftext{ and }y,y',wgeq 0$$
By Farkas' lemma this system is infeasible if and only if:
$$exists utext{ such that }ubegin{pmatrix}B&-B&Iend{pmatrix}geq 0text{ and }uf<0$$
i.e.
$$exists utext{ such that }uB=0text{ and }ugeq 0text{ and }uf<0.$$
answered Jan 23 at 5:56
DapDap
20.2k842
$endgroup$
$xnotinmathrm{proj}_x(P)$ if and only if the system $Bzleq b-Ax$ is infeasible.
The statement you want follows from one of the generalized forms of Farkas' lemma. In particular Theorem 3.6 in "Integer Programming" by Conforti et al says that exactly one of these holds:
$exists y$ such that $Byleq f$
$exists u$ such that $uf< 0$ and $uB=0,$ $ugeq 0$
Substituting in $z$ and $b-Ax$ for $y$ and $f$ gives what you want.
To prove the generalization from the basic version of Farkas' lemma, add slack variables $w$ to convert the system to an equality, and split $y$ into positive and negative parts:
$$exists y^+,y^-,wtext{ such that }By-By+w=ftext{ and }y^+,y^-,wgeq 0$$
or in block matrix form:
$$exists y^+,y^-,wtext{ such that }begin{pmatrix}B&-B&Iend{pmatrix}begin{pmatrix}y^+\y^-\wend{pmatrix}=ftext{ and }y,y',wgeq 0$$
By Farkas' lemma this system is infeasible if and only if:
$$exists utext{ such that }ubegin{pmatrix}B&-B&Iend{pmatrix}geq 0text{ and }uf<0$$
i.e.
$$exists utext{ such that }uB=0text{ and }ugeq 0text{ and }uf<0.$$
answered Jan 23 at 5:56
DapDap
20.2k842
answered Jan 23 at 5:56
DapDap
20.2k842
answered Jan 23 at 5:56
DapDap
20.2k842
answered Jan 23 at 5:56
DapDap
20.2k842
20.2k842
add a comment |
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%2f3078797%2fproving-a-projection-based-on-farkas-lemma%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$
Is this referring to the same question as math.stackexchange.com/questions/2968085/…? They look similar but the $R$'s are $R_+$'s and there is a $V$ instead of $C_p.$ What's the cone of $P$?
$endgroup$
– Dap
Jan 21 at 6:55
$begingroup$
@Dap It is based on theory I found while looking for an answer to that question. Not sure if it is 100% the same. Anyway, i added the definition of the cone.
$endgroup$
– user3053216
Jan 21 at 9:21