Mixing
Under what conditions the following constraint is convex?
$begingroup$
We know that if a matrix $mathbb{A}$ is positive definite then $tr~mathbb{A}$ is a convex function. But how can we show that the following constraint results in a convex set $$-tr~mathbb{AQ}leq 0$$ where $mathbb{Q}$ is some matrix with constant real values.
optimization convex-analysis convex-optimization
asked Jan 28 at 14:07
Frank MosesFrank Moses
1,179419
$endgroup$
add a comment |
$begingroup$
We know that if a matrix $mathbb{A}$ is positive definite then $tr~mathbb{A}$ is a convex function. But how can we show that the following constraint results in a convex set $$-tr~mathbb{AQ}leq 0$$ where $mathbb{Q}$ is some matrix with constant real values.
optimization convex-analysis convex-optimization
asked Jan 28 at 14:07
Frank MosesFrank Moses
1,179419
$endgroup$
$begingroup$
@supinf thus far I only know how to show that $tr ~mathbb{A}$ is a convex function (this is an exercise in Stephen Boyd book). But I do not know how to show that by multiplying $mathbb{A}$ by $mathbb{Q}$ it becomes a concave function.
$endgroup$
– Frank Moses
Jan 28 at 14:23
1
$begingroup$
Have you tried to write out a formula for $-mbox{tr} AQ$ in terms of the elements of $A$ and $Q$?
$endgroup$
– Brian Borchers
Jan 28 at 15:26
$begingroup$
@BrianBorchers ok now I know that its a linear function so it is both convex and concave at the same time
$endgroup$
– Frank Moses
Jan 28 at 16:04
1
$begingroup$
So, you know that $-mbox{tr}(AQ) $ is a convex function and your constraint is of the form convex function of A is less than 0. Is that enough to establish that the feasible region is convex?
$endgroup$
– Brian Borchers
Jan 28 at 16:18
$begingroup$
@BrianBorchers I think so. Here is the reason why I think so (please correct me if I am wrong). As the function on the left side is convex therefore its sublevel set is convex for any level. Since this is also true for level=0, I conclude that the constraint result in a convex set. (Please let me know if this reasoning is wrong. Thanks in advance.)
$endgroup$
– Frank Moses
Jan 28 at 16:31
add a comment |
$begingroup$
We know that if a matrix $mathbb{A}$ is positive definite then $tr~mathbb{A}$ is a convex function. But how can we show that the following constraint results in a convex set $$-tr~mathbb{AQ}leq 0$$ where $mathbb{Q}$ is some matrix with constant real values.
optimization convex-analysis convex-optimization
asked Jan 28 at 14:07
Frank MosesFrank Moses
1,179419
$endgroup$
We know that if a matrix $mathbb{A}$ is positive definite then $tr~mathbb{A}$ is a convex function. But how can we show that the following constraint results in a convex set $$-tr~mathbb{AQ}leq 0$$ where $mathbb{Q}$ is some matrix with constant real values.
optimization convex-analysis convex-optimization
optimization convex-analysis convex-optimization
asked Jan 28 at 14:07
Frank MosesFrank Moses
1,179419
asked Jan 28 at 14:07
Frank MosesFrank Moses
1,179419
edited Jan 28 at 14:20
Frank Moses
asked Jan 28 at 14:07
Frank MosesFrank Moses
1,179419
asked Jan 28 at 14:07
Frank MosesFrank Moses
1,179419
asked Jan 28 at 14:07
Frank MosesFrank Moses
1,179419
1,179419
$begingroup$
@supinf thus far I only know how to show that $tr ~mathbb{A}$ is a convex function (this is an exercise in Stephen Boyd book). But I do not know how to show that by multiplying $mathbb{A}$ by $mathbb{Q}$ it becomes a concave function.
$endgroup$
– Frank Moses
Jan 28 at 14:23
1
$begingroup$
Have you tried to write out a formula for $-mbox{tr} AQ$ in terms of the elements of $A$ and $Q$?
$endgroup$
– Brian Borchers
Jan 28 at 15:26
$begingroup$
@BrianBorchers ok now I know that its a linear function so it is both convex and concave at the same time
$endgroup$
– Frank Moses
Jan 28 at 16:04
1
$begingroup$
So, you know that $-mbox{tr}(AQ) $ is a convex function and your constraint is of the form convex function of A is less than 0. Is that enough to establish that the feasible region is convex?
$endgroup$
– Brian Borchers
Jan 28 at 16:18
$begingroup$
@BrianBorchers I think so. Here is the reason why I think so (please correct me if I am wrong). As the function on the left side is convex therefore its sublevel set is convex for any level. Since this is also true for level=0, I conclude that the constraint result in a convex set. (Please let me know if this reasoning is wrong. Thanks in advance.)
$endgroup$
– Frank Moses
Jan 28 at 16:31
add a comment |
$begingroup$
@supinf thus far I only know how to show that $tr ~mathbb{A}$ is a convex function (this is an exercise in Stephen Boyd book). But I do not know how to show that by multiplying $mathbb{A}$ by $mathbb{Q}$ it becomes a concave function.
$endgroup$
– Frank Moses
Jan 28 at 14:23
1
$begingroup$
Have you tried to write out a formula for $-mbox{tr} AQ$ in terms of the elements of $A$ and $Q$?
$endgroup$
– Brian Borchers
Jan 28 at 15:26
$begingroup$
@BrianBorchers ok now I know that its a linear function so it is both convex and concave at the same time
$endgroup$
– Frank Moses
Jan 28 at 16:04
1
$begingroup$
So, you know that $-mbox{tr}(AQ) $ is a convex function and your constraint is of the form convex function of A is less than 0. Is that enough to establish that the feasible region is convex?
$endgroup$
– Brian Borchers
Jan 28 at 16:18
$begingroup$
@BrianBorchers I think so. Here is the reason why I think so (please correct me if I am wrong). As the function on the left side is convex therefore its sublevel set is convex for any level. Since this is also true for level=0, I conclude that the constraint result in a convex set. (Please let me know if this reasoning is wrong. Thanks in advance.)
$endgroup$
– Frank Moses
Jan 28 at 16:31
$begingroup$
@supinf thus far I only know how to show that $tr ~mathbb{A}$ is a convex function (this is an exercise in Stephen Boyd book). But I do not know how to show that by multiplying $mathbb{A}$ by $mathbb{Q}$ it becomes a concave function.
$endgroup$
– Frank Moses
Jan 28 at 14:23
$begingroup$
@supinf thus far I only know how to show that $tr ~mathbb{A}$ is a convex function (this is an exercise in Stephen Boyd book). But I do not know how to show that by multiplying $mathbb{A}$ by $mathbb{Q}$ it becomes a concave function.
$endgroup$
– Frank Moses
Jan 28 at 14:23
1
1
$begingroup$
Have you tried to write out a formula for $-mbox{tr} AQ$ in terms of the elements of $A$ and $Q$?
$endgroup$
– Brian Borchers
Jan 28 at 15:26
$begingroup$
Have you tried to write out a formula for $-mbox{tr} AQ$ in terms of the elements of $A$ and $Q$?
$endgroup$
– Brian Borchers
Jan 28 at 15:26
$begingroup$
@BrianBorchers ok now I know that its a linear function so it is both convex and concave at the same time
$endgroup$
– Frank Moses
Jan 28 at 16:04
$begingroup$
@BrianBorchers ok now I know that its a linear function so it is both convex and concave at the same time
$endgroup$
– Frank Moses
Jan 28 at 16:04
1
1
$begingroup$
So, you know that $-mbox{tr}(AQ) $ is a convex function and your constraint is of the form convex function of A is less than 0. Is that enough to establish that the feasible region is convex?
$endgroup$
– Brian Borchers
Jan 28 at 16:18
$begingroup$
So, you know that $-mbox{tr}(AQ) $ is a convex function and your constraint is of the form convex function of A is less than 0. Is that enough to establish that the feasible region is convex?
$endgroup$
– Brian Borchers
Jan 28 at 16:18
$begingroup$
@BrianBorchers I think so. Here is the reason why I think so (please correct me if I am wrong). As the function on the left side is convex therefore its sublevel set is convex for any level. Since this is also true for level=0, I conclude that the constraint result in a convex set. (Please let me know if this reasoning is wrong. Thanks in advance.)
$endgroup$
– Frank Moses
Jan 28 at 16:31
$begingroup$
@BrianBorchers I think so. Here is the reason why I think so (please correct me if I am wrong). As the function on the left side is convex therefore its sublevel set is convex for any level. Since this is also true for level=0, I conclude that the constraint result in a convex set. (Please let me know if this reasoning is wrong. Thanks in advance.)
$endgroup$
– Frank Moses
Jan 28 at 16:31
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Like @Brian Borchers hinted at, it is a composition of two linear operations (multiply with a constant matrix, and trace), so the whole thing $Tr(AQ)$ is linear in $A$ given $Q$.
If you want to show it the long way, assume there are $A_1,A_2$ that satisfy the constraint, i.e. $-Tr(A_1 Q) leq 0$,$-Tr(A_2 Q) leq 0$. For any $theta in [0,1]$, let $A_3 = theta A_1 + (1-theta) A_2$ be the convex combination of the two matrices, then we have
begin{equation}
begin{split}
-Tr(A_3 Q) &= - Tr ((theta A_1 + (1-theta)A_2) Q) \
&= -Tr(theta A_1Q + (1-theta) A_2 Q) \
&= - theta cdot Tr(A_1Q) - (1-theta) cdot Tr(A_2Q) \
&leq 0
end{split}
end{equation}
where the last equality comes from the linear nature of trace operator and the inequality is from the simple fact that sum of two $leq 0$ entities is still $leq 0$. Therefore $A_3$ is still in the same set for arbitrary $theta in [0,1]$, hence the feasible set is convex.
answered Jan 29 at 1:32
Tingkai LiuTingkai Liu
758
$endgroup$
$begingroup$
thank you for your answer. Can you please also answer/comment on this question math.stackexchange.com/questions/3091183/…
$endgroup$
– Frank Moses
Jan 29 at 7: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%2f3090899%2funder-what-conditions-the-following-constraint-is-convex%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$
Like @Brian Borchers hinted at, it is a composition of two linear operations (multiply with a constant matrix, and trace), so the whole thing $Tr(AQ)$ is linear in $A$ given $Q$.
If you want to show it the long way, assume there are $A_1,A_2$ that satisfy the constraint, i.e. $-Tr(A_1 Q) leq 0$,$-Tr(A_2 Q) leq 0$. For any $theta in [0,1]$, let $A_3 = theta A_1 + (1-theta) A_2$ be the convex combination of the two matrices, then we have
begin{equation}
begin{split}
-Tr(A_3 Q) &= - Tr ((theta A_1 + (1-theta)A_2) Q) \
&= -Tr(theta A_1Q + (1-theta) A_2 Q) \
&= - theta cdot Tr(A_1Q) - (1-theta) cdot Tr(A_2Q) \
&leq 0
end{split}
end{equation}
where the last equality comes from the linear nature of trace operator and the inequality is from the simple fact that sum of two $leq 0$ entities is still $leq 0$. Therefore $A_3$ is still in the same set for arbitrary $theta in [0,1]$, hence the feasible set is convex.
answered Jan 29 at 1:32
Tingkai LiuTingkai Liu
758
$endgroup$
$begingroup$
thank you for your answer. Can you please also answer/comment on this question math.stackexchange.com/questions/3091183/…
$endgroup$
– Frank Moses
Jan 29 at 7:17
add a comment |
$begingroup$
Like @Brian Borchers hinted at, it is a composition of two linear operations (multiply with a constant matrix, and trace), so the whole thing $Tr(AQ)$ is linear in $A$ given $Q$.
If you want to show it the long way, assume there are $A_1,A_2$ that satisfy the constraint, i.e. $-Tr(A_1 Q) leq 0$,$-Tr(A_2 Q) leq 0$. For any $theta in [0,1]$, let $A_3 = theta A_1 + (1-theta) A_2$ be the convex combination of the two matrices, then we have
begin{equation}
begin{split}
-Tr(A_3 Q) &= - Tr ((theta A_1 + (1-theta)A_2) Q) \
&= -Tr(theta A_1Q + (1-theta) A_2 Q) \
&= - theta cdot Tr(A_1Q) - (1-theta) cdot Tr(A_2Q) \
&leq 0
end{split}
end{equation}
where the last equality comes from the linear nature of trace operator and the inequality is from the simple fact that sum of two $leq 0$ entities is still $leq 0$. Therefore $A_3$ is still in the same set for arbitrary $theta in [0,1]$, hence the feasible set is convex.
answered Jan 29 at 1:32
Tingkai LiuTingkai Liu
758
$endgroup$
$begingroup$
thank you for your answer. Can you please also answer/comment on this question math.stackexchange.com/questions/3091183/…
$endgroup$
– Frank Moses
Jan 29 at 7:17
add a comment |
$begingroup$
Like @Brian Borchers hinted at, it is a composition of two linear operations (multiply with a constant matrix, and trace), so the whole thing $Tr(AQ)$ is linear in $A$ given $Q$.
If you want to show it the long way, assume there are $A_1,A_2$ that satisfy the constraint, i.e. $-Tr(A_1 Q) leq 0$,$-Tr(A_2 Q) leq 0$. For any $theta in [0,1]$, let $A_3 = theta A_1 + (1-theta) A_2$ be the convex combination of the two matrices, then we have
begin{equation}
begin{split}
-Tr(A_3 Q) &= - Tr ((theta A_1 + (1-theta)A_2) Q) \
&= -Tr(theta A_1Q + (1-theta) A_2 Q) \
&= - theta cdot Tr(A_1Q) - (1-theta) cdot Tr(A_2Q) \
&leq 0
end{split}
end{equation}
where the last equality comes from the linear nature of trace operator and the inequality is from the simple fact that sum of two $leq 0$ entities is still $leq 0$. Therefore $A_3$ is still in the same set for arbitrary $theta in [0,1]$, hence the feasible set is convex.
answered Jan 29 at 1:32
Tingkai LiuTingkai Liu
758
$endgroup$
Like @Brian Borchers hinted at, it is a composition of two linear operations (multiply with a constant matrix, and trace), so the whole thing $Tr(AQ)$ is linear in $A$ given $Q$.
If you want to show it the long way, assume there are $A_1,A_2$ that satisfy the constraint, i.e. $-Tr(A_1 Q) leq 0$,$-Tr(A_2 Q) leq 0$. For any $theta in [0,1]$, let $A_3 = theta A_1 + (1-theta) A_2$ be the convex combination of the two matrices, then we have
begin{equation}
begin{split}
-Tr(A_3 Q) &= - Tr ((theta A_1 + (1-theta)A_2) Q) \
&= -Tr(theta A_1Q + (1-theta) A_2 Q) \
&= - theta cdot Tr(A_1Q) - (1-theta) cdot Tr(A_2Q) \
&leq 0
end{split}
end{equation}
where the last equality comes from the linear nature of trace operator and the inequality is from the simple fact that sum of two $leq 0$ entities is still $leq 0$. Therefore $A_3$ is still in the same set for arbitrary $theta in [0,1]$, hence the feasible set is convex.
answered Jan 29 at 1:32
Tingkai LiuTingkai Liu
758
answered Jan 29 at 1:32
Tingkai LiuTingkai Liu
758
answered Jan 29 at 1:32
Tingkai LiuTingkai Liu
758
answered Jan 29 at 1:32
Tingkai LiuTingkai Liu
758
758
$begingroup$
thank you for your answer. Can you please also answer/comment on this question math.stackexchange.com/questions/3091183/…
$endgroup$
– Frank Moses
Jan 29 at 7:17
add a comment |
$begingroup$
thank you for your answer. Can you please also answer/comment on this question math.stackexchange.com/questions/3091183/…
$endgroup$
– Frank Moses
Jan 29 at 7:17
$begingroup$
thank you for your answer. Can you please also answer/comment on this question math.stackexchange.com/questions/3091183/…
$endgroup$
– Frank Moses
Jan 29 at 7:17
$begingroup$
thank you for your answer. Can you please also answer/comment on this question math.stackexchange.com/questions/3091183/…
$endgroup$
– Frank Moses
Jan 29 at 7: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%2f3090899%2funder-what-conditions-the-following-constraint-is-convex%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$
@supinf thus far I only know how to show that $tr ~mathbb{A}$ is a convex function (this is an exercise in Stephen Boyd book). But I do not know how to show that by multiplying $mathbb{A}$ by $mathbb{Q}$ it becomes a concave function.
$endgroup$
– Frank Moses
Jan 28 at 14:23
1
$begingroup$
Have you tried to write out a formula for $-mbox{tr} AQ$ in terms of the elements of $A$ and $Q$?
$endgroup$
– Brian Borchers
Jan 28 at 15:26
$begingroup$
@BrianBorchers ok now I know that its a linear function so it is both convex and concave at the same time
$endgroup$
– Frank Moses
Jan 28 at 16:04
1
$begingroup$
So, you know that $-mbox{tr}(AQ) $ is a convex function and your constraint is of the form convex function of A is less than 0. Is that enough to establish that the feasible region is convex?
$endgroup$
– Brian Borchers
Jan 28 at 16:18
$begingroup$
@BrianBorchers I think so. Here is the reason why I think so (please correct me if I am wrong). As the function on the left side is convex therefore its sublevel set is convex for any level. Since this is also true for level=0, I conclude that the constraint result in a convex set. (Please let me know if this reasoning is wrong. Thanks in advance.)
$endgroup$
– Frank Moses
Jan 28 at 16:31