Prove that the dual of the norm approximation problem has the given form.
$begingroup$
Consider the norm approximation:
$$
(P) begin{cases}
min_{x in mathbb{R}^n} Vert Ax - b Vert
end{cases}
$$
where $A in mathcal{M}_{m times n}(mathbb{R})$ and $b in mathbb{R}^m$.
Part (1) — Write $(P)$ with an equality constraint.
Attempt:
Since $Vert Ax -bVert geq 0$ then add the following constraint:
$$
(P) begin{cases}
min_{x in mathbb{R}^n} Vert Ax - b Vert,\
text{s.t.} ;; Ax-b=0
end{cases}
$$
I am not sure if this is correct, or why this could be correct. It was pure intuition because the smallest value the norm can attain is $0$.
Part (2) — Prove that the dual of $(P)$ is the following:
$$
(P^*) begin{cases}
max_{nu} ; langle b, nu rangle, \
text{s.t. } ; A^top nu = 0, ;; Vert nu Vert_* leq 1.
end{cases}
$$
The dual norm is defined as $Vert nu Vert_* = sup_{Vert x Vert leq 1} langle nu, xrangle $.
Attempt:
The Lagrangian is $L(x,nu) = Vert Ax -bVert + langle nu,Ax-b rangle$
I know that the Lagrangian dual problem is defined as:
$$
(P^*) begin{cases}
max_{(lambda,nu)} ; inf_{x in mathbb{R^n}} L(x,lambda,
nu)\
text{s.t. } ; lambda geq 0
end{cases}
$$
Where $lambda$ are the multipliers of the inequality constraints.
But I do not have any inequality constraints.
Can the $Ax - b = 0$ constraint be counted as $Ax - b geq 0$ and $Ax - b leq 0$?
Any help is greatly appreciated. I am really unsure of how to proceed.
optimization convex-analysis convex-optimization
asked Dec 7 '18 at 12:43
ex.nihilex.nihil
215111
$endgroup$
add a comment |
$begingroup$
Consider the norm approximation:
$$
(P) begin{cases}
min_{x in mathbb{R}^n} Vert Ax - b Vert
end{cases}
$$
where $A in mathcal{M}_{m times n}(mathbb{R})$ and $b in mathbb{R}^m$.
Part (1) — Write $(P)$ with an equality constraint.
Attempt:
Since $Vert Ax -bVert geq 0$ then add the following constraint:
$$
(P) begin{cases}
min_{x in mathbb{R}^n} Vert Ax - b Vert,\
text{s.t.} ;; Ax-b=0
end{cases}
$$
I am not sure if this is correct, or why this could be correct. It was pure intuition because the smallest value the norm can attain is $0$.
Part (2) — Prove that the dual of $(P)$ is the following:
$$
(P^*) begin{cases}
max_{nu} ; langle b, nu rangle, \
text{s.t. } ; A^top nu = 0, ;; Vert nu Vert_* leq 1.
end{cases}
$$
The dual norm is defined as $Vert nu Vert_* = sup_{Vert x Vert leq 1} langle nu, xrangle $.
Attempt:
The Lagrangian is $L(x,nu) = Vert Ax -bVert + langle nu,Ax-b rangle$
I know that the Lagrangian dual problem is defined as:
$$
(P^*) begin{cases}
max_{(lambda,nu)} ; inf_{x in mathbb{R^n}} L(x,lambda,
nu)\
text{s.t. } ; lambda geq 0
end{cases}
$$
Where $lambda$ are the multipliers of the inequality constraints.
But I do not have any inequality constraints.
Can the $Ax - b = 0$ constraint be counted as $Ax - b geq 0$ and $Ax - b leq 0$?
Any help is greatly appreciated. I am really unsure of how to proceed.
optimization convex-analysis convex-optimization
asked Dec 7 '18 at 12:43
ex.nihilex.nihil
215111
$endgroup$
3
$begingroup$
I think what they mean in part 1 is to reformulate the problem as $min|u|$ subject to $u=Ax-b$, and proceed with part 2 from there. What you did is pulling a most likely infeasible constraint out of the blue.
$endgroup$
– Michal Adamaszek
Dec 7 '18 at 12:48
add a comment |
$begingroup$
Consider the norm approximation:
$$
(P) begin{cases}
min_{x in mathbb{R}^n} Vert Ax - b Vert
end{cases}
$$
where $A in mathcal{M}_{m times n}(mathbb{R})$ and $b in mathbb{R}^m$.
Part (1) — Write $(P)$ with an equality constraint.
Attempt:
Since $Vert Ax -bVert geq 0$ then add the following constraint:
$$
(P) begin{cases}
min_{x in mathbb{R}^n} Vert Ax - b Vert,\
text{s.t.} ;; Ax-b=0
end{cases}
$$
I am not sure if this is correct, or why this could be correct. It was pure intuition because the smallest value the norm can attain is $0$.
Part (2) — Prove that the dual of $(P)$ is the following:
$$
(P^*) begin{cases}
max_{nu} ; langle b, nu rangle, \
text{s.t. } ; A^top nu = 0, ;; Vert nu Vert_* leq 1.
end{cases}
$$
The dual norm is defined as $Vert nu Vert_* = sup_{Vert x Vert leq 1} langle nu, xrangle $.
Attempt:
The Lagrangian is $L(x,nu) = Vert Ax -bVert + langle nu,Ax-b rangle$
I know that the Lagrangian dual problem is defined as:
$$
(P^*) begin{cases}
max_{(lambda,nu)} ; inf_{x in mathbb{R^n}} L(x,lambda,
nu)\
text{s.t. } ; lambda geq 0
end{cases}
$$
Where $lambda$ are the multipliers of the inequality constraints.
But I do not have any inequality constraints.
Can the $Ax - b = 0$ constraint be counted as $Ax - b geq 0$ and $Ax - b leq 0$?
Any help is greatly appreciated. I am really unsure of how to proceed.
optimization convex-analysis convex-optimization
asked Dec 7 '18 at 12:43
ex.nihilex.nihil
215111
$endgroup$
Consider the norm approximation:
$$
(P) begin{cases}
min_{x in mathbb{R}^n} Vert Ax - b Vert
end{cases}
$$
where $A in mathcal{M}_{m times n}(mathbb{R})$ and $b in mathbb{R}^m$.
Part (1) — Write $(P)$ with an equality constraint.
Attempt:
Since $Vert Ax -bVert geq 0$ then add the following constraint:
$$
(P) begin{cases}
min_{x in mathbb{R}^n} Vert Ax - b Vert,\
text{s.t.} ;; Ax-b=0
end{cases}
$$
I am not sure if this is correct, or why this could be correct. It was pure intuition because the smallest value the norm can attain is $0$.
Part (2) — Prove that the dual of $(P)$ is the following:
$$
(P^*) begin{cases}
max_{nu} ; langle b, nu rangle, \
text{s.t. } ; A^top nu = 0, ;; Vert nu Vert_* leq 1.
end{cases}
$$
The dual norm is defined as $Vert nu Vert_* = sup_{Vert x Vert leq 1} langle nu, xrangle $.
Attempt:
The Lagrangian is $L(x,nu) = Vert Ax -bVert + langle nu,Ax-b rangle$
I know that the Lagrangian dual problem is defined as:
$$
(P^*) begin{cases}
max_{(lambda,nu)} ; inf_{x in mathbb{R^n}} L(x,lambda,
nu)\
text{s.t. } ; lambda geq 0
end{cases}
$$
Where $lambda$ are the multipliers of the inequality constraints.
But I do not have any inequality constraints.
Can the $Ax - b = 0$ constraint be counted as $Ax - b geq 0$ and $Ax - b leq 0$?
Any help is greatly appreciated. I am really unsure of how to proceed.
optimization convex-analysis convex-optimization
optimization convex-analysis convex-optimization
asked Dec 7 '18 at 12:43
ex.nihilex.nihil
215111
asked Dec 7 '18 at 12:43
ex.nihilex.nihil
215111
asked Dec 7 '18 at 12:43
ex.nihilex.nihil
215111
asked Dec 7 '18 at 12:43
ex.nihilex.nihil
215111
asked Dec 7 '18 at 12:43
ex.nihilex.nihil
215111
215111
3
$begingroup$
I think what they mean in part 1 is to reformulate the problem as $min|u|$ subject to $u=Ax-b$, and proceed with part 2 from there. What you did is pulling a most likely infeasible constraint out of the blue.
$endgroup$
– Michal Adamaszek
Dec 7 '18 at 12:48
add a comment |
3
$begingroup$
I think what they mean in part 1 is to reformulate the problem as $min|u|$ subject to $u=Ax-b$, and proceed with part 2 from there. What you did is pulling a most likely infeasible constraint out of the blue.
$endgroup$
– Michal Adamaszek
Dec 7 '18 at 12:48
3
3
$begingroup$
I think what they mean in part 1 is to reformulate the problem as $min|u|$ subject to $u=Ax-b$, and proceed with part 2 from there. What you did is pulling a most likely infeasible constraint out of the blue.
$endgroup$
– Michal Adamaszek
Dec 7 '18 at 12:48
$begingroup$
I think what they mean in part 1 is to reformulate the problem as $min|u|$ subject to $u=Ax-b$, and proceed with part 2 from there. What you did is pulling a most likely infeasible constraint out of the blue.
$endgroup$
– Michal Adamaszek
Dec 7 '18 at 12:48
add a comment |
0
active
oldest
votes
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%2f3029858%2fprove-that-the-dual-of-the-norm-approximation-problem-has-the-given-form%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3029858%2fprove-that-the-dual-of-the-norm-approximation-problem-has-the-given-form%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
3
$begingroup$
I think what they mean in part 1 is to reformulate the problem as $min|u|$ subject to $u=Ax-b$, and proceed with part 2 from there. What you did is pulling a most likely infeasible constraint out of the blue.
$endgroup$
– Michal Adamaszek
Dec 7 '18 at 12:48