Proving infeasibility using DualityQuestions about weak duality theoremStrong duality theorem written with iffs?linear programming infeasibility, dual & primal relationUtilizing theorems of duality to solve primal linear programming problemStrong duality optimal controlFeasibility and boundedness of non-linear programmingHow obtain the dual variables' value given a primal solutionFarkas Lemma using dualityMeasuring infeasibility in convex optimization, relations with dual problemdoes strong duality hold for minimum cost flow problem
What is required to make GPS signals available indoors?
Processor speed limited at 0.4 Ghz
Avoiding the "not like other girls" trope?
Does the Cone of Cold spell freeze water?
Bullying boss launched a smear campaign and made me unemployable
Am I breaking OOP practice with this architecture?
How to stretch the corners of this image so that it looks like a perfect rectangle?
Why do I get negative height?
Fair gambler's ruin problem intuition
What do you call someone who asks many questions?
Does the Idaho Potato Commission associate potato skins with healthy eating?
How seriously should I take size and weight limits of hand luggage?
Can compressed videos be decoded back to their uncompresed original format?
What are the G forces leaving Earth orbit?
Ambiguity in the definition of entropy
Finding the error in an argument
Where would I need my direct neural interface to be implanted?
Is this answer explanation correct?
Could the museum Saturn V's be refitted for one more flight?
What is the most common color to indicate the input-field is disabled?
What historical events would have to change in order to make 19th century "steampunk" technology possible?
Finitely generated matrix groups whose eigenvalues are all algebraic
Can someone clarify Hamming's notion of important problems in relation to modern academia?
Car headlights in a world without electricity
Proving infeasibility using Duality
Questions about weak duality theoremStrong duality theorem written with iffs?linear programming infeasibility, dual & primal relationUtilizing theorems of duality to solve primal linear programming problemStrong duality optimal controlFeasibility and boundedness of non-linear programmingHow obtain the dual variables' value given a primal solutionFarkas Lemma using dualityMeasuring infeasibility in convex optimization, relations with dual problemdoes strong duality hold for minimum cost flow problem
$begingroup$
suppose we have the linear program min$c^Tx: Ax leq 0, x leq 0$ and its corresponding dual
max$0^Tx: A^Ty geq 0, y leq 0$. How can we show that the Dual is infeasible? I started by contradiction and assumed the Dual is feasible, then its optimal value will be $0$ and by strong duality, the primal should also have an optimal value of $0$, however I am not able to reach a contradiction from this point.
linear-algebra linear-programming duality-theorems
asked Mar 20 at 19:58
SkrrrrrttttSkrrrrrtttt
387110
$endgroup$
add a comment |
$begingroup$
suppose we have the linear program min$c^Tx: Ax leq 0, x leq 0$ and its corresponding dual
max$0^Tx: A^Ty geq 0, y leq 0$. How can we show that the Dual is infeasible? I started by contradiction and assumed the Dual is feasible, then its optimal value will be $0$ and by strong duality, the primal should also have an optimal value of $0$, however I am not able to reach a contradiction from this point.
linear-algebra linear-programming duality-theorems
asked Mar 20 at 19:58
SkrrrrrttttSkrrrrrtttt
387110
$endgroup$
add a comment |
$begingroup$
suppose we have the linear program min$c^Tx: Ax leq 0, x leq 0$ and its corresponding dual
max$0^Tx: A^Ty geq 0, y leq 0$. How can we show that the Dual is infeasible? I started by contradiction and assumed the Dual is feasible, then its optimal value will be $0$ and by strong duality, the primal should also have an optimal value of $0$, however I am not able to reach a contradiction from this point.
linear-algebra linear-programming duality-theorems
asked Mar 20 at 19:58
SkrrrrrttttSkrrrrrtttt
387110
$endgroup$
suppose we have the linear program min$c^Tx: Ax leq 0, x leq 0$ and its corresponding dual
max$0^Tx: A^Ty geq 0, y leq 0$. How can we show that the Dual is infeasible? I started by contradiction and assumed the Dual is feasible, then its optimal value will be $0$ and by strong duality, the primal should also have an optimal value of $0$, however I am not able to reach a contradiction from this point.
linear-algebra linear-programming duality-theorems
linear-algebra linear-programming duality-theorems
asked Mar 20 at 19:58
SkrrrrrttttSkrrrrrtttt
387110
asked Mar 20 at 19:58
SkrrrrrttttSkrrrrrtttt
387110
asked Mar 20 at 19:58
SkrrrrrttttSkrrrrrtttt
387110
asked Mar 20 at 19:58
SkrrrrrttttSkrrrrrtttt
387110
asked Mar 20 at 19:58
SkrrrrrttttSkrrrrrtttt
387110
387110
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint
The dual for this problem is $$max g(lambda_1,lambda_2)\texts. t.\lambda_1,lambda_2succeq 0$$where $$g(lambda_1,lambda_2)=inf_xc^Tx+lambda_1^TAx+lambda_2^Tx\=inf_x(c+A^Tlambda_1+lambda_2)^Tx$$Now, when is the dual problem infeasible? How is it applied here?
answered Mar 20 at 20:26
Mostafa AyazMostafa Ayaz
18.2k31040
$endgroup$
$begingroup$
I am not familiar with this way of applying duality
$endgroup$
– Skrrrrrtttt
Mar 20 at 20:34
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%2f3155941%2fproving-infeasibility-using-duality%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$
Hint
The dual for this problem is $$max g(lambda_1,lambda_2)\texts. t.\lambda_1,lambda_2succeq 0$$where $$g(lambda_1,lambda_2)=inf_xc^Tx+lambda_1^TAx+lambda_2^Tx\=inf_x(c+A^Tlambda_1+lambda_2)^Tx$$Now, when is the dual problem infeasible? How is it applied here?
answered Mar 20 at 20:26
Mostafa AyazMostafa Ayaz
18.2k31040
$endgroup$
$begingroup$
I am not familiar with this way of applying duality
$endgroup$
– Skrrrrrtttt
Mar 20 at 20:34
add a comment |
$begingroup$
Hint
The dual for this problem is $$max g(lambda_1,lambda_2)\texts. t.\lambda_1,lambda_2succeq 0$$where $$g(lambda_1,lambda_2)=inf_xc^Tx+lambda_1^TAx+lambda_2^Tx\=inf_x(c+A^Tlambda_1+lambda_2)^Tx$$Now, when is the dual problem infeasible? How is it applied here?
answered Mar 20 at 20:26
Mostafa AyazMostafa Ayaz
18.2k31040
$endgroup$
$begingroup$
I am not familiar with this way of applying duality
$endgroup$
– Skrrrrrtttt
Mar 20 at 20:34
add a comment |
$begingroup$
Hint
The dual for this problem is $$max g(lambda_1,lambda_2)\texts. t.\lambda_1,lambda_2succeq 0$$where $$g(lambda_1,lambda_2)=inf_xc^Tx+lambda_1^TAx+lambda_2^Tx\=inf_x(c+A^Tlambda_1+lambda_2)^Tx$$Now, when is the dual problem infeasible? How is it applied here?
answered Mar 20 at 20:26
Mostafa AyazMostafa Ayaz
18.2k31040
$endgroup$
Hint
The dual for this problem is $$max g(lambda_1,lambda_2)\texts. t.\lambda_1,lambda_2succeq 0$$where $$g(lambda_1,lambda_2)=inf_xc^Tx+lambda_1^TAx+lambda_2^Tx\=inf_x(c+A^Tlambda_1+lambda_2)^Tx$$Now, when is the dual problem infeasible? How is it applied here?
answered Mar 20 at 20:26
Mostafa AyazMostafa Ayaz
18.2k31040
answered Mar 20 at 20:26
Mostafa AyazMostafa Ayaz
18.2k31040
answered Mar 20 at 20:26
Mostafa AyazMostafa Ayaz
18.2k31040
answered Mar 20 at 20:26
Mostafa AyazMostafa Ayaz
18.2k31040
18.2k31040
$begingroup$
I am not familiar with this way of applying duality
$endgroup$
– Skrrrrrtttt
Mar 20 at 20:34
add a comment |
$begingroup$
I am not familiar with this way of applying duality
$endgroup$
– Skrrrrrtttt
Mar 20 at 20:34
$begingroup$
I am not familiar with this way of applying duality
$endgroup$
– Skrrrrrtttt
Mar 20 at 20:34
$begingroup$
I am not familiar with this way of applying duality
$endgroup$
– Skrrrrrtttt
Mar 20 at 20:34
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%2f3155941%2fproving-infeasibility-using-duality%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
