Proving convexity of $h(y) = inf_{Ax=y}{f(x)}$ for convex $f(x)$ over $mathbb{R}^n$, and...
$begingroup$
Got into this question in an optimization course:
Let $f:mathbb{R}^nrightarrowmathbb{R}$ be convex, and let $Ainmathbb{R}^{mtimes{n}}$. Consider:
$$h(y) = inf_{Ax=y}{{f(x)}}$$
Prove that $h$ is convex.
Any help? It's not the traditional preservation of convexity under infimum.
I believe the direction should be something like: Assume $x_0inmathbb{R}^n$ is the $x$ for which $h(y_0)=f(x_0)$. Thus,
$$h(y_0)=f(x_0)leq{f(x_0+z)}$$
for any $z$ that holds $Az=0$.
From here i don't know how to continue...
convex-analysis convex-optimization
asked Dec 20 '18 at 15:43
RondoRondo
32
$endgroup$
add a comment |
$begingroup$
Got into this question in an optimization course:
Let $f:mathbb{R}^nrightarrowmathbb{R}$ be convex, and let $Ainmathbb{R}^{mtimes{n}}$. Consider:
$$h(y) = inf_{Ax=y}{{f(x)}}$$
Prove that $h$ is convex.
Any help? It's not the traditional preservation of convexity under infimum.
I believe the direction should be something like: Assume $x_0inmathbb{R}^n$ is the $x$ for which $h(y_0)=f(x_0)$. Thus,
$$h(y_0)=f(x_0)leq{f(x_0+z)}$$
for any $z$ that holds $Az=0$.
From here i don't know how to continue...
convex-analysis convex-optimization
asked Dec 20 '18 at 15:43
RondoRondo
32
$endgroup$
$begingroup$
I am not sure why you did not appreciate my answer, but your statement "It's not the traditional preservation of convexity under infimum" is not true and my answer showed that.
$endgroup$
– LinAlg
Dec 24 '18 at 19:55
add a comment |
$begingroup$
Got into this question in an optimization course:
Let $f:mathbb{R}^nrightarrowmathbb{R}$ be convex, and let $Ainmathbb{R}^{mtimes{n}}$. Consider:
$$h(y) = inf_{Ax=y}{{f(x)}}$$
Prove that $h$ is convex.
Any help? It's not the traditional preservation of convexity under infimum.
I believe the direction should be something like: Assume $x_0inmathbb{R}^n$ is the $x$ for which $h(y_0)=f(x_0)$. Thus,
$$h(y_0)=f(x_0)leq{f(x_0+z)}$$
for any $z$ that holds $Az=0$.
From here i don't know how to continue...
convex-analysis convex-optimization
asked Dec 20 '18 at 15:43
RondoRondo
32
$endgroup$
Got into this question in an optimization course:
Let $f:mathbb{R}^nrightarrowmathbb{R}$ be convex, and let $Ainmathbb{R}^{mtimes{n}}$. Consider:
$$h(y) = inf_{Ax=y}{{f(x)}}$$
Prove that $h$ is convex.
Any help? It's not the traditional preservation of convexity under infimum.
I believe the direction should be something like: Assume $x_0inmathbb{R}^n$ is the $x$ for which $h(y_0)=f(x_0)$. Thus,
$$h(y_0)=f(x_0)leq{f(x_0+z)}$$
for any $z$ that holds $Az=0$.
From here i don't know how to continue...
convex-analysis convex-optimization
convex-analysis convex-optimization
asked Dec 20 '18 at 15:43
RondoRondo
32
asked Dec 20 '18 at 15:43
RondoRondo
32
edited Dec 20 '18 at 16:15
Rondo
asked Dec 20 '18 at 15:43
RondoRondo
32
asked Dec 20 '18 at 15:43
RondoRondo
32
asked Dec 20 '18 at 15:43
RondoRondo
32
32
$begingroup$
I am not sure why you did not appreciate my answer, but your statement "It's not the traditional preservation of convexity under infimum" is not true and my answer showed that.
$endgroup$
– LinAlg
Dec 24 '18 at 19:55
add a comment |
$begingroup$
I am not sure why you did not appreciate my answer, but your statement "It's not the traditional preservation of convexity under infimum" is not true and my answer showed that.
$endgroup$
– LinAlg
Dec 24 '18 at 19:55
$begingroup$
I am not sure why you did not appreciate my answer, but your statement "It's not the traditional preservation of convexity under infimum" is not true and my answer showed that.
$endgroup$
– LinAlg
Dec 24 '18 at 19:55
$begingroup$
I am not sure why you did not appreciate my answer, but your statement "It's not the traditional preservation of convexity under infimum" is not true and my answer showed that.
$endgroup$
– LinAlg
Dec 24 '18 at 19:55
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $epsilon>0$ be arbitrary and assume that
$$
u = alpha v + (1-alpha)w,quad alphain(0,1), ;u,v,winmathbb{R}^m.
$$ Assume $A^{-1}(v)={x|Ax = v}$ is not empty. By the assumption, we can find $x$ such that $Ax = v$ and
$$
h(v) leq f(x)leq h(v)+epsilon.
$$ Also assume that $A^{-1}(w)$ is not empty and find $x'$ such that
$$
h(w)leq f(x')leq h(w)+epsilon.
$$ Now, note that $alpha x+(1-alpha)x' in A^{-1}(u)$. Therefore, it holds that
$$
h(u) leq f(alpha x+(1-alpha)x') leq alpha f(x) +(1-alpha)f(x')leq alpha h(v)+(1-alpha)h(w) +epsilon.
$$ Since $epsilon>0$ was arbitrary, we get
$$h(u) leq alpha h(v)+(1-alpha)h(w) ,
$$as desired.
If $A^{-1}(v)$ is empty, according to the definition, we have
$$
h(v) = inf_{xin A^{-1}(v)} f(x) = inf varnothing = infty.
$$ Hence if one of the sets $A^{-1}(v)$ or $A^{-1}(w)$ is empty, then
$$
h(u) leq alpha h(v)+(1-alpha)h(w)=infty
$$ is obvious. (But it is desirable to assume that $A :mathbb{R}^n to mathbb{R}^m$ is surjective.)
answered Dec 20 '18 at 15:59
SongSong
16.5k1741
$endgroup$
add a comment |
$begingroup$
Consider $g(x,y) = f(x) + delta( (x,y) | Ax=y)$, where $delta$ is the support function that takes the value 0 if $Ax=y$, and $infty$ otherwise. Since $g$ is jointly convex and $h$ is the infinimum over one coordinate (partial minimization), $h$ is convex.
answered Dec 20 '18 at 16:57
LinAlgLinAlg
10k1521
$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%2f3047667%2fproving-convexity-of-hy-inf-ax-yfx-for-convex-fx-over-mathbb%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $epsilon>0$ be arbitrary and assume that
$$
u = alpha v + (1-alpha)w,quad alphain(0,1), ;u,v,winmathbb{R}^m.
$$ Assume $A^{-1}(v)={x|Ax = v}$ is not empty. By the assumption, we can find $x$ such that $Ax = v$ and
$$
h(v) leq f(x)leq h(v)+epsilon.
$$ Also assume that $A^{-1}(w)$ is not empty and find $x'$ such that
$$
h(w)leq f(x')leq h(w)+epsilon.
$$ Now, note that $alpha x+(1-alpha)x' in A^{-1}(u)$. Therefore, it holds that
$$
h(u) leq f(alpha x+(1-alpha)x') leq alpha f(x) +(1-alpha)f(x')leq alpha h(v)+(1-alpha)h(w) +epsilon.
$$ Since $epsilon>0$ was arbitrary, we get
$$h(u) leq alpha h(v)+(1-alpha)h(w) ,
$$as desired.
If $A^{-1}(v)$ is empty, according to the definition, we have
$$
h(v) = inf_{xin A^{-1}(v)} f(x) = inf varnothing = infty.
$$ Hence if one of the sets $A^{-1}(v)$ or $A^{-1}(w)$ is empty, then
$$
h(u) leq alpha h(v)+(1-alpha)h(w)=infty
$$ is obvious. (But it is desirable to assume that $A :mathbb{R}^n to mathbb{R}^m$ is surjective.)
answered Dec 20 '18 at 15:59
SongSong
16.5k1741
$endgroup$
add a comment |
$begingroup$
Let $epsilon>0$ be arbitrary and assume that
$$
u = alpha v + (1-alpha)w,quad alphain(0,1), ;u,v,winmathbb{R}^m.
$$ Assume $A^{-1}(v)={x|Ax = v}$ is not empty. By the assumption, we can find $x$ such that $Ax = v$ and
$$
h(v) leq f(x)leq h(v)+epsilon.
$$ Also assume that $A^{-1}(w)$ is not empty and find $x'$ such that
$$
h(w)leq f(x')leq h(w)+epsilon.
$$ Now, note that $alpha x+(1-alpha)x' in A^{-1}(u)$. Therefore, it holds that
$$
h(u) leq f(alpha x+(1-alpha)x') leq alpha f(x) +(1-alpha)f(x')leq alpha h(v)+(1-alpha)h(w) +epsilon.
$$ Since $epsilon>0$ was arbitrary, we get
$$h(u) leq alpha h(v)+(1-alpha)h(w) ,
$$as desired.
If $A^{-1}(v)$ is empty, according to the definition, we have
$$
h(v) = inf_{xin A^{-1}(v)} f(x) = inf varnothing = infty.
$$ Hence if one of the sets $A^{-1}(v)$ or $A^{-1}(w)$ is empty, then
$$
h(u) leq alpha h(v)+(1-alpha)h(w)=infty
$$ is obvious. (But it is desirable to assume that $A :mathbb{R}^n to mathbb{R}^m$ is surjective.)
answered Dec 20 '18 at 15:59
SongSong
16.5k1741
$endgroup$
add a comment |
$begingroup$
Let $epsilon>0$ be arbitrary and assume that
$$
u = alpha v + (1-alpha)w,quad alphain(0,1), ;u,v,winmathbb{R}^m.
$$ Assume $A^{-1}(v)={x|Ax = v}$ is not empty. By the assumption, we can find $x$ such that $Ax = v$ and
$$
h(v) leq f(x)leq h(v)+epsilon.
$$ Also assume that $A^{-1}(w)$ is not empty and find $x'$ such that
$$
h(w)leq f(x')leq h(w)+epsilon.
$$ Now, note that $alpha x+(1-alpha)x' in A^{-1}(u)$. Therefore, it holds that
$$
h(u) leq f(alpha x+(1-alpha)x') leq alpha f(x) +(1-alpha)f(x')leq alpha h(v)+(1-alpha)h(w) +epsilon.
$$ Since $epsilon>0$ was arbitrary, we get
$$h(u) leq alpha h(v)+(1-alpha)h(w) ,
$$as desired.
If $A^{-1}(v)$ is empty, according to the definition, we have
$$
h(v) = inf_{xin A^{-1}(v)} f(x) = inf varnothing = infty.
$$ Hence if one of the sets $A^{-1}(v)$ or $A^{-1}(w)$ is empty, then
$$
h(u) leq alpha h(v)+(1-alpha)h(w)=infty
$$ is obvious. (But it is desirable to assume that $A :mathbb{R}^n to mathbb{R}^m$ is surjective.)
answered Dec 20 '18 at 15:59
SongSong
16.5k1741
$endgroup$
Let $epsilon>0$ be arbitrary and assume that
$$
u = alpha v + (1-alpha)w,quad alphain(0,1), ;u,v,winmathbb{R}^m.
$$ Assume $A^{-1}(v)={x|Ax = v}$ is not empty. By the assumption, we can find $x$ such that $Ax = v$ and
$$
h(v) leq f(x)leq h(v)+epsilon.
$$ Also assume that $A^{-1}(w)$ is not empty and find $x'$ such that
$$
h(w)leq f(x')leq h(w)+epsilon.
$$ Now, note that $alpha x+(1-alpha)x' in A^{-1}(u)$. Therefore, it holds that
$$
h(u) leq f(alpha x+(1-alpha)x') leq alpha f(x) +(1-alpha)f(x')leq alpha h(v)+(1-alpha)h(w) +epsilon.
$$ Since $epsilon>0$ was arbitrary, we get
$$h(u) leq alpha h(v)+(1-alpha)h(w) ,
$$as desired.
If $A^{-1}(v)$ is empty, according to the definition, we have
$$
h(v) = inf_{xin A^{-1}(v)} f(x) = inf varnothing = infty.
$$ Hence if one of the sets $A^{-1}(v)$ or $A^{-1}(w)$ is empty, then
$$
h(u) leq alpha h(v)+(1-alpha)h(w)=infty
$$ is obvious. (But it is desirable to assume that $A :mathbb{R}^n to mathbb{R}^m$ is surjective.)
answered Dec 20 '18 at 15:59
SongSong
16.5k1741
answered Dec 20 '18 at 15:59
SongSong
16.5k1741
answered Dec 20 '18 at 15:59
SongSong
16.5k1741
answered Dec 20 '18 at 15:59
SongSong
16.5k1741
16.5k1741
add a comment |
add a comment |
$begingroup$
Consider $g(x,y) = f(x) + delta( (x,y) | Ax=y)$, where $delta$ is the support function that takes the value 0 if $Ax=y$, and $infty$ otherwise. Since $g$ is jointly convex and $h$ is the infinimum over one coordinate (partial minimization), $h$ is convex.
answered Dec 20 '18 at 16:57
LinAlgLinAlg
10k1521
$endgroup$
add a comment |
$begingroup$
Consider $g(x,y) = f(x) + delta( (x,y) | Ax=y)$, where $delta$ is the support function that takes the value 0 if $Ax=y$, and $infty$ otherwise. Since $g$ is jointly convex and $h$ is the infinimum over one coordinate (partial minimization), $h$ is convex.
answered Dec 20 '18 at 16:57
LinAlgLinAlg
10k1521
$endgroup$
add a comment |
$begingroup$
Consider $g(x,y) = f(x) + delta( (x,y) | Ax=y)$, where $delta$ is the support function that takes the value 0 if $Ax=y$, and $infty$ otherwise. Since $g$ is jointly convex and $h$ is the infinimum over one coordinate (partial minimization), $h$ is convex.
answered Dec 20 '18 at 16:57
LinAlgLinAlg
10k1521
$endgroup$
Consider $g(x,y) = f(x) + delta( (x,y) | Ax=y)$, where $delta$ is the support function that takes the value 0 if $Ax=y$, and $infty$ otherwise. Since $g$ is jointly convex and $h$ is the infinimum over one coordinate (partial minimization), $h$ is convex.
answered Dec 20 '18 at 16:57
LinAlgLinAlg
10k1521
answered Dec 20 '18 at 16:57
LinAlgLinAlg
10k1521
answered Dec 20 '18 at 16:57
LinAlgLinAlg
10k1521
answered Dec 20 '18 at 16:57
LinAlgLinAlg
10k1521
10k1521
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%2f3047667%2fproving-convexity-of-hy-inf-ax-yfx-for-convex-fx-over-mathbb%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$
I am not sure why you did not appreciate my answer, but your statement "It's not the traditional preservation of convexity under infimum" is not true and my answer showed that.
$endgroup$
– LinAlg
Dec 24 '18 at 19:55