Mixing
Minimize $|mathbf{x-y}|^2 $ subject to $x in $ set $S={mathbf{x} in mathbb{R}^n ;;;mid ;;;...
$begingroup$
We are given the set $S={mathbf{x} in mathbb{R}^n ;;;mid ;;; |mathbf{x-x_c}|^2leq r^2 }$ and a point $mathbf{y} in mathbb{R}^n$.
Our goal is to find point $mathbf{hat{x}}$ which minimizes $|mathbf{x-y}|_2^2$.
- If $|mathbf{x-y}|_2^2leq r^2$ then point $mathbf{y}$ lies in set and the distance is $0$
- If $|mathbf{x-y}|_2^2 > r^2$ then point $mathbf{y}$ lies somewhere outside of $S$. That means the the point in question $mathbf{hat{x}}$ must be on the set S , so it follows that $|mathbf{hat{x}-x_c}|^2=r^2$
Finally, the problem can be formulated as
begin{equation*}
begin{aligned}
& underset{x}{text{minimize}}
& & f_0(x)=|mathbf{x-y}|^2 \
& text{subject to}
& & h(x) = |mathbf{x-x_c}|^2-r^2=0
end{aligned}
end{equation*}
What optimization method can I use to solve the above problem? I have solved problems with linear equlity constraints but this problem is quadratically constrained.
Is there any way to transform the problem to be linearly constrained?
multivariable-calculus convex-analysis convex-optimization lagrange-multiplier karush-kuhn-tucker
asked Feb 1 '16 at 17:30
Dimitri CDimitri C
495722
$endgroup$
add a comment |
$begingroup$
We are given the set $S={mathbf{x} in mathbb{R}^n ;;;mid ;;; |mathbf{x-x_c}|^2leq r^2 }$ and a point $mathbf{y} in mathbb{R}^n$.
Our goal is to find point $mathbf{hat{x}}$ which minimizes $|mathbf{x-y}|_2^2$.
- If $|mathbf{x-y}|_2^2leq r^2$ then point $mathbf{y}$ lies in set and the distance is $0$
- If $|mathbf{x-y}|_2^2 > r^2$ then point $mathbf{y}$ lies somewhere outside of $S$. That means the the point in question $mathbf{hat{x}}$ must be on the set S , so it follows that $|mathbf{hat{x}-x_c}|^2=r^2$
Finally, the problem can be formulated as
begin{equation*}
begin{aligned}
& underset{x}{text{minimize}}
& & f_0(x)=|mathbf{x-y}|^2 \
& text{subject to}
& & h(x) = |mathbf{x-x_c}|^2-r^2=0
end{aligned}
end{equation*}
What optimization method can I use to solve the above problem? I have solved problems with linear equlity constraints but this problem is quadratically constrained.
Is there any way to transform the problem to be linearly constrained?
multivariable-calculus convex-analysis convex-optimization lagrange-multiplier karush-kuhn-tucker
asked Feb 1 '16 at 17:30
Dimitri CDimitri C
495722
$endgroup$
$begingroup$
But you have already the tag "lagrange-multiplier". Anyways, $h(x)=0$ if and only if $|mathbf{x-x_c}|=r$. Is this comment helpful?
$endgroup$
– John B
Feb 1 '16 at 17:34
$begingroup$
@Jonas I know the KKT conditions for the problem are $nabla f_0(mathbf{hat{x}})+lambda nabla h(mathbf{hat{x}})=0$ and $h(mathbf{hat{x}})=0$ but I am not sure how to continue.. I want to solve the problem with Newton's method but I can not with the quadratic constraint.
$endgroup$
– Dimitri C
Feb 1 '16 at 17:40
add a comment |
$begingroup$
We are given the set $S={mathbf{x} in mathbb{R}^n ;;;mid ;;; |mathbf{x-x_c}|^2leq r^2 }$ and a point $mathbf{y} in mathbb{R}^n$.
Our goal is to find point $mathbf{hat{x}}$ which minimizes $|mathbf{x-y}|_2^2$.
- If $|mathbf{x-y}|_2^2leq r^2$ then point $mathbf{y}$ lies in set and the distance is $0$
- If $|mathbf{x-y}|_2^2 > r^2$ then point $mathbf{y}$ lies somewhere outside of $S$. That means the the point in question $mathbf{hat{x}}$ must be on the set S , so it follows that $|mathbf{hat{x}-x_c}|^2=r^2$
Finally, the problem can be formulated as
begin{equation*}
begin{aligned}
& underset{x}{text{minimize}}
& & f_0(x)=|mathbf{x-y}|^2 \
& text{subject to}
& & h(x) = |mathbf{x-x_c}|^2-r^2=0
end{aligned}
end{equation*}
What optimization method can I use to solve the above problem? I have solved problems with linear equlity constraints but this problem is quadratically constrained.
Is there any way to transform the problem to be linearly constrained?
multivariable-calculus convex-analysis convex-optimization lagrange-multiplier karush-kuhn-tucker
asked Feb 1 '16 at 17:30
Dimitri CDimitri C
495722
$endgroup$
We are given the set $S={mathbf{x} in mathbb{R}^n ;;;mid ;;; |mathbf{x-x_c}|^2leq r^2 }$ and a point $mathbf{y} in mathbb{R}^n$.
Our goal is to find point $mathbf{hat{x}}$ which minimizes $|mathbf{x-y}|_2^2$.
- If $|mathbf{x-y}|_2^2leq r^2$ then point $mathbf{y}$ lies in set and the distance is $0$
- If $|mathbf{x-y}|_2^2 > r^2$ then point $mathbf{y}$ lies somewhere outside of $S$. That means the the point in question $mathbf{hat{x}}$ must be on the set S , so it follows that $|mathbf{hat{x}-x_c}|^2=r^2$
Finally, the problem can be formulated as
begin{equation*}
begin{aligned}
& underset{x}{text{minimize}}
& & f_0(x)=|mathbf{x-y}|^2 \
& text{subject to}
& & h(x) = |mathbf{x-x_c}|^2-r^2=0
end{aligned}
end{equation*}
What optimization method can I use to solve the above problem? I have solved problems with linear equlity constraints but this problem is quadratically constrained.
Is there any way to transform the problem to be linearly constrained?
multivariable-calculus convex-analysis convex-optimization lagrange-multiplier karush-kuhn-tucker
multivariable-calculus convex-analysis convex-optimization lagrange-multiplier karush-kuhn-tucker
asked Feb 1 '16 at 17:30
Dimitri CDimitri C
495722
asked Feb 1 '16 at 17:30
Dimitri CDimitri C
495722
asked Feb 1 '16 at 17:30
Dimitri CDimitri C
495722
asked Feb 1 '16 at 17:30
Dimitri CDimitri C
495722
asked Feb 1 '16 at 17:30
Dimitri CDimitri C
495722
495722
$begingroup$
But you have already the tag "lagrange-multiplier". Anyways, $h(x)=0$ if and only if $|mathbf{x-x_c}|=r$. Is this comment helpful?
$endgroup$
– John B
Feb 1 '16 at 17:34
$begingroup$
@Jonas I know the KKT conditions for the problem are $nabla f_0(mathbf{hat{x}})+lambda nabla h(mathbf{hat{x}})=0$ and $h(mathbf{hat{x}})=0$ but I am not sure how to continue.. I want to solve the problem with Newton's method but I can not with the quadratic constraint.
$endgroup$
– Dimitri C
Feb 1 '16 at 17:40
add a comment |
$begingroup$
But you have already the tag "lagrange-multiplier". Anyways, $h(x)=0$ if and only if $|mathbf{x-x_c}|=r$. Is this comment helpful?
$endgroup$
– John B
Feb 1 '16 at 17:34
$begingroup$
@Jonas I know the KKT conditions for the problem are $nabla f_0(mathbf{hat{x}})+lambda nabla h(mathbf{hat{x}})=0$ and $h(mathbf{hat{x}})=0$ but I am not sure how to continue.. I want to solve the problem with Newton's method but I can not with the quadratic constraint.
$endgroup$
– Dimitri C
Feb 1 '16 at 17:40
$begingroup$
But you have already the tag "lagrange-multiplier". Anyways, $h(x)=0$ if and only if $|mathbf{x-x_c}|=r$. Is this comment helpful?
$endgroup$
– John B
Feb 1 '16 at 17:34
$begingroup$
But you have already the tag "lagrange-multiplier". Anyways, $h(x)=0$ if and only if $|mathbf{x-x_c}|=r$. Is this comment helpful?
$endgroup$
– John B
Feb 1 '16 at 17:34
$begingroup$
@Jonas I know the KKT conditions for the problem are $nabla f_0(mathbf{hat{x}})+lambda nabla h(mathbf{hat{x}})=0$ and $h(mathbf{hat{x}})=0$ but I am not sure how to continue.. I want to solve the problem with Newton's method but I can not with the quadratic constraint.
$endgroup$
– Dimitri C
Feb 1 '16 at 17:40
$begingroup$
@Jonas I know the KKT conditions for the problem are $nabla f_0(mathbf{hat{x}})+lambda nabla h(mathbf{hat{x}})=0$ and $h(mathbf{hat{x}})=0$ but I am not sure how to continue.. I want to solve the problem with Newton's method but I can not with the quadratic constraint.
$endgroup$
– Dimitri C
Feb 1 '16 at 17:40
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The projection onto balls is well known and has a closed form.
As observed, when you are in the ball, then $hat{x}=y$.
If $y$ is outside the ball, then move on the linesegment
connecting $y$ and the center $x_c$ until you hit the boundary
of the ball:
$$ hat{x} = x_c + rfrac{y-x_c}{|y-x_c|}.$$
answered Jan 31 at 22:29
max_zornmax_zorn
3,44061429
$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%2f1636182%2fminimize-mathbfx-y-2-subject-to-x-in-set-s-mathbfx-in-math%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$
The projection onto balls is well known and has a closed form.
As observed, when you are in the ball, then $hat{x}=y$.
If $y$ is outside the ball, then move on the linesegment
connecting $y$ and the center $x_c$ until you hit the boundary
of the ball:
$$ hat{x} = x_c + rfrac{y-x_c}{|y-x_c|}.$$
answered Jan 31 at 22:29
max_zornmax_zorn
3,44061429
$endgroup$
add a comment |
$begingroup$
The projection onto balls is well known and has a closed form.
As observed, when you are in the ball, then $hat{x}=y$.
If $y$ is outside the ball, then move on the linesegment
connecting $y$ and the center $x_c$ until you hit the boundary
of the ball:
$$ hat{x} = x_c + rfrac{y-x_c}{|y-x_c|}.$$
answered Jan 31 at 22:29
max_zornmax_zorn
3,44061429
$endgroup$
add a comment |
$begingroup$
The projection onto balls is well known and has a closed form.
As observed, when you are in the ball, then $hat{x}=y$.
If $y$ is outside the ball, then move on the linesegment
connecting $y$ and the center $x_c$ until you hit the boundary
of the ball:
$$ hat{x} = x_c + rfrac{y-x_c}{|y-x_c|}.$$
answered Jan 31 at 22:29
max_zornmax_zorn
3,44061429
$endgroup$
The projection onto balls is well known and has a closed form.
As observed, when you are in the ball, then $hat{x}=y$.
If $y$ is outside the ball, then move on the linesegment
connecting $y$ and the center $x_c$ until you hit the boundary
of the ball:
$$ hat{x} = x_c + rfrac{y-x_c}{|y-x_c|}.$$
answered Jan 31 at 22:29
max_zornmax_zorn
3,44061429
answered Jan 31 at 22:29
max_zornmax_zorn
3,44061429
answered Jan 31 at 22:29
max_zornmax_zorn
3,44061429
answered Jan 31 at 22:29
max_zornmax_zorn
3,44061429
3,44061429
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%2f1636182%2fminimize-mathbfx-y-2-subject-to-x-in-set-s-mathbfx-in-math%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$
But you have already the tag "lagrange-multiplier". Anyways, $h(x)=0$ if and only if $|mathbf{x-x_c}|=r$. Is this comment helpful?
$endgroup$
– John B
Feb 1 '16 at 17:34
$begingroup$
@Jonas I know the KKT conditions for the problem are $nabla f_0(mathbf{hat{x}})+lambda nabla h(mathbf{hat{x}})=0$ and $h(mathbf{hat{x}})=0$ but I am not sure how to continue.. I want to solve the problem with Newton's method but I can not with the quadratic constraint.
$endgroup$
– Dimitri C
Feb 1 '16 at 17:40