Why is the lagrange dual function concave?
$begingroup$
In a book I'm reading (Convex Optimization by Boyd and Vandenberghe) it says
I'm struggling to understand the last sentence. Why can one conclude concavity from having a pointwise infimum of a family of affine functions?
lagrange-multiplier supremum-and-infimum
$endgroup$
add a comment |
$begingroup$
In a book I'm reading (Convex Optimization by Boyd and Vandenberghe) it says
I'm struggling to understand the last sentence. Why can one conclude concavity from having a pointwise infimum of a family of affine functions?
lagrange-multiplier supremum-and-infimum
$endgroup$
add a comment |
$begingroup$
In a book I'm reading (Convex Optimization by Boyd and Vandenberghe) it says
I'm struggling to understand the last sentence. Why can one conclude concavity from having a pointwise infimum of a family of affine functions?
lagrange-multiplier supremum-and-infimum
$endgroup$
In a book I'm reading (Convex Optimization by Boyd and Vandenberghe) it says
I'm struggling to understand the last sentence. Why can one conclude concavity from having a pointwise infimum of a family of affine functions?
lagrange-multiplier supremum-and-infimum
lagrange-multiplier supremum-and-infimum
edited Aug 11 '18 at 7:52
mcsanchez
134
134
asked Jul 26 '15 at 11:55
user2820379user2820379
15818
15818
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
The Lagrange function $L(x,lambda,mu)$ is affine in $lambda$ and $mu$, thus, concave, and the infimum of concave functions is concave. (Equivalently to the supremum of convex is convex.)
$endgroup$
$begingroup$
What does affine in $lambda$ and $mu$ mean?
$endgroup$
– user2820379
Jul 26 '15 at 12:27
1
$begingroup$
@user2820379 Affine function is simply a linear function plus a constant (with respect to $lambda$ and $mu$ for any fixed $x$).
$endgroup$
– A.Γ.
Jul 26 '15 at 12:30
add a comment |
$begingroup$
The book referenced is Convex Optimization by Boyd and Vandenberghe. To better see the "pointwise infimum", consider a slight change/abuse of notation: $L_x(xi) = L(x, lambda, nu)$ where $xi = (lambda, nu)$. For a fixed $x$, $L_x(xi)$ is affine in $xi$ so ${L_x(xi) ,:, x in mathcal{D}}$ is a family of affine functions and its pointwise infimum is
$$g(xi) = inf_x ,{L_x(xi),:,xinmathcal{D}}$$
Now we can use @A.Γ.'s pointer to show that $g$ is concave by showing the epigraph of $-g$ is convex. For a given $xi$, we have $g(xi) le L_x(xi)$ for any $L_x$ from the family so $(xi, -g(xi))$ is always "above" $(xi, -L_x(xi)$) hence $rm{epi}(-g) in bigcap_x rm{epi}(L_x)$.
$endgroup$
add a comment |
$begingroup$
Concavity of the dual function is very much a non-intuitive property.
One way to show it is to use the fact that a function is convex if and only if its epigraph is a convex set. The epigraph of a function $f(vec x)$ is the set of points 'above' that function:
$$left{(vec x,y) mid y geq f(vec x)right}$$
For the dual function we have the pointwise infimum of a family of affine functions:
$$D(vec lambda, vec nu) = inf_{vec x} mathcal{L}(vec x,vec lambda, vec nu) = inf_{vec x} A(vec x) begin{bmatrix} vec lambda \ vec nu end{bmatrix} + vec b(vec x)$$
That is, we can re-write the Lagrangian to have the form $Avec lambda + vec b$ for some matrix $A$ and vector $vec b$ that both depend on $vec x$.
Loosely speaking, pointwise means we can pick different values for $vec x$ depending on the value of $vec lambda$.
The epigraph of $mathcal{L}$ is for any given value of $vec x$ is going to be a convex set, as once $vec x$ is fixed the function is affine, and affine functions are both convex and concave. If we flip this notion, we can look at negative epigraphs, or the set of points 'below' the function. This negative epigraph of $D$ is going to be the intersection of the negative eopigraphs of all possible functions formed by fixing all possible values of $vec x$. The intersection of convex sets is a convex set, so this negative epigraph is a convex set. The negative epigraph of a function is a convex set if and only if the function is concave, so the dual function $D$ must be concave!
It helps a bit to draw this out on a sheet of paper.
$endgroup$
add a comment |
$begingroup$
I think it's easier to visualize the maximization case, in which the sup is convex. Say you change a multiplier in the direction that relaxes its constraint, then the lagrangian, being affine on the multiplier, is at least linearly better respect to the change and there is probably room for improvement above linearity because of the relaxation, hence you get convexity. Indeed, the constraint evaluated at the current optimum is a subgradient of the lagrangian. In terms of the epigraph, after changing the multiplier you will stay at least in the same affine member of the family, but you may as well scale up to the next one.
$endgroup$
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%2f1374399%2fwhy-is-the-lagrange-dual-function-concave%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The Lagrange function $L(x,lambda,mu)$ is affine in $lambda$ and $mu$, thus, concave, and the infimum of concave functions is concave. (Equivalently to the supremum of convex is convex.)
$endgroup$
$begingroup$
What does affine in $lambda$ and $mu$ mean?
$endgroup$
– user2820379
Jul 26 '15 at 12:27
1
$begingroup$
@user2820379 Affine function is simply a linear function plus a constant (with respect to $lambda$ and $mu$ for any fixed $x$).
$endgroup$
– A.Γ.
Jul 26 '15 at 12:30
add a comment |
$begingroup$
The Lagrange function $L(x,lambda,mu)$ is affine in $lambda$ and $mu$, thus, concave, and the infimum of concave functions is concave. (Equivalently to the supremum of convex is convex.)
$endgroup$
$begingroup$
What does affine in $lambda$ and $mu$ mean?
$endgroup$
– user2820379
Jul 26 '15 at 12:27
1
$begingroup$
@user2820379 Affine function is simply a linear function plus a constant (with respect to $lambda$ and $mu$ for any fixed $x$).
$endgroup$
– A.Γ.
Jul 26 '15 at 12:30
add a comment |
$begingroup$
The Lagrange function $L(x,lambda,mu)$ is affine in $lambda$ and $mu$, thus, concave, and the infimum of concave functions is concave. (Equivalently to the supremum of convex is convex.)
$endgroup$
The Lagrange function $L(x,lambda,mu)$ is affine in $lambda$ and $mu$, thus, concave, and the infimum of concave functions is concave. (Equivalently to the supremum of convex is convex.)
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Jul 26 '15 at 12:08
A.Γ.A.Γ.
22.7k32656
22.7k32656
$begingroup$
What does affine in $lambda$ and $mu$ mean?
$endgroup$
– user2820379
Jul 26 '15 at 12:27
1
$begingroup$
@user2820379 Affine function is simply a linear function plus a constant (with respect to $lambda$ and $mu$ for any fixed $x$).
$endgroup$
– A.Γ.
Jul 26 '15 at 12:30
add a comment |
$begingroup$
What does affine in $lambda$ and $mu$ mean?
$endgroup$
– user2820379
Jul 26 '15 at 12:27
1
$begingroup$
@user2820379 Affine function is simply a linear function plus a constant (with respect to $lambda$ and $mu$ for any fixed $x$).
$endgroup$
– A.Γ.
Jul 26 '15 at 12:30
$begingroup$
What does affine in $lambda$ and $mu$ mean?
$endgroup$
– user2820379
Jul 26 '15 at 12:27
$begingroup$
What does affine in $lambda$ and $mu$ mean?
$endgroup$
– user2820379
Jul 26 '15 at 12:27
1
1
$begingroup$
@user2820379 Affine function is simply a linear function plus a constant (with respect to $lambda$ and $mu$ for any fixed $x$).
$endgroup$
– A.Γ.
Jul 26 '15 at 12:30
$begingroup$
@user2820379 Affine function is simply a linear function plus a constant (with respect to $lambda$ and $mu$ for any fixed $x$).
$endgroup$
– A.Γ.
Jul 26 '15 at 12:30
add a comment |
$begingroup$
The book referenced is Convex Optimization by Boyd and Vandenberghe. To better see the "pointwise infimum", consider a slight change/abuse of notation: $L_x(xi) = L(x, lambda, nu)$ where $xi = (lambda, nu)$. For a fixed $x$, $L_x(xi)$ is affine in $xi$ so ${L_x(xi) ,:, x in mathcal{D}}$ is a family of affine functions and its pointwise infimum is
$$g(xi) = inf_x ,{L_x(xi),:,xinmathcal{D}}$$
Now we can use @A.Γ.'s pointer to show that $g$ is concave by showing the epigraph of $-g$ is convex. For a given $xi$, we have $g(xi) le L_x(xi)$ for any $L_x$ from the family so $(xi, -g(xi))$ is always "above" $(xi, -L_x(xi)$) hence $rm{epi}(-g) in bigcap_x rm{epi}(L_x)$.
$endgroup$
add a comment |
$begingroup$
The book referenced is Convex Optimization by Boyd and Vandenberghe. To better see the "pointwise infimum", consider a slight change/abuse of notation: $L_x(xi) = L(x, lambda, nu)$ where $xi = (lambda, nu)$. For a fixed $x$, $L_x(xi)$ is affine in $xi$ so ${L_x(xi) ,:, x in mathcal{D}}$ is a family of affine functions and its pointwise infimum is
$$g(xi) = inf_x ,{L_x(xi),:,xinmathcal{D}}$$
Now we can use @A.Γ.'s pointer to show that $g$ is concave by showing the epigraph of $-g$ is convex. For a given $xi$, we have $g(xi) le L_x(xi)$ for any $L_x$ from the family so $(xi, -g(xi))$ is always "above" $(xi, -L_x(xi)$) hence $rm{epi}(-g) in bigcap_x rm{epi}(L_x)$.
$endgroup$
add a comment |
$begingroup$
The book referenced is Convex Optimization by Boyd and Vandenberghe. To better see the "pointwise infimum", consider a slight change/abuse of notation: $L_x(xi) = L(x, lambda, nu)$ where $xi = (lambda, nu)$. For a fixed $x$, $L_x(xi)$ is affine in $xi$ so ${L_x(xi) ,:, x in mathcal{D}}$ is a family of affine functions and its pointwise infimum is
$$g(xi) = inf_x ,{L_x(xi),:,xinmathcal{D}}$$
Now we can use @A.Γ.'s pointer to show that $g$ is concave by showing the epigraph of $-g$ is convex. For a given $xi$, we have $g(xi) le L_x(xi)$ for any $L_x$ from the family so $(xi, -g(xi))$ is always "above" $(xi, -L_x(xi)$) hence $rm{epi}(-g) in bigcap_x rm{epi}(L_x)$.
$endgroup$
The book referenced is Convex Optimization by Boyd and Vandenberghe. To better see the "pointwise infimum", consider a slight change/abuse of notation: $L_x(xi) = L(x, lambda, nu)$ where $xi = (lambda, nu)$. For a fixed $x$, $L_x(xi)$ is affine in $xi$ so ${L_x(xi) ,:, x in mathcal{D}}$ is a family of affine functions and its pointwise infimum is
$$g(xi) = inf_x ,{L_x(xi),:,xinmathcal{D}}$$
Now we can use @A.Γ.'s pointer to show that $g$ is concave by showing the epigraph of $-g$ is convex. For a given $xi$, we have $g(xi) le L_x(xi)$ for any $L_x$ from the family so $(xi, -g(xi))$ is always "above" $(xi, -L_x(xi)$) hence $rm{epi}(-g) in bigcap_x rm{epi}(L_x)$.
answered Aug 11 '18 at 7:36
mcsanchezmcsanchez
134
134
add a comment |
add a comment |
$begingroup$
Concavity of the dual function is very much a non-intuitive property.
One way to show it is to use the fact that a function is convex if and only if its epigraph is a convex set. The epigraph of a function $f(vec x)$ is the set of points 'above' that function:
$$left{(vec x,y) mid y geq f(vec x)right}$$
For the dual function we have the pointwise infimum of a family of affine functions:
$$D(vec lambda, vec nu) = inf_{vec x} mathcal{L}(vec x,vec lambda, vec nu) = inf_{vec x} A(vec x) begin{bmatrix} vec lambda \ vec nu end{bmatrix} + vec b(vec x)$$
That is, we can re-write the Lagrangian to have the form $Avec lambda + vec b$ for some matrix $A$ and vector $vec b$ that both depend on $vec x$.
Loosely speaking, pointwise means we can pick different values for $vec x$ depending on the value of $vec lambda$.
The epigraph of $mathcal{L}$ is for any given value of $vec x$ is going to be a convex set, as once $vec x$ is fixed the function is affine, and affine functions are both convex and concave. If we flip this notion, we can look at negative epigraphs, or the set of points 'below' the function. This negative epigraph of $D$ is going to be the intersection of the negative eopigraphs of all possible functions formed by fixing all possible values of $vec x$. The intersection of convex sets is a convex set, so this negative epigraph is a convex set. The negative epigraph of a function is a convex set if and only if the function is concave, so the dual function $D$ must be concave!
It helps a bit to draw this out on a sheet of paper.
$endgroup$
add a comment |
$begingroup$
Concavity of the dual function is very much a non-intuitive property.
One way to show it is to use the fact that a function is convex if and only if its epigraph is a convex set. The epigraph of a function $f(vec x)$ is the set of points 'above' that function:
$$left{(vec x,y) mid y geq f(vec x)right}$$
For the dual function we have the pointwise infimum of a family of affine functions:
$$D(vec lambda, vec nu) = inf_{vec x} mathcal{L}(vec x,vec lambda, vec nu) = inf_{vec x} A(vec x) begin{bmatrix} vec lambda \ vec nu end{bmatrix} + vec b(vec x)$$
That is, we can re-write the Lagrangian to have the form $Avec lambda + vec b$ for some matrix $A$ and vector $vec b$ that both depend on $vec x$.
Loosely speaking, pointwise means we can pick different values for $vec x$ depending on the value of $vec lambda$.
The epigraph of $mathcal{L}$ is for any given value of $vec x$ is going to be a convex set, as once $vec x$ is fixed the function is affine, and affine functions are both convex and concave. If we flip this notion, we can look at negative epigraphs, or the set of points 'below' the function. This negative epigraph of $D$ is going to be the intersection of the negative eopigraphs of all possible functions formed by fixing all possible values of $vec x$. The intersection of convex sets is a convex set, so this negative epigraph is a convex set. The negative epigraph of a function is a convex set if and only if the function is concave, so the dual function $D$ must be concave!
It helps a bit to draw this out on a sheet of paper.
$endgroup$
add a comment |
$begingroup$
Concavity of the dual function is very much a non-intuitive property.
One way to show it is to use the fact that a function is convex if and only if its epigraph is a convex set. The epigraph of a function $f(vec x)$ is the set of points 'above' that function:
$$left{(vec x,y) mid y geq f(vec x)right}$$
For the dual function we have the pointwise infimum of a family of affine functions:
$$D(vec lambda, vec nu) = inf_{vec x} mathcal{L}(vec x,vec lambda, vec nu) = inf_{vec x} A(vec x) begin{bmatrix} vec lambda \ vec nu end{bmatrix} + vec b(vec x)$$
That is, we can re-write the Lagrangian to have the form $Avec lambda + vec b$ for some matrix $A$ and vector $vec b$ that both depend on $vec x$.
Loosely speaking, pointwise means we can pick different values for $vec x$ depending on the value of $vec lambda$.
The epigraph of $mathcal{L}$ is for any given value of $vec x$ is going to be a convex set, as once $vec x$ is fixed the function is affine, and affine functions are both convex and concave. If we flip this notion, we can look at negative epigraphs, or the set of points 'below' the function. This negative epigraph of $D$ is going to be the intersection of the negative eopigraphs of all possible functions formed by fixing all possible values of $vec x$. The intersection of convex sets is a convex set, so this negative epigraph is a convex set. The negative epigraph of a function is a convex set if and only if the function is concave, so the dual function $D$ must be concave!
It helps a bit to draw this out on a sheet of paper.
$endgroup$
Concavity of the dual function is very much a non-intuitive property.
One way to show it is to use the fact that a function is convex if and only if its epigraph is a convex set. The epigraph of a function $f(vec x)$ is the set of points 'above' that function:
$$left{(vec x,y) mid y geq f(vec x)right}$$
For the dual function we have the pointwise infimum of a family of affine functions:
$$D(vec lambda, vec nu) = inf_{vec x} mathcal{L}(vec x,vec lambda, vec nu) = inf_{vec x} A(vec x) begin{bmatrix} vec lambda \ vec nu end{bmatrix} + vec b(vec x)$$
That is, we can re-write the Lagrangian to have the form $Avec lambda + vec b$ for some matrix $A$ and vector $vec b$ that both depend on $vec x$.
Loosely speaking, pointwise means we can pick different values for $vec x$ depending on the value of $vec lambda$.
The epigraph of $mathcal{L}$ is for any given value of $vec x$ is going to be a convex set, as once $vec x$ is fixed the function is affine, and affine functions are both convex and concave. If we flip this notion, we can look at negative epigraphs, or the set of points 'below' the function. This negative epigraph of $D$ is going to be the intersection of the negative eopigraphs of all possible functions formed by fixing all possible values of $vec x$. The intersection of convex sets is a convex set, so this negative epigraph is a convex set. The negative epigraph of a function is a convex set if and only if the function is concave, so the dual function $D$ must be concave!
It helps a bit to draw this out on a sheet of paper.
answered Apr 21 '18 at 22:35
MageekMageek
1115
1115
add a comment |
add a comment |
$begingroup$
I think it's easier to visualize the maximization case, in which the sup is convex. Say you change a multiplier in the direction that relaxes its constraint, then the lagrangian, being affine on the multiplier, is at least linearly better respect to the change and there is probably room for improvement above linearity because of the relaxation, hence you get convexity. Indeed, the constraint evaluated at the current optimum is a subgradient of the lagrangian. In terms of the epigraph, after changing the multiplier you will stay at least in the same affine member of the family, but you may as well scale up to the next one.
$endgroup$
add a comment |
$begingroup$
I think it's easier to visualize the maximization case, in which the sup is convex. Say you change a multiplier in the direction that relaxes its constraint, then the lagrangian, being affine on the multiplier, is at least linearly better respect to the change and there is probably room for improvement above linearity because of the relaxation, hence you get convexity. Indeed, the constraint evaluated at the current optimum is a subgradient of the lagrangian. In terms of the epigraph, after changing the multiplier you will stay at least in the same affine member of the family, but you may as well scale up to the next one.
$endgroup$
add a comment |
$begingroup$
I think it's easier to visualize the maximization case, in which the sup is convex. Say you change a multiplier in the direction that relaxes its constraint, then the lagrangian, being affine on the multiplier, is at least linearly better respect to the change and there is probably room for improvement above linearity because of the relaxation, hence you get convexity. Indeed, the constraint evaluated at the current optimum is a subgradient of the lagrangian. In terms of the epigraph, after changing the multiplier you will stay at least in the same affine member of the family, but you may as well scale up to the next one.
$endgroup$
I think it's easier to visualize the maximization case, in which the sup is convex. Say you change a multiplier in the direction that relaxes its constraint, then the lagrangian, being affine on the multiplier, is at least linearly better respect to the change and there is probably room for improvement above linearity because of the relaxation, hence you get convexity. Indeed, the constraint evaluated at the current optimum is a subgradient of the lagrangian. In terms of the epigraph, after changing the multiplier you will stay at least in the same affine member of the family, but you may as well scale up to the next one.
edited Dec 18 '18 at 17:00
answered Dec 18 '18 at 5:26
memeplexmemeplex
16613
16613
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%2f1374399%2fwhy-is-the-lagrange-dual-function-concave%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