Show minimum distance to a convex set is a convex function.
$begingroup$
Show that
$$
g(x)=inf_{z in C}|x-z|
$$
where $g:mathbb{R}^n rightarrow mathbb{R}$, $C$ is a convex set in $mathbb{R}^n$ (nor close neither bounded), and $|cdot|$ is a norm on $mathbb{R}^n$.
Let $x,y$ be in $mathbb{R}^n$. We need to show that
$$
g(lambda x +(1-lambda)y) leq lambda g(x)+ (1-lambda)g(y) tag{1}
$$
I tried the following:
$$
|lambda x +(1-lambda)y-z| leq lambda| x -z| + (1-lambda)| y-z| ,, forall {z in C}
$$
Since
$$
g(lambda x +(1-lambda)y)=inf_{z in C}|lambda x +(1-lambda)y-z| leq |lambda x +(1-lambda)y-z| ,, forall {z in C}
$$
So
$$
g(lambda x +(1-lambda)y)=inf_{z in C}|lambda x +(1-lambda)y-z| leq lambda| x -z| + (1-lambda)| y-z| ,, forall {z in C}
$$
I do not know how to handle the right hand side and apply infimum in a right way because the following is not correct in general
$$
inf_{z in C}|lambda x +(1-lambda)y-z| nleq lambda inf_{z in C} | x -z| + (1-lambda) inf_{z in C} | y-z|
$$
Or maybe my initial way to prove the convexity is wrong. Can you complete my proof or show the claim using another way?
convex-analysis convex-optimization convex-geometry
$endgroup$
add a comment |
$begingroup$
Show that
$$
g(x)=inf_{z in C}|x-z|
$$
where $g:mathbb{R}^n rightarrow mathbb{R}$, $C$ is a convex set in $mathbb{R}^n$ (nor close neither bounded), and $|cdot|$ is a norm on $mathbb{R}^n$.
Let $x,y$ be in $mathbb{R}^n$. We need to show that
$$
g(lambda x +(1-lambda)y) leq lambda g(x)+ (1-lambda)g(y) tag{1}
$$
I tried the following:
$$
|lambda x +(1-lambda)y-z| leq lambda| x -z| + (1-lambda)| y-z| ,, forall {z in C}
$$
Since
$$
g(lambda x +(1-lambda)y)=inf_{z in C}|lambda x +(1-lambda)y-z| leq |lambda x +(1-lambda)y-z| ,, forall {z in C}
$$
So
$$
g(lambda x +(1-lambda)y)=inf_{z in C}|lambda x +(1-lambda)y-z| leq lambda| x -z| + (1-lambda)| y-z| ,, forall {z in C}
$$
I do not know how to handle the right hand side and apply infimum in a right way because the following is not correct in general
$$
inf_{z in C}|lambda x +(1-lambda)y-z| nleq lambda inf_{z in C} | x -z| + (1-lambda) inf_{z in C} | y-z|
$$
Or maybe my initial way to prove the convexity is wrong. Can you complete my proof or show the claim using another way?
convex-analysis convex-optimization convex-geometry
$endgroup$
$begingroup$
Hint: you can prove this for any jointly convex function $f(x,z)$, not just for $f(x,z) = ||x-z||$.
$endgroup$
– LinAlg
Dec 2 '18 at 23:44
add a comment |
$begingroup$
Show that
$$
g(x)=inf_{z in C}|x-z|
$$
where $g:mathbb{R}^n rightarrow mathbb{R}$, $C$ is a convex set in $mathbb{R}^n$ (nor close neither bounded), and $|cdot|$ is a norm on $mathbb{R}^n$.
Let $x,y$ be in $mathbb{R}^n$. We need to show that
$$
g(lambda x +(1-lambda)y) leq lambda g(x)+ (1-lambda)g(y) tag{1}
$$
I tried the following:
$$
|lambda x +(1-lambda)y-z| leq lambda| x -z| + (1-lambda)| y-z| ,, forall {z in C}
$$
Since
$$
g(lambda x +(1-lambda)y)=inf_{z in C}|lambda x +(1-lambda)y-z| leq |lambda x +(1-lambda)y-z| ,, forall {z in C}
$$
So
$$
g(lambda x +(1-lambda)y)=inf_{z in C}|lambda x +(1-lambda)y-z| leq lambda| x -z| + (1-lambda)| y-z| ,, forall {z in C}
$$
I do not know how to handle the right hand side and apply infimum in a right way because the following is not correct in general
$$
inf_{z in C}|lambda x +(1-lambda)y-z| nleq lambda inf_{z in C} | x -z| + (1-lambda) inf_{z in C} | y-z|
$$
Or maybe my initial way to prove the convexity is wrong. Can you complete my proof or show the claim using another way?
convex-analysis convex-optimization convex-geometry
$endgroup$
Show that
$$
g(x)=inf_{z in C}|x-z|
$$
where $g:mathbb{R}^n rightarrow mathbb{R}$, $C$ is a convex set in $mathbb{R}^n$ (nor close neither bounded), and $|cdot|$ is a norm on $mathbb{R}^n$.
Let $x,y$ be in $mathbb{R}^n$. We need to show that
$$
g(lambda x +(1-lambda)y) leq lambda g(x)+ (1-lambda)g(y) tag{1}
$$
I tried the following:
$$
|lambda x +(1-lambda)y-z| leq lambda| x -z| + (1-lambda)| y-z| ,, forall {z in C}
$$
Since
$$
g(lambda x +(1-lambda)y)=inf_{z in C}|lambda x +(1-lambda)y-z| leq |lambda x +(1-lambda)y-z| ,, forall {z in C}
$$
So
$$
g(lambda x +(1-lambda)y)=inf_{z in C}|lambda x +(1-lambda)y-z| leq lambda| x -z| + (1-lambda)| y-z| ,, forall {z in C}
$$
I do not know how to handle the right hand side and apply infimum in a right way because the following is not correct in general
$$
inf_{z in C}|lambda x +(1-lambda)y-z| nleq lambda inf_{z in C} | x -z| + (1-lambda) inf_{z in C} | y-z|
$$
Or maybe my initial way to prove the convexity is wrong. Can you complete my proof or show the claim using another way?
convex-analysis convex-optimization convex-geometry
convex-analysis convex-optimization convex-geometry
asked Dec 2 '18 at 23:16
SaeedSaeed
928310
928310
$begingroup$
Hint: you can prove this for any jointly convex function $f(x,z)$, not just for $f(x,z) = ||x-z||$.
$endgroup$
– LinAlg
Dec 2 '18 at 23:44
add a comment |
$begingroup$
Hint: you can prove this for any jointly convex function $f(x,z)$, not just for $f(x,z) = ||x-z||$.
$endgroup$
– LinAlg
Dec 2 '18 at 23:44
$begingroup$
Hint: you can prove this for any jointly convex function $f(x,z)$, not just for $f(x,z) = ||x-z||$.
$endgroup$
– LinAlg
Dec 2 '18 at 23:44
$begingroup$
Hint: you can prove this for any jointly convex function $f(x,z)$, not just for $f(x,z) = ||x-z||$.
$endgroup$
– LinAlg
Dec 2 '18 at 23:44
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint: try starting from the opposite direction, consider the subadditivity of the infimum and see if you can show it that way
$endgroup$
$begingroup$
Your statement is not an answer, please write it as a comment and delete your answer.
$endgroup$
– Saeed
Dec 3 '18 at 4:17
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%2f3023357%2fshow-minimum-distance-to-a-convex-set-is-a-convex-function%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: try starting from the opposite direction, consider the subadditivity of the infimum and see if you can show it that way
$endgroup$
$begingroup$
Your statement is not an answer, please write it as a comment and delete your answer.
$endgroup$
– Saeed
Dec 3 '18 at 4:17
add a comment |
$begingroup$
Hint: try starting from the opposite direction, consider the subadditivity of the infimum and see if you can show it that way
$endgroup$
$begingroup$
Your statement is not an answer, please write it as a comment and delete your answer.
$endgroup$
– Saeed
Dec 3 '18 at 4:17
add a comment |
$begingroup$
Hint: try starting from the opposite direction, consider the subadditivity of the infimum and see if you can show it that way
$endgroup$
Hint: try starting from the opposite direction, consider the subadditivity of the infimum and see if you can show it that way
answered Dec 3 '18 at 2:51
svailsvail
12
12
$begingroup$
Your statement is not an answer, please write it as a comment and delete your answer.
$endgroup$
– Saeed
Dec 3 '18 at 4:17
add a comment |
$begingroup$
Your statement is not an answer, please write it as a comment and delete your answer.
$endgroup$
– Saeed
Dec 3 '18 at 4:17
$begingroup$
Your statement is not an answer, please write it as a comment and delete your answer.
$endgroup$
– Saeed
Dec 3 '18 at 4:17
$begingroup$
Your statement is not an answer, please write it as a comment and delete your answer.
$endgroup$
– Saeed
Dec 3 '18 at 4:17
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%2f3023357%2fshow-minimum-distance-to-a-convex-set-is-a-convex-function%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$
Hint: you can prove this for any jointly convex function $f(x,z)$, not just for $f(x,z) = ||x-z||$.
$endgroup$
– LinAlg
Dec 2 '18 at 23:44