the reason behind dual the inner problem in robust optimization
$begingroup$
I have reading some material about Robust optimization.
It seems that dual optimization theory is the main techniques to reformulate robust optimization.
for example:
$$min_xqquad c^Tx$$
$$s.tqquad a^Txleq b$$
where$$qquad ain {a|Daleq d} $$
and the problem is equivalent
$$min_xqquad c^Tx$$
$$s.tqquad max_{Daleq d}a^Txleq b$$
and they use dual theory reformulate the max problem to min problem
which is
$$min_xqquad c^Tx$$
$$s.tqquad min_{D^Tp=x,pgeq0}p^Tdleq b$$
and finally it equivalent to $$min_{x,p}qquad c^Tx$$
$s.t$
$$p^Tdleq b$$
$$D^Tp=x$$
$$pgeq0$$
My question is
1.why we use dual theory to reformulate the inner problem?
2.why we can omit the second minimize in constraints?
optimization convex-optimization
asked Dec 18 '18 at 17:03
Vergil ChanVergil Chan
354
$endgroup$
add a comment |
$begingroup$
I have reading some material about Robust optimization.
It seems that dual optimization theory is the main techniques to reformulate robust optimization.
for example:
$$min_xqquad c^Tx$$
$$s.tqquad a^Txleq b$$
where$$qquad ain {a|Daleq d} $$
and the problem is equivalent
$$min_xqquad c^Tx$$
$$s.tqquad max_{Daleq d}a^Txleq b$$
and they use dual theory reformulate the max problem to min problem
which is
$$min_xqquad c^Tx$$
$$s.tqquad min_{D^Tp=x,pgeq0}p^Tdleq b$$
and finally it equivalent to $$min_{x,p}qquad c^Tx$$
$s.t$
$$p^Tdleq b$$
$$D^Tp=x$$
$$pgeq0$$
My question is
1.why we use dual theory to reformulate the inner problem?
2.why we can omit the second minimize in constraints?
optimization convex-optimization
asked Dec 18 '18 at 17:03
Vergil ChanVergil Chan
354
$endgroup$
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Jan 5 at 16:12
add a comment |
$begingroup$
I have reading some material about Robust optimization.
It seems that dual optimization theory is the main techniques to reformulate robust optimization.
for example:
$$min_xqquad c^Tx$$
$$s.tqquad a^Txleq b$$
where$$qquad ain {a|Daleq d} $$
and the problem is equivalent
$$min_xqquad c^Tx$$
$$s.tqquad max_{Daleq d}a^Txleq b$$
and they use dual theory reformulate the max problem to min problem
which is
$$min_xqquad c^Tx$$
$$s.tqquad min_{D^Tp=x,pgeq0}p^Tdleq b$$
and finally it equivalent to $$min_{x,p}qquad c^Tx$$
$s.t$
$$p^Tdleq b$$
$$D^Tp=x$$
$$pgeq0$$
My question is
1.why we use dual theory to reformulate the inner problem?
2.why we can omit the second minimize in constraints?
optimization convex-optimization
asked Dec 18 '18 at 17:03
Vergil ChanVergil Chan
354
$endgroup$
I have reading some material about Robust optimization.
It seems that dual optimization theory is the main techniques to reformulate robust optimization.
for example:
$$min_xqquad c^Tx$$
$$s.tqquad a^Txleq b$$
where$$qquad ain {a|Daleq d} $$
and the problem is equivalent
$$min_xqquad c^Tx$$
$$s.tqquad max_{Daleq d}a^Txleq b$$
and they use dual theory reformulate the max problem to min problem
which is
$$min_xqquad c^Tx$$
$$s.tqquad min_{D^Tp=x,pgeq0}p^Tdleq b$$
and finally it equivalent to $$min_{x,p}qquad c^Tx$$
$s.t$
$$p^Tdleq b$$
$$D^Tp=x$$
$$pgeq0$$
My question is
1.why we use dual theory to reformulate the inner problem?
2.why we can omit the second minimize in constraints?
optimization convex-optimization
optimization convex-optimization
asked Dec 18 '18 at 17:03
Vergil ChanVergil Chan
354
asked Dec 18 '18 at 17:03
Vergil ChanVergil Chan
354
asked Dec 18 '18 at 17:03
Vergil ChanVergil Chan
354
asked Dec 18 '18 at 17:03
Vergil ChanVergil Chan
354
asked Dec 18 '18 at 17:03
Vergil ChanVergil Chan
354
354
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Jan 5 at 16:12
add a comment |
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Jan 5 at 16:12
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Jan 5 at 16:12
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Jan 5 at 16:12
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
We use duality theory because we can do 'step 2'. It is a technique to turn a problem with uncountable many constraints into something manageable.
If you can find one $p geq 0$ for which $D^Tp = x$ and $p^T d leq b$, that is already sufficient to conclude that the minimum over $pgeq 0$ for which $D^Tp=x$ is less than or equal to $b$.
answered Dec 18 '18 at 17:42
LinAlgLinAlg
10.1k1521
$endgroup$
$begingroup$
thanks for your reply,but I still have confusion here. 1.as you mentioned,I know the problem have infinite constraints,but I don't know what happen to those infinite constraints, when we dualize the inner problem,can you give me some detail illustrated?
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:14
$begingroup$
and for the question 2,why is already sufficient to conclude..... is that any theorem or prove to illustrate this thing? i.e KKT condition or something ele? thank you!
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:20
$begingroup$
@VergilChan the infinite constraints went into a modest number of constraints. It is clear that the final formulation is just a regular linear optimization problem. It is sufficient to conclude from the definition of the minimum: the minimum of a set is not larger than any element of a set.
$endgroup$
– LinAlg
Dec 19 '18 at 14:45
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%2f3045407%2fthe-reason-behind-dual-the-inner-problem-in-robust-optimization%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$
We use duality theory because we can do 'step 2'. It is a technique to turn a problem with uncountable many constraints into something manageable.
If you can find one $p geq 0$ for which $D^Tp = x$ and $p^T d leq b$, that is already sufficient to conclude that the minimum over $pgeq 0$ for which $D^Tp=x$ is less than or equal to $b$.
answered Dec 18 '18 at 17:42
LinAlgLinAlg
10.1k1521
$endgroup$
$begingroup$
thanks for your reply,but I still have confusion here. 1.as you mentioned,I know the problem have infinite constraints,but I don't know what happen to those infinite constraints, when we dualize the inner problem,can you give me some detail illustrated?
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:14
$begingroup$
and for the question 2,why is already sufficient to conclude..... is that any theorem or prove to illustrate this thing? i.e KKT condition or something ele? thank you!
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:20
$begingroup$
@VergilChan the infinite constraints went into a modest number of constraints. It is clear that the final formulation is just a regular linear optimization problem. It is sufficient to conclude from the definition of the minimum: the minimum of a set is not larger than any element of a set.
$endgroup$
– LinAlg
Dec 19 '18 at 14:45
add a comment |
$begingroup$
We use duality theory because we can do 'step 2'. It is a technique to turn a problem with uncountable many constraints into something manageable.
If you can find one $p geq 0$ for which $D^Tp = x$ and $p^T d leq b$, that is already sufficient to conclude that the minimum over $pgeq 0$ for which $D^Tp=x$ is less than or equal to $b$.
answered Dec 18 '18 at 17:42
LinAlgLinAlg
10.1k1521
$endgroup$
$begingroup$
thanks for your reply,but I still have confusion here. 1.as you mentioned,I know the problem have infinite constraints,but I don't know what happen to those infinite constraints, when we dualize the inner problem,can you give me some detail illustrated?
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:14
$begingroup$
and for the question 2,why is already sufficient to conclude..... is that any theorem or prove to illustrate this thing? i.e KKT condition or something ele? thank you!
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:20
$begingroup$
@VergilChan the infinite constraints went into a modest number of constraints. It is clear that the final formulation is just a regular linear optimization problem. It is sufficient to conclude from the definition of the minimum: the minimum of a set is not larger than any element of a set.
$endgroup$
– LinAlg
Dec 19 '18 at 14:45
add a comment |
$begingroup$
We use duality theory because we can do 'step 2'. It is a technique to turn a problem with uncountable many constraints into something manageable.
If you can find one $p geq 0$ for which $D^Tp = x$ and $p^T d leq b$, that is already sufficient to conclude that the minimum over $pgeq 0$ for which $D^Tp=x$ is less than or equal to $b$.
answered Dec 18 '18 at 17:42
LinAlgLinAlg
10.1k1521
$endgroup$
We use duality theory because we can do 'step 2'. It is a technique to turn a problem with uncountable many constraints into something manageable.
If you can find one $p geq 0$ for which $D^Tp = x$ and $p^T d leq b$, that is already sufficient to conclude that the minimum over $pgeq 0$ for which $D^Tp=x$ is less than or equal to $b$.
answered Dec 18 '18 at 17:42
LinAlgLinAlg
10.1k1521
answered Dec 18 '18 at 17:42
LinAlgLinAlg
10.1k1521
answered Dec 18 '18 at 17:42
LinAlgLinAlg
10.1k1521
answered Dec 18 '18 at 17:42
LinAlgLinAlg
10.1k1521
10.1k1521
$begingroup$
thanks for your reply,but I still have confusion here. 1.as you mentioned,I know the problem have infinite constraints,but I don't know what happen to those infinite constraints, when we dualize the inner problem,can you give me some detail illustrated?
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:14
$begingroup$
and for the question 2,why is already sufficient to conclude..... is that any theorem or prove to illustrate this thing? i.e KKT condition or something ele? thank you!
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:20
$begingroup$
@VergilChan the infinite constraints went into a modest number of constraints. It is clear that the final formulation is just a regular linear optimization problem. It is sufficient to conclude from the definition of the minimum: the minimum of a set is not larger than any element of a set.
$endgroup$
– LinAlg
Dec 19 '18 at 14:45
add a comment |
$begingroup$
thanks for your reply,but I still have confusion here. 1.as you mentioned,I know the problem have infinite constraints,but I don't know what happen to those infinite constraints, when we dualize the inner problem,can you give me some detail illustrated?
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:14
$begingroup$
and for the question 2,why is already sufficient to conclude..... is that any theorem or prove to illustrate this thing? i.e KKT condition or something ele? thank you!
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:20
$begingroup$
@VergilChan the infinite constraints went into a modest number of constraints. It is clear that the final formulation is just a regular linear optimization problem. It is sufficient to conclude from the definition of the minimum: the minimum of a set is not larger than any element of a set.
$endgroup$
– LinAlg
Dec 19 '18 at 14:45
$begingroup$
thanks for your reply,but I still have confusion here. 1.as you mentioned,I know the problem have infinite constraints,but I don't know what happen to those infinite constraints, when we dualize the inner problem,can you give me some detail illustrated?
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:14
$begingroup$
thanks for your reply,but I still have confusion here. 1.as you mentioned,I know the problem have infinite constraints,but I don't know what happen to those infinite constraints, when we dualize the inner problem,can you give me some detail illustrated?
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:14
$begingroup$
and for the question 2,why is already sufficient to conclude..... is that any theorem or prove to illustrate this thing? i.e KKT condition or something ele? thank you!
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:20
$begingroup$
and for the question 2,why is already sufficient to conclude..... is that any theorem or prove to illustrate this thing? i.e KKT condition or something ele? thank you!
$endgroup$
– Vergil Chan
Dec 19 '18 at 3:20
$begingroup$
@VergilChan the infinite constraints went into a modest number of constraints. It is clear that the final formulation is just a regular linear optimization problem. It is sufficient to conclude from the definition of the minimum: the minimum of a set is not larger than any element of a set.
$endgroup$
– LinAlg
Dec 19 '18 at 14:45
$begingroup$
@VergilChan the infinite constraints went into a modest number of constraints. It is clear that the final formulation is just a regular linear optimization problem. It is sufficient to conclude from the definition of the minimum: the minimum of a set is not larger than any element of a set.
$endgroup$
– LinAlg
Dec 19 '18 at 14:45
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%2f3045407%2fthe-reason-behind-dual-the-inner-problem-in-robust-optimization%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$
did you appreciate my answer?
$endgroup$
– LinAlg
Jan 5 at 16:12