Lagrange duality compared with Lagrange multiplier method
$begingroup$
As we all know, Lagrange multiplier method says:
in order to find the extremum of $f(x)$ over $x$, s.t. $g(x)=0$,
one instead finds the extremum of $f(x)+lambda g(x)$ over $x$ and $lambda$. Note here only finding extrema is talked about, not min or max.
Lagrange duality says
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
I understand here one has to talk about min and max unlike extremum as in normal Lagrange multiplier method in order for the duality to exist. It is particularly useful for inequality constraints, and perhaps only used for inequality constraints. I know the way I understand might not have grasped the entire meanings, so any comments or corrections about what I said?
lagrange-multiplier karush-kuhn-tucker
edited Dec 18 '18 at 8:49
Arthur
116k7116199
asked Dec 18 '18 at 8:38
feynmanfeynman
1061
$endgroup$
add a comment |
$begingroup$
As we all know, Lagrange multiplier method says:
in order to find the extremum of $f(x)$ over $x$, s.t. $g(x)=0$,
one instead finds the extremum of $f(x)+lambda g(x)$ over $x$ and $lambda$. Note here only finding extrema is talked about, not min or max.
Lagrange duality says
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
I understand here one has to talk about min and max unlike extremum as in normal Lagrange multiplier method in order for the duality to exist. It is particularly useful for inequality constraints, and perhaps only used for inequality constraints. I know the way I understand might not have grasped the entire meanings, so any comments or corrections about what I said?
lagrange-multiplier karush-kuhn-tucker
edited Dec 18 '18 at 8:49
Arthur
116k7116199
asked Dec 18 '18 at 8:38
feynmanfeynman
1061
$endgroup$
add a comment |
$begingroup$
As we all know, Lagrange multiplier method says:
in order to find the extremum of $f(x)$ over $x$, s.t. $g(x)=0$,
one instead finds the extremum of $f(x)+lambda g(x)$ over $x$ and $lambda$. Note here only finding extrema is talked about, not min or max.
Lagrange duality says
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
I understand here one has to talk about min and max unlike extremum as in normal Lagrange multiplier method in order for the duality to exist. It is particularly useful for inequality constraints, and perhaps only used for inequality constraints. I know the way I understand might not have grasped the entire meanings, so any comments or corrections about what I said?
lagrange-multiplier karush-kuhn-tucker
edited Dec 18 '18 at 8:49
Arthur
116k7116199
asked Dec 18 '18 at 8:38
feynmanfeynman
1061
$endgroup$
As we all know, Lagrange multiplier method says:
in order to find the extremum of $f(x)$ over $x$, s.t. $g(x)=0$,
one instead finds the extremum of $f(x)+lambda g(x)$ over $x$ and $lambda$. Note here only finding extrema is talked about, not min or max.
Lagrange duality says
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
I understand here one has to talk about min and max unlike extremum as in normal Lagrange multiplier method in order for the duality to exist. It is particularly useful for inequality constraints, and perhaps only used for inequality constraints. I know the way I understand might not have grasped the entire meanings, so any comments or corrections about what I said?
lagrange-multiplier karush-kuhn-tucker
lagrange-multiplier karush-kuhn-tucker
edited Dec 18 '18 at 8:49
Arthur
116k7116199
asked Dec 18 '18 at 8:38
feynmanfeynman
1061
edited Dec 18 '18 at 8:49
Arthur
116k7116199
asked Dec 18 '18 at 8:38
feynmanfeynman
1061
edited Dec 18 '18 at 8:49
Arthur
116k7116199
edited Dec 18 '18 at 8:49
Arthur
116k7116199
edited Dec 18 '18 at 8:49
Arthur
116k7116199
116k7116199
asked Dec 18 '18 at 8:38
feynmanfeynman
1061
asked Dec 18 '18 at 8:38
feynmanfeynman
1061
asked Dec 18 '18 at 8:38
feynmanfeynman
1061
1061
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Some geometrical ideas about.
The Lagrangian $L(x,lambda)$ stationary points are saddle points. Saddle points have that characteristic
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
See for instance the plot of
$$
L(x,lambda) = x + lambda(x-1)
$$
The stationary point is located at $(x^*,lambda^*) = (1,-1)$ in red, as solution for
$$
L_x = 1+lambda = 0\
L_{lambda} = x-1 = 0
$$
Observe the level curves for $L(x,lambda)$ characterizing a saddle point around the stationary point.
answered Dec 18 '18 at 11:05
CesareoCesareo
9,0413516
$endgroup$
$begingroup$
Right, I agree that the normal Lagrangian multiplier method finds saddle points. But Lagrange duality method finds min and max, rather than saddle points?
$endgroup$
– feynman
Dec 19 '18 at 13:38
$begingroup$
@feynman Please. Have a look at sites.math.washington.edu/~burke/crs/516/notes/saddlepoints.pdf
$endgroup$
– Cesareo
Dec 19 '18 at 13: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%2f3044913%2flagrange-duality-compared-with-lagrange-multiplier-method%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$
Some geometrical ideas about.
The Lagrangian $L(x,lambda)$ stationary points are saddle points. Saddle points have that characteristic
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
See for instance the plot of
$$
L(x,lambda) = x + lambda(x-1)
$$
The stationary point is located at $(x^*,lambda^*) = (1,-1)$ in red, as solution for
$$
L_x = 1+lambda = 0\
L_{lambda} = x-1 = 0
$$
Observe the level curves for $L(x,lambda)$ characterizing a saddle point around the stationary point.
answered Dec 18 '18 at 11:05
CesareoCesareo
9,0413516
$endgroup$
$begingroup$
Right, I agree that the normal Lagrangian multiplier method finds saddle points. But Lagrange duality method finds min and max, rather than saddle points?
$endgroup$
– feynman
Dec 19 '18 at 13:38
$begingroup$
@feynman Please. Have a look at sites.math.washington.edu/~burke/crs/516/notes/saddlepoints.pdf
$endgroup$
– Cesareo
Dec 19 '18 at 13:45
add a comment |
$begingroup$
Some geometrical ideas about.
The Lagrangian $L(x,lambda)$ stationary points are saddle points. Saddle points have that characteristic
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
See for instance the plot of
$$
L(x,lambda) = x + lambda(x-1)
$$
The stationary point is located at $(x^*,lambda^*) = (1,-1)$ in red, as solution for
$$
L_x = 1+lambda = 0\
L_{lambda} = x-1 = 0
$$
Observe the level curves for $L(x,lambda)$ characterizing a saddle point around the stationary point.
answered Dec 18 '18 at 11:05
CesareoCesareo
9,0413516
$endgroup$
$begingroup$
Right, I agree that the normal Lagrangian multiplier method finds saddle points. But Lagrange duality method finds min and max, rather than saddle points?
$endgroup$
– feynman
Dec 19 '18 at 13:38
$begingroup$
@feynman Please. Have a look at sites.math.washington.edu/~burke/crs/516/notes/saddlepoints.pdf
$endgroup$
– Cesareo
Dec 19 '18 at 13:45
add a comment |
$begingroup$
Some geometrical ideas about.
The Lagrangian $L(x,lambda)$ stationary points are saddle points. Saddle points have that characteristic
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
See for instance the plot of
$$
L(x,lambda) = x + lambda(x-1)
$$
The stationary point is located at $(x^*,lambda^*) = (1,-1)$ in red, as solution for
$$
L_x = 1+lambda = 0\
L_{lambda} = x-1 = 0
$$
Observe the level curves for $L(x,lambda)$ characterizing a saddle point around the stationary point.
answered Dec 18 '18 at 11:05
CesareoCesareo
9,0413516
$endgroup$
Some geometrical ideas about.
The Lagrangian $L(x,lambda)$ stationary points are saddle points. Saddle points have that characteristic
$$
min_x(max_lambda(f(x)+lambda g(x)))=max_lambda(min_x(f(x)+lambda g(x)))
$$
See for instance the plot of
$$
L(x,lambda) = x + lambda(x-1)
$$
The stationary point is located at $(x^*,lambda^*) = (1,-1)$ in red, as solution for
$$
L_x = 1+lambda = 0\
L_{lambda} = x-1 = 0
$$
Observe the level curves for $L(x,lambda)$ characterizing a saddle point around the stationary point.
answered Dec 18 '18 at 11:05
CesareoCesareo
9,0413516
answered Dec 18 '18 at 11:05
CesareoCesareo
9,0413516
answered Dec 18 '18 at 11:05
CesareoCesareo
9,0413516
answered Dec 18 '18 at 11:05
CesareoCesareo
9,0413516
9,0413516
$begingroup$
Right, I agree that the normal Lagrangian multiplier method finds saddle points. But Lagrange duality method finds min and max, rather than saddle points?
$endgroup$
– feynman
Dec 19 '18 at 13:38
$begingroup$
@feynman Please. Have a look at sites.math.washington.edu/~burke/crs/516/notes/saddlepoints.pdf
$endgroup$
– Cesareo
Dec 19 '18 at 13:45
add a comment |
$begingroup$
Right, I agree that the normal Lagrangian multiplier method finds saddle points. But Lagrange duality method finds min and max, rather than saddle points?
$endgroup$
– feynman
Dec 19 '18 at 13:38
$begingroup$
@feynman Please. Have a look at sites.math.washington.edu/~burke/crs/516/notes/saddlepoints.pdf
$endgroup$
– Cesareo
Dec 19 '18 at 13:45
$begingroup$
Right, I agree that the normal Lagrangian multiplier method finds saddle points. But Lagrange duality method finds min and max, rather than saddle points?
$endgroup$
– feynman
Dec 19 '18 at 13:38
$begingroup$
Right, I agree that the normal Lagrangian multiplier method finds saddle points. But Lagrange duality method finds min and max, rather than saddle points?
$endgroup$
– feynman
Dec 19 '18 at 13:38
$begingroup$
@feynman Please. Have a look at sites.math.washington.edu/~burke/crs/516/notes/saddlepoints.pdf
$endgroup$
– Cesareo
Dec 19 '18 at 13:45
$begingroup$
@feynman Please. Have a look at sites.math.washington.edu/~burke/crs/516/notes/saddlepoints.pdf
$endgroup$
– Cesareo
Dec 19 '18 at 13: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%2f3044913%2flagrange-duality-compared-with-lagrange-multiplier-method%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
