Can I apply the Schur complement on both sides of an inequality
$begingroup$
I have the following matrix inequality that I need to express as an LMI
$ A^T Q^{-1} A - Q + sum_i A_i^T Q^{-1} A_i < 0$
($Q > 0$, $A = XQ+YB$, $A_i = X_i Q+Y_i B$)
which I rewrote to
$ A^T Q^{-1} A - Q < - sum_i A_i^T Q^{-1} A_i$
Now I want to use Schur's complement and express this inequality as
$
begin{bmatrix}
-Q & A^T \
A & -Q
end{bmatrix}
< sum_i
begin{bmatrix}
0 & A_i^T \
A_i & Q
end{bmatrix}
$
and therefore
$
begin{bmatrix}
-Q & A^T \
A & -Q
end{bmatrix}
- sum_i
begin{bmatrix}
0 & A_i^T \
A_i & Q
end{bmatrix}
< 0 $
which is a form my solver, solving for Q and B, should be able to handle.
Can I use the Schur complement in this way and are these two inequalities equivalent?
matrices proof-verification matrix-equations lmis schur-complement
$endgroup$
add a comment |
$begingroup$
I have the following matrix inequality that I need to express as an LMI
$ A^T Q^{-1} A - Q + sum_i A_i^T Q^{-1} A_i < 0$
($Q > 0$, $A = XQ+YB$, $A_i = X_i Q+Y_i B$)
which I rewrote to
$ A^T Q^{-1} A - Q < - sum_i A_i^T Q^{-1} A_i$
Now I want to use Schur's complement and express this inequality as
$
begin{bmatrix}
-Q & A^T \
A & -Q
end{bmatrix}
< sum_i
begin{bmatrix}
0 & A_i^T \
A_i & Q
end{bmatrix}
$
and therefore
$
begin{bmatrix}
-Q & A^T \
A & -Q
end{bmatrix}
- sum_i
begin{bmatrix}
0 & A_i^T \
A_i & Q
end{bmatrix}
< 0 $
which is a form my solver, solving for Q and B, should be able to handle.
Can I use the Schur complement in this way and are these two inequalities equivalent?
matrices proof-verification matrix-equations lmis schur-complement
$endgroup$
$begingroup$
Which variables are known and which variables do you want to solve for?
$endgroup$
– Kwin van der Veen
Dec 1 '18 at 23:48
$begingroup$
@KwinvanderVeen I have edited my question. X and Y are known, Q and B are unknown
$endgroup$
– Alex bGoode
Dec 2 '18 at 1:51
$begingroup$
The matrices $A_i$ are also known as well?
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 2:55
$begingroup$
Yes, they have the same structure, $X_i$ and $Y_i$ are known
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:38
add a comment |
$begingroup$
I have the following matrix inequality that I need to express as an LMI
$ A^T Q^{-1} A - Q + sum_i A_i^T Q^{-1} A_i < 0$
($Q > 0$, $A = XQ+YB$, $A_i = X_i Q+Y_i B$)
which I rewrote to
$ A^T Q^{-1} A - Q < - sum_i A_i^T Q^{-1} A_i$
Now I want to use Schur's complement and express this inequality as
$
begin{bmatrix}
-Q & A^T \
A & -Q
end{bmatrix}
< sum_i
begin{bmatrix}
0 & A_i^T \
A_i & Q
end{bmatrix}
$
and therefore
$
begin{bmatrix}
-Q & A^T \
A & -Q
end{bmatrix}
- sum_i
begin{bmatrix}
0 & A_i^T \
A_i & Q
end{bmatrix}
< 0 $
which is a form my solver, solving for Q and B, should be able to handle.
Can I use the Schur complement in this way and are these two inequalities equivalent?
matrices proof-verification matrix-equations lmis schur-complement
$endgroup$
I have the following matrix inequality that I need to express as an LMI
$ A^T Q^{-1} A - Q + sum_i A_i^T Q^{-1} A_i < 0$
($Q > 0$, $A = XQ+YB$, $A_i = X_i Q+Y_i B$)
which I rewrote to
$ A^T Q^{-1} A - Q < - sum_i A_i^T Q^{-1} A_i$
Now I want to use Schur's complement and express this inequality as
$
begin{bmatrix}
-Q & A^T \
A & -Q
end{bmatrix}
< sum_i
begin{bmatrix}
0 & A_i^T \
A_i & Q
end{bmatrix}
$
and therefore
$
begin{bmatrix}
-Q & A^T \
A & -Q
end{bmatrix}
- sum_i
begin{bmatrix}
0 & A_i^T \
A_i & Q
end{bmatrix}
< 0 $
which is a form my solver, solving for Q and B, should be able to handle.
Can I use the Schur complement in this way and are these two inequalities equivalent?
matrices proof-verification matrix-equations lmis schur-complement
matrices proof-verification matrix-equations lmis schur-complement
edited Dec 2 '18 at 16:02
Alex bGoode
asked Dec 1 '18 at 18:57
Alex bGoodeAlex bGoode
1257
1257
$begingroup$
Which variables are known and which variables do you want to solve for?
$endgroup$
– Kwin van der Veen
Dec 1 '18 at 23:48
$begingroup$
@KwinvanderVeen I have edited my question. X and Y are known, Q and B are unknown
$endgroup$
– Alex bGoode
Dec 2 '18 at 1:51
$begingroup$
The matrices $A_i$ are also known as well?
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 2:55
$begingroup$
Yes, they have the same structure, $X_i$ and $Y_i$ are known
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:38
add a comment |
$begingroup$
Which variables are known and which variables do you want to solve for?
$endgroup$
– Kwin van der Veen
Dec 1 '18 at 23:48
$begingroup$
@KwinvanderVeen I have edited my question. X and Y are known, Q and B are unknown
$endgroup$
– Alex bGoode
Dec 2 '18 at 1:51
$begingroup$
The matrices $A_i$ are also known as well?
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 2:55
$begingroup$
Yes, they have the same structure, $X_i$ and $Y_i$ are known
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:38
$begingroup$
Which variables are known and which variables do you want to solve for?
$endgroup$
– Kwin van der Veen
Dec 1 '18 at 23:48
$begingroup$
Which variables are known and which variables do you want to solve for?
$endgroup$
– Kwin van der Veen
Dec 1 '18 at 23:48
$begingroup$
@KwinvanderVeen I have edited my question. X and Y are known, Q and B are unknown
$endgroup$
– Alex bGoode
Dec 2 '18 at 1:51
$begingroup$
@KwinvanderVeen I have edited my question. X and Y are known, Q and B are unknown
$endgroup$
– Alex bGoode
Dec 2 '18 at 1:51
$begingroup$
The matrices $A_i$ are also known as well?
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 2:55
$begingroup$
The matrices $A_i$ are also known as well?
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 2:55
$begingroup$
Yes, they have the same structure, $X_i$ and $Y_i$ are known
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:38
$begingroup$
Yes, they have the same structure, $X_i$ and $Y_i$ are known
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:38
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You can't use Schur's complement in that way. Namely when you have the matrix inequalities
$$
A - B^top C^{-1} B succ 0, quad C succ 0,
$$
then you can combine this into the following one matrix inequality
$$
M =
begin{bmatrix}
A & B^top \ B & C
end{bmatrix} succ 0.
$$
This is because $M$ can be decomposed as follows
$$
M =
underbrace{
begin{bmatrix}
I & B^top C^{-1} \ 0 & I
end{bmatrix}
}_{T^top}
begin{bmatrix}
A - B^top C^{-1} B & 0 \ 0 & C
end{bmatrix}
underbrace{
begin{bmatrix}
I & 0 \ C^{-1} B & I
end{bmatrix}
}_{T}.
$$
Namely $M succ 0$ means that $x^top M,x > 0 forall, xneq0$. So when using $x=T,y$ one gets $x^top M,x = y^top T^top M,T,y$. It holds that $xneq0$ iff $yneq0$, since $T$ is full rank (lower triangular with ones on the diagonal), thus it also has to hold that $T^top M,T succ 0$.
But remember that this equivalent matrix inequality formulation only works because the matrix $T$ transforms $M$ into a block diagonal matrix with the blocks the original matrix inequalities. So your proposition only works if there exists a transformation $T$ such that
$$
T^top left(
begin{bmatrix}
Q & -A^top \
-A & Q
end{bmatrix}
+ sum_i
begin{bmatrix}
0 & A_i^top \
A_i & Q
end{bmatrix}
right) T
$$
gives back the original matrix inequalities as blocks on the diagonal.
$endgroup$
$begingroup$
Thank you, I will need to take some time and understand your answer. Do you have any pointers on how I can transform my original problem into an LMI or should I post another question for this?
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:40
$begingroup$
@AlexbGoode what are the sizes of $Y$ and $B$? If $Y$ has a rank equal to the size of $Q$ then you could define $A$ as a variable and later use that to solve for $B$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 12:50
$begingroup$
Nevermind, you only have one $B$ and multiple $A$/$A_i$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 13:14
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%2f3021681%2fcan-i-apply-the-schur-complement-on-both-sides-of-an-inequality%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$
You can't use Schur's complement in that way. Namely when you have the matrix inequalities
$$
A - B^top C^{-1} B succ 0, quad C succ 0,
$$
then you can combine this into the following one matrix inequality
$$
M =
begin{bmatrix}
A & B^top \ B & C
end{bmatrix} succ 0.
$$
This is because $M$ can be decomposed as follows
$$
M =
underbrace{
begin{bmatrix}
I & B^top C^{-1} \ 0 & I
end{bmatrix}
}_{T^top}
begin{bmatrix}
A - B^top C^{-1} B & 0 \ 0 & C
end{bmatrix}
underbrace{
begin{bmatrix}
I & 0 \ C^{-1} B & I
end{bmatrix}
}_{T}.
$$
Namely $M succ 0$ means that $x^top M,x > 0 forall, xneq0$. So when using $x=T,y$ one gets $x^top M,x = y^top T^top M,T,y$. It holds that $xneq0$ iff $yneq0$, since $T$ is full rank (lower triangular with ones on the diagonal), thus it also has to hold that $T^top M,T succ 0$.
But remember that this equivalent matrix inequality formulation only works because the matrix $T$ transforms $M$ into a block diagonal matrix with the blocks the original matrix inequalities. So your proposition only works if there exists a transformation $T$ such that
$$
T^top left(
begin{bmatrix}
Q & -A^top \
-A & Q
end{bmatrix}
+ sum_i
begin{bmatrix}
0 & A_i^top \
A_i & Q
end{bmatrix}
right) T
$$
gives back the original matrix inequalities as blocks on the diagonal.
$endgroup$
$begingroup$
Thank you, I will need to take some time and understand your answer. Do you have any pointers on how I can transform my original problem into an LMI or should I post another question for this?
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:40
$begingroup$
@AlexbGoode what are the sizes of $Y$ and $B$? If $Y$ has a rank equal to the size of $Q$ then you could define $A$ as a variable and later use that to solve for $B$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 12:50
$begingroup$
Nevermind, you only have one $B$ and multiple $A$/$A_i$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 13:14
add a comment |
$begingroup$
You can't use Schur's complement in that way. Namely when you have the matrix inequalities
$$
A - B^top C^{-1} B succ 0, quad C succ 0,
$$
then you can combine this into the following one matrix inequality
$$
M =
begin{bmatrix}
A & B^top \ B & C
end{bmatrix} succ 0.
$$
This is because $M$ can be decomposed as follows
$$
M =
underbrace{
begin{bmatrix}
I & B^top C^{-1} \ 0 & I
end{bmatrix}
}_{T^top}
begin{bmatrix}
A - B^top C^{-1} B & 0 \ 0 & C
end{bmatrix}
underbrace{
begin{bmatrix}
I & 0 \ C^{-1} B & I
end{bmatrix}
}_{T}.
$$
Namely $M succ 0$ means that $x^top M,x > 0 forall, xneq0$. So when using $x=T,y$ one gets $x^top M,x = y^top T^top M,T,y$. It holds that $xneq0$ iff $yneq0$, since $T$ is full rank (lower triangular with ones on the diagonal), thus it also has to hold that $T^top M,T succ 0$.
But remember that this equivalent matrix inequality formulation only works because the matrix $T$ transforms $M$ into a block diagonal matrix with the blocks the original matrix inequalities. So your proposition only works if there exists a transformation $T$ such that
$$
T^top left(
begin{bmatrix}
Q & -A^top \
-A & Q
end{bmatrix}
+ sum_i
begin{bmatrix}
0 & A_i^top \
A_i & Q
end{bmatrix}
right) T
$$
gives back the original matrix inequalities as blocks on the diagonal.
$endgroup$
$begingroup$
Thank you, I will need to take some time and understand your answer. Do you have any pointers on how I can transform my original problem into an LMI or should I post another question for this?
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:40
$begingroup$
@AlexbGoode what are the sizes of $Y$ and $B$? If $Y$ has a rank equal to the size of $Q$ then you could define $A$ as a variable and later use that to solve for $B$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 12:50
$begingroup$
Nevermind, you only have one $B$ and multiple $A$/$A_i$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 13:14
add a comment |
$begingroup$
You can't use Schur's complement in that way. Namely when you have the matrix inequalities
$$
A - B^top C^{-1} B succ 0, quad C succ 0,
$$
then you can combine this into the following one matrix inequality
$$
M =
begin{bmatrix}
A & B^top \ B & C
end{bmatrix} succ 0.
$$
This is because $M$ can be decomposed as follows
$$
M =
underbrace{
begin{bmatrix}
I & B^top C^{-1} \ 0 & I
end{bmatrix}
}_{T^top}
begin{bmatrix}
A - B^top C^{-1} B & 0 \ 0 & C
end{bmatrix}
underbrace{
begin{bmatrix}
I & 0 \ C^{-1} B & I
end{bmatrix}
}_{T}.
$$
Namely $M succ 0$ means that $x^top M,x > 0 forall, xneq0$. So when using $x=T,y$ one gets $x^top M,x = y^top T^top M,T,y$. It holds that $xneq0$ iff $yneq0$, since $T$ is full rank (lower triangular with ones on the diagonal), thus it also has to hold that $T^top M,T succ 0$.
But remember that this equivalent matrix inequality formulation only works because the matrix $T$ transforms $M$ into a block diagonal matrix with the blocks the original matrix inequalities. So your proposition only works if there exists a transformation $T$ such that
$$
T^top left(
begin{bmatrix}
Q & -A^top \
-A & Q
end{bmatrix}
+ sum_i
begin{bmatrix}
0 & A_i^top \
A_i & Q
end{bmatrix}
right) T
$$
gives back the original matrix inequalities as blocks on the diagonal.
$endgroup$
You can't use Schur's complement in that way. Namely when you have the matrix inequalities
$$
A - B^top C^{-1} B succ 0, quad C succ 0,
$$
then you can combine this into the following one matrix inequality
$$
M =
begin{bmatrix}
A & B^top \ B & C
end{bmatrix} succ 0.
$$
This is because $M$ can be decomposed as follows
$$
M =
underbrace{
begin{bmatrix}
I & B^top C^{-1} \ 0 & I
end{bmatrix}
}_{T^top}
begin{bmatrix}
A - B^top C^{-1} B & 0 \ 0 & C
end{bmatrix}
underbrace{
begin{bmatrix}
I & 0 \ C^{-1} B & I
end{bmatrix}
}_{T}.
$$
Namely $M succ 0$ means that $x^top M,x > 0 forall, xneq0$. So when using $x=T,y$ one gets $x^top M,x = y^top T^top M,T,y$. It holds that $xneq0$ iff $yneq0$, since $T$ is full rank (lower triangular with ones on the diagonal), thus it also has to hold that $T^top M,T succ 0$.
But remember that this equivalent matrix inequality formulation only works because the matrix $T$ transforms $M$ into a block diagonal matrix with the blocks the original matrix inequalities. So your proposition only works if there exists a transformation $T$ such that
$$
T^top left(
begin{bmatrix}
Q & -A^top \
-A & Q
end{bmatrix}
+ sum_i
begin{bmatrix}
0 & A_i^top \
A_i & Q
end{bmatrix}
right) T
$$
gives back the original matrix inequalities as blocks on the diagonal.
edited Dec 3 '18 at 2:28
answered Dec 2 '18 at 4:17
Kwin van der VeenKwin van der Veen
5,4952828
5,4952828
$begingroup$
Thank you, I will need to take some time and understand your answer. Do you have any pointers on how I can transform my original problem into an LMI or should I post another question for this?
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:40
$begingroup$
@AlexbGoode what are the sizes of $Y$ and $B$? If $Y$ has a rank equal to the size of $Q$ then you could define $A$ as a variable and later use that to solve for $B$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 12:50
$begingroup$
Nevermind, you only have one $B$ and multiple $A$/$A_i$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 13:14
add a comment |
$begingroup$
Thank you, I will need to take some time and understand your answer. Do you have any pointers on how I can transform my original problem into an LMI or should I post another question for this?
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:40
$begingroup$
@AlexbGoode what are the sizes of $Y$ and $B$? If $Y$ has a rank equal to the size of $Q$ then you could define $A$ as a variable and later use that to solve for $B$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 12:50
$begingroup$
Nevermind, you only have one $B$ and multiple $A$/$A_i$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 13:14
$begingroup$
Thank you, I will need to take some time and understand your answer. Do you have any pointers on how I can transform my original problem into an LMI or should I post another question for this?
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:40
$begingroup$
Thank you, I will need to take some time and understand your answer. Do you have any pointers on how I can transform my original problem into an LMI or should I post another question for this?
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:40
$begingroup$
@AlexbGoode what are the sizes of $Y$ and $B$? If $Y$ has a rank equal to the size of $Q$ then you could define $A$ as a variable and later use that to solve for $B$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 12:50
$begingroup$
@AlexbGoode what are the sizes of $Y$ and $B$? If $Y$ has a rank equal to the size of $Q$ then you could define $A$ as a variable and later use that to solve for $B$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 12:50
$begingroup$
Nevermind, you only have one $B$ and multiple $A$/$A_i$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 13:14
$begingroup$
Nevermind, you only have one $B$ and multiple $A$/$A_i$.
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 13:14
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%2f3021681%2fcan-i-apply-the-schur-complement-on-both-sides-of-an-inequality%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$
Which variables are known and which variables do you want to solve for?
$endgroup$
– Kwin van der Veen
Dec 1 '18 at 23:48
$begingroup$
@KwinvanderVeen I have edited my question. X and Y are known, Q and B are unknown
$endgroup$
– Alex bGoode
Dec 2 '18 at 1:51
$begingroup$
The matrices $A_i$ are also known as well?
$endgroup$
– Kwin van der Veen
Dec 2 '18 at 2:55
$begingroup$
Yes, they have the same structure, $X_i$ and $Y_i$ are known
$endgroup$
– Alex bGoode
Dec 2 '18 at 12:38