Mixing
Proving convexity using definition of symmetric positive semidefinite
$begingroup$
I have a $f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}$.
$boldsymbol{Q}$ is an $n times n$ symmetric positive semidefinite matrix. How can I show that $f(boldsymbol{x})$ is convex on the domain $R^n$?
Attempt:
By definition of convex, for any $x,yinmathbb R$, we have
$$f(frac{x+y}2)leqfrac12(f(x)+f(y))$$
Thus it is sufficient to reduce and prove that
$$frac12(x+y)^TQ(x+y)leq x^TQx+y^TQy\
x^TQy+y^TQxleq x^TQx+y^TQy$$
Namely
$$(x-y)^TQ(x-y)geq0$$
At this point I am stuck on how to use positive semi-definite - assuming my logic is sound up to this point.
convex-optimization
asked Jan 30 '17 at 7:38
ozarkaozarka
1949
$endgroup$
|
show 1 more comment
$begingroup$
I have a $f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}$.
$boldsymbol{Q}$ is an $n times n$ symmetric positive semidefinite matrix. How can I show that $f(boldsymbol{x})$ is convex on the domain $R^n$?
Attempt:
By definition of convex, for any $x,yinmathbb R$, we have
$$f(frac{x+y}2)leqfrac12(f(x)+f(y))$$
Thus it is sufficient to reduce and prove that
$$frac12(x+y)^TQ(x+y)leq x^TQx+y^TQy\
x^TQy+y^TQxleq x^TQx+y^TQy$$
Namely
$$(x-y)^TQ(x-y)geq0$$
At this point I am stuck on how to use positive semi-definite - assuming my logic is sound up to this point.
convex-optimization
asked Jan 30 '17 at 7:38
ozarkaozarka
1949
$endgroup$
$begingroup$
What does positive semidefinite mean?
$endgroup$
– littleO
Jan 30 '17 at 7:48
$begingroup$
It means that the scalar $x^T Q x$ is guaranteed to be non-negative. I guess I'm stuck on what more I have to show. Do I just state the definition and end it there?
$endgroup$
– ozarka
Jan 30 '17 at 7:50
$begingroup$
Is it correct to use the definition of convexity that I used? I think this is really where I am struggling.
$endgroup$
– ozarka
Jan 30 '17 at 7:53
$begingroup$
If you have already proved that this definition of convexity is equivalent to the standard definition, or if you are allowed to assume this fact, then you can finish off your proof just by invoking the definition of positive semidefinite in the final step.
$endgroup$
– littleO
Jan 30 '17 at 10:56
1
$begingroup$
A different proof is to note that $f$ is differentiable on $mathbb R^n$ and $nabla^2 f(x) = 2Q$ is positive semidefinite for all $x$. Since the Hessian of $f$ is positive semidefinite for all $x$, it follows that $f$ is convex.
$endgroup$
– littleO
Jan 30 '17 at 10:57
|
show 1 more comment
$begingroup$
I have a $f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}$.
$boldsymbol{Q}$ is an $n times n$ symmetric positive semidefinite matrix. How can I show that $f(boldsymbol{x})$ is convex on the domain $R^n$?
Attempt:
By definition of convex, for any $x,yinmathbb R$, we have
$$f(frac{x+y}2)leqfrac12(f(x)+f(y))$$
Thus it is sufficient to reduce and prove that
$$frac12(x+y)^TQ(x+y)leq x^TQx+y^TQy\
x^TQy+y^TQxleq x^TQx+y^TQy$$
Namely
$$(x-y)^TQ(x-y)geq0$$
At this point I am stuck on how to use positive semi-definite - assuming my logic is sound up to this point.
convex-optimization
asked Jan 30 '17 at 7:38
ozarkaozarka
1949
$endgroup$
I have a $f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}$.
$boldsymbol{Q}$ is an $n times n$ symmetric positive semidefinite matrix. How can I show that $f(boldsymbol{x})$ is convex on the domain $R^n$?
Attempt:
By definition of convex, for any $x,yinmathbb R$, we have
$$f(frac{x+y}2)leqfrac12(f(x)+f(y))$$
Thus it is sufficient to reduce and prove that
$$frac12(x+y)^TQ(x+y)leq x^TQx+y^TQy\
x^TQy+y^TQxleq x^TQx+y^TQy$$
Namely
$$(x-y)^TQ(x-y)geq0$$
At this point I am stuck on how to use positive semi-definite - assuming my logic is sound up to this point.
convex-optimization
convex-optimization
asked Jan 30 '17 at 7:38
ozarkaozarka
1949
asked Jan 30 '17 at 7:38
ozarkaozarka
1949
asked Jan 30 '17 at 7:38
ozarkaozarka
1949
asked Jan 30 '17 at 7:38
ozarkaozarka
1949
asked Jan 30 '17 at 7:38
ozarkaozarka
1949
1949
$begingroup$
What does positive semidefinite mean?
$endgroup$
– littleO
Jan 30 '17 at 7:48
$begingroup$
It means that the scalar $x^T Q x$ is guaranteed to be non-negative. I guess I'm stuck on what more I have to show. Do I just state the definition and end it there?
$endgroup$
– ozarka
Jan 30 '17 at 7:50
$begingroup$
Is it correct to use the definition of convexity that I used? I think this is really where I am struggling.
$endgroup$
– ozarka
Jan 30 '17 at 7:53
$begingroup$
If you have already proved that this definition of convexity is equivalent to the standard definition, or if you are allowed to assume this fact, then you can finish off your proof just by invoking the definition of positive semidefinite in the final step.
$endgroup$
– littleO
Jan 30 '17 at 10:56
1
$begingroup$
A different proof is to note that $f$ is differentiable on $mathbb R^n$ and $nabla^2 f(x) = 2Q$ is positive semidefinite for all $x$. Since the Hessian of $f$ is positive semidefinite for all $x$, it follows that $f$ is convex.
$endgroup$
– littleO
Jan 30 '17 at 10:57
|
show 1 more comment
$begingroup$
What does positive semidefinite mean?
$endgroup$
– littleO
Jan 30 '17 at 7:48
$begingroup$
It means that the scalar $x^T Q x$ is guaranteed to be non-negative. I guess I'm stuck on what more I have to show. Do I just state the definition and end it there?
$endgroup$
– ozarka
Jan 30 '17 at 7:50
$begingroup$
Is it correct to use the definition of convexity that I used? I think this is really where I am struggling.
$endgroup$
– ozarka
Jan 30 '17 at 7:53
$begingroup$
If you have already proved that this definition of convexity is equivalent to the standard definition, or if you are allowed to assume this fact, then you can finish off your proof just by invoking the definition of positive semidefinite in the final step.
$endgroup$
– littleO
Jan 30 '17 at 10:56
1
$begingroup$
A different proof is to note that $f$ is differentiable on $mathbb R^n$ and $nabla^2 f(x) = 2Q$ is positive semidefinite for all $x$. Since the Hessian of $f$ is positive semidefinite for all $x$, it follows that $f$ is convex.
$endgroup$
– littleO
Jan 30 '17 at 10:57
$begingroup$
What does positive semidefinite mean?
$endgroup$
– littleO
Jan 30 '17 at 7:48
$begingroup$
What does positive semidefinite mean?
$endgroup$
– littleO
Jan 30 '17 at 7:48
$begingroup$
It means that the scalar $x^T Q x$ is guaranteed to be non-negative. I guess I'm stuck on what more I have to show. Do I just state the definition and end it there?
$endgroup$
– ozarka
Jan 30 '17 at 7:50
$begingroup$
It means that the scalar $x^T Q x$ is guaranteed to be non-negative. I guess I'm stuck on what more I have to show. Do I just state the definition and end it there?
$endgroup$
– ozarka
Jan 30 '17 at 7:50
$begingroup$
Is it correct to use the definition of convexity that I used? I think this is really where I am struggling.
$endgroup$
– ozarka
Jan 30 '17 at 7:53
$begingroup$
Is it correct to use the definition of convexity that I used? I think this is really where I am struggling.
$endgroup$
– ozarka
Jan 30 '17 at 7:53
$begingroup$
If you have already proved that this definition of convexity is equivalent to the standard definition, or if you are allowed to assume this fact, then you can finish off your proof just by invoking the definition of positive semidefinite in the final step.
$endgroup$
– littleO
Jan 30 '17 at 10:56
$begingroup$
If you have already proved that this definition of convexity is equivalent to the standard definition, or if you are allowed to assume this fact, then you can finish off your proof just by invoking the definition of positive semidefinite in the final step.
$endgroup$
– littleO
Jan 30 '17 at 10:56
1
1
$begingroup$
A different proof is to note that $f$ is differentiable on $mathbb R^n$ and $nabla^2 f(x) = 2Q$ is positive semidefinite for all $x$. Since the Hessian of $f$ is positive semidefinite for all $x$, it follows that $f$ is convex.
$endgroup$
– littleO
Jan 30 '17 at 10:57
$begingroup$
A different proof is to note that $f$ is differentiable on $mathbb R^n$ and $nabla^2 f(x) = 2Q$ is positive semidefinite for all $x$. Since the Hessian of $f$ is positive semidefinite for all $x$, it follows that $f$ is convex.
$endgroup$
– littleO
Jan 30 '17 at 10:57
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
(a) For $;f:mathbb{R}to mathbb{R}$, $;f(x)=x^2$ we verify that $f$ is convex. In fact,
$$(alpha x+(1-alpha )y)^2leq alpha x^2+(1-alpha)y^2 Leftrightarrow\
alpha^2x^2+2alpha (1-alpha)xy+(1-alpha)^2y^2-alpha x^2-(1-alpha)y^2leq 0Leftrightarrow\(alpha^2-alpha)x^2+(alpha^2-alpha)y^2+ 2(alpha^2-alpha)xyleq 0Leftrightarrow\
(alpha^2-alpha)(x+y)^2leq 0.$$ The last inequality is verified because $alpha^2-alpha leq 0$ for all $alphain [0,1]$. That is, $$f(alpha x+(1-alpha )y)leq alpha f(x)+(1-alpha)f(y)quad forall{x,y}in{V},; forall{alpha }in{[0,1]}.$$ and $f$ is a convex function.
(b) For $;f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x};$ with $;boldsymbol{Q};$ positive semidefinite, we can express
$$f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}=boldsymbol{(boldsymbol{P}x})^{boldsymbol{T}} boldsymbol{D} (boldsymbol{P}boldsymbol{x})=x_1^2+cdots+x_r^2$$ and apply (a).
answered Jan 30 '17 at 8:46
Fernando RevillaFernando Revilla
3,332520
$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%2f2120528%2fproving-convexity-using-definition-of-symmetric-positive-semidefinite%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$
(a) For $;f:mathbb{R}to mathbb{R}$, $;f(x)=x^2$ we verify that $f$ is convex. In fact,
$$(alpha x+(1-alpha )y)^2leq alpha x^2+(1-alpha)y^2 Leftrightarrow\
alpha^2x^2+2alpha (1-alpha)xy+(1-alpha)^2y^2-alpha x^2-(1-alpha)y^2leq 0Leftrightarrow\(alpha^2-alpha)x^2+(alpha^2-alpha)y^2+ 2(alpha^2-alpha)xyleq 0Leftrightarrow\
(alpha^2-alpha)(x+y)^2leq 0.$$ The last inequality is verified because $alpha^2-alpha leq 0$ for all $alphain [0,1]$. That is, $$f(alpha x+(1-alpha )y)leq alpha f(x)+(1-alpha)f(y)quad forall{x,y}in{V},; forall{alpha }in{[0,1]}.$$ and $f$ is a convex function.
(b) For $;f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x};$ with $;boldsymbol{Q};$ positive semidefinite, we can express
$$f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}=boldsymbol{(boldsymbol{P}x})^{boldsymbol{T}} boldsymbol{D} (boldsymbol{P}boldsymbol{x})=x_1^2+cdots+x_r^2$$ and apply (a).
answered Jan 30 '17 at 8:46
Fernando RevillaFernando Revilla
3,332520
$endgroup$
add a comment |
$begingroup$
(a) For $;f:mathbb{R}to mathbb{R}$, $;f(x)=x^2$ we verify that $f$ is convex. In fact,
$$(alpha x+(1-alpha )y)^2leq alpha x^2+(1-alpha)y^2 Leftrightarrow\
alpha^2x^2+2alpha (1-alpha)xy+(1-alpha)^2y^2-alpha x^2-(1-alpha)y^2leq 0Leftrightarrow\(alpha^2-alpha)x^2+(alpha^2-alpha)y^2+ 2(alpha^2-alpha)xyleq 0Leftrightarrow\
(alpha^2-alpha)(x+y)^2leq 0.$$ The last inequality is verified because $alpha^2-alpha leq 0$ for all $alphain [0,1]$. That is, $$f(alpha x+(1-alpha )y)leq alpha f(x)+(1-alpha)f(y)quad forall{x,y}in{V},; forall{alpha }in{[0,1]}.$$ and $f$ is a convex function.
(b) For $;f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x};$ with $;boldsymbol{Q};$ positive semidefinite, we can express
$$f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}=boldsymbol{(boldsymbol{P}x})^{boldsymbol{T}} boldsymbol{D} (boldsymbol{P}boldsymbol{x})=x_1^2+cdots+x_r^2$$ and apply (a).
answered Jan 30 '17 at 8:46
Fernando RevillaFernando Revilla
3,332520
$endgroup$
add a comment |
$begingroup$
(a) For $;f:mathbb{R}to mathbb{R}$, $;f(x)=x^2$ we verify that $f$ is convex. In fact,
$$(alpha x+(1-alpha )y)^2leq alpha x^2+(1-alpha)y^2 Leftrightarrow\
alpha^2x^2+2alpha (1-alpha)xy+(1-alpha)^2y^2-alpha x^2-(1-alpha)y^2leq 0Leftrightarrow\(alpha^2-alpha)x^2+(alpha^2-alpha)y^2+ 2(alpha^2-alpha)xyleq 0Leftrightarrow\
(alpha^2-alpha)(x+y)^2leq 0.$$ The last inequality is verified because $alpha^2-alpha leq 0$ for all $alphain [0,1]$. That is, $$f(alpha x+(1-alpha )y)leq alpha f(x)+(1-alpha)f(y)quad forall{x,y}in{V},; forall{alpha }in{[0,1]}.$$ and $f$ is a convex function.
(b) For $;f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x};$ with $;boldsymbol{Q};$ positive semidefinite, we can express
$$f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}=boldsymbol{(boldsymbol{P}x})^{boldsymbol{T}} boldsymbol{D} (boldsymbol{P}boldsymbol{x})=x_1^2+cdots+x_r^2$$ and apply (a).
answered Jan 30 '17 at 8:46
Fernando RevillaFernando Revilla
3,332520
$endgroup$
(a) For $;f:mathbb{R}to mathbb{R}$, $;f(x)=x^2$ we verify that $f$ is convex. In fact,
$$(alpha x+(1-alpha )y)^2leq alpha x^2+(1-alpha)y^2 Leftrightarrow\
alpha^2x^2+2alpha (1-alpha)xy+(1-alpha)^2y^2-alpha x^2-(1-alpha)y^2leq 0Leftrightarrow\(alpha^2-alpha)x^2+(alpha^2-alpha)y^2+ 2(alpha^2-alpha)xyleq 0Leftrightarrow\
(alpha^2-alpha)(x+y)^2leq 0.$$ The last inequality is verified because $alpha^2-alpha leq 0$ for all $alphain [0,1]$. That is, $$f(alpha x+(1-alpha )y)leq alpha f(x)+(1-alpha)f(y)quad forall{x,y}in{V},; forall{alpha }in{[0,1]}.$$ and $f$ is a convex function.
(b) For $;f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x};$ with $;boldsymbol{Q};$ positive semidefinite, we can express
$$f(boldsymbol{x}) = boldsymbol{x}^{boldsymbol{T}} boldsymbol{Q} boldsymbol{x}=boldsymbol{(boldsymbol{P}x})^{boldsymbol{T}} boldsymbol{D} (boldsymbol{P}boldsymbol{x})=x_1^2+cdots+x_r^2$$ and apply (a).
answered Jan 30 '17 at 8:46
Fernando RevillaFernando Revilla
3,332520
edited Jan 30 '17 at 8:57
answered Jan 30 '17 at 8:46
Fernando RevillaFernando Revilla
3,332520
answered Jan 30 '17 at 8:46
Fernando RevillaFernando Revilla
3,332520
answered Jan 30 '17 at 8:46
Fernando RevillaFernando Revilla
3,332520
3,332520
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%2f2120528%2fproving-convexity-using-definition-of-symmetric-positive-semidefinite%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$
What does positive semidefinite mean?
$endgroup$
– littleO
Jan 30 '17 at 7:48
$begingroup$
It means that the scalar $x^T Q x$ is guaranteed to be non-negative. I guess I'm stuck on what more I have to show. Do I just state the definition and end it there?
$endgroup$
– ozarka
Jan 30 '17 at 7:50
$begingroup$
Is it correct to use the definition of convexity that I used? I think this is really where I am struggling.
$endgroup$
– ozarka
Jan 30 '17 at 7:53
$begingroup$
If you have already proved that this definition of convexity is equivalent to the standard definition, or if you are allowed to assume this fact, then you can finish off your proof just by invoking the definition of positive semidefinite in the final step.
$endgroup$
– littleO
Jan 30 '17 at 10:56
1
$begingroup$
A different proof is to note that $f$ is differentiable on $mathbb R^n$ and $nabla^2 f(x) = 2Q$ is positive semidefinite for all $x$. Since the Hessian of $f$ is positive semidefinite for all $x$, it follows that $f$ is convex.
$endgroup$
– littleO
Jan 30 '17 at 10:57