Writing a convex quadratic constraint in SOC form
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am trying to apply the following transformation for a problem:
Consider a quadratic constraint of the form
$$ x^TA^TAx+b^Tx+cleq0. $$
This is equivalent to the SOC constraint
$$ left| beginarrayc(1+b^Tx+c)/2\Axendarrayright|_2 leq (1-b^Tx-c)/2. $$
The challenge for me is, my problem is in the form $x^T Q x + bx +c leq 0$ where $Q$ is not positive definite (it is semidefinite). So I can't apply Cholesky decomposition $Q = L^T L$ and I can't use the transformation above.
I am now trying to find another method. I tried eigenvalue-eigenvector decomposition: $Q = VDV^T$ where $D$ is a diagonal matrix. But that doesn't give the same solution as Cholesky does.
How can I write the constraint in SOC form?
linear-algebra optimization matrix-decomposition positive-definite
edited Aug 12 at 2:45
David M.
1,369318
asked Aug 10 at 17:37
aslv95
397
 |Â
show 3 more comments
up vote
1
down vote
favorite
I am trying to apply the following transformation for a problem:
Consider a quadratic constraint of the form
$$ x^TA^TAx+b^Tx+cleq0. $$
This is equivalent to the SOC constraint
$$ left| beginarrayc(1+b^Tx+c)/2\Axendarrayright|_2 leq (1-b^Tx-c)/2. $$
The challenge for me is, my problem is in the form $x^T Q x + bx +c leq 0$ where $Q$ is not positive definite (it is semidefinite). So I can't apply Cholesky decomposition $Q = L^T L$ and I can't use the transformation above.
I am now trying to find another method. I tried eigenvalue-eigenvector decomposition: $Q = VDV^T$ where $D$ is a diagonal matrix. But that doesn't give the same solution as Cholesky does.
How can I write the constraint in SOC form?
linear-algebra optimization matrix-decomposition positive-definite
edited Aug 12 at 2:45
David M.
1,369318
asked Aug 10 at 17:37
aslv95
397
1
$x^TQxleq 0$ where $Q$ is positive semidefinite is a bit silly, as that simply means $x$ has to be in the null-space of $Q$, i.e. it is a linear constraint.
– Johan Löfberg
Aug 11 at 12:57
1
I think you can use the eigenvalue decomposition and write it as $Q=VD^1/2D^1/2V^T=(VD^1/2)(VD^1/2)^T$.
– David M.
Aug 12 at 2:27
1
Also, the Cholesky decomposition is indeed defined for positive semidefinite matrices (see wiki page, for example), you just can't use the same algorithm to compute it. An $L D L^mathsfT$ decomposition of $Q$ can give a semidefinite Cholesky by breaking up the $D$ into $(D^1/2)^2$.
– cdipaolo
Aug 12 at 4:05
1
Just use any factorization based on, e.g., eigenvalue decomposition, SVD, or LDL. You will have zeros in the diagonal in the middle matrix, indicating that you can remove some of the rows and thus use a compressed factorization $Q=M^TM$ where $M$ is fat.
– Johan Löfberg
Aug 12 at 7:31
1
@aslv95 Not quite — my comment was about getting a bonafide Cholesky decomposition since L is lower triangular, but both solutions work equally well in theory.
– cdipaolo
Aug 12 at 16:19
 |Â
show 3 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am trying to apply the following transformation for a problem:
Consider a quadratic constraint of the form
$$ x^TA^TAx+b^Tx+cleq0. $$
This is equivalent to the SOC constraint
$$ left| beginarrayc(1+b^Tx+c)/2\Axendarrayright|_2 leq (1-b^Tx-c)/2. $$
The challenge for me is, my problem is in the form $x^T Q x + bx +c leq 0$ where $Q$ is not positive definite (it is semidefinite). So I can't apply Cholesky decomposition $Q = L^T L$ and I can't use the transformation above.
I am now trying to find another method. I tried eigenvalue-eigenvector decomposition: $Q = VDV^T$ where $D$ is a diagonal matrix. But that doesn't give the same solution as Cholesky does.
How can I write the constraint in SOC form?
linear-algebra optimization matrix-decomposition positive-definite
edited Aug 12 at 2:45
David M.
1,369318
asked Aug 10 at 17:37
aslv95
397
I am trying to apply the following transformation for a problem:
Consider a quadratic constraint of the form
$$ x^TA^TAx+b^Tx+cleq0. $$
This is equivalent to the SOC constraint
$$ left| beginarrayc(1+b^Tx+c)/2\Axendarrayright|_2 leq (1-b^Tx-c)/2. $$
The challenge for me is, my problem is in the form $x^T Q x + bx +c leq 0$ where $Q$ is not positive definite (it is semidefinite). So I can't apply Cholesky decomposition $Q = L^T L$ and I can't use the transformation above.
I am now trying to find another method. I tried eigenvalue-eigenvector decomposition: $Q = VDV^T$ where $D$ is a diagonal matrix. But that doesn't give the same solution as Cholesky does.
How can I write the constraint in SOC form?
linear-algebra optimization matrix-decomposition positive-definite
edited Aug 12 at 2:45
David M.
1,369318
asked Aug 10 at 17:37
aslv95
397
edited Aug 12 at 2:45
David M.
1,369318
edited Aug 12 at 2:45
David M.
1,369318
edited Aug 12 at 2:45
David M.
1,369318
1,369318
asked Aug 10 at 17:37
aslv95
397
asked Aug 10 at 17:37
aslv95
397
asked Aug 10 at 17:37
aslv95
397
397
1
$x^TQxleq 0$ where $Q$ is positive semidefinite is a bit silly, as that simply means $x$ has to be in the null-space of $Q$, i.e. it is a linear constraint.
– Johan Löfberg
Aug 11 at 12:57
1
I think you can use the eigenvalue decomposition and write it as $Q=VD^1/2D^1/2V^T=(VD^1/2)(VD^1/2)^T$.
– David M.
Aug 12 at 2:27
1
Also, the Cholesky decomposition is indeed defined for positive semidefinite matrices (see wiki page, for example), you just can't use the same algorithm to compute it. An $L D L^mathsfT$ decomposition of $Q$ can give a semidefinite Cholesky by breaking up the $D$ into $(D^1/2)^2$.
– cdipaolo
Aug 12 at 4:05
1
Just use any factorization based on, e.g., eigenvalue decomposition, SVD, or LDL. You will have zeros in the diagonal in the middle matrix, indicating that you can remove some of the rows and thus use a compressed factorization $Q=M^TM$ where $M$ is fat.
– Johan Löfberg
Aug 12 at 7:31
1
@aslv95 Not quite — my comment was about getting a bonafide Cholesky decomposition since L is lower triangular, but both solutions work equally well in theory.
– cdipaolo
Aug 12 at 16:19
 |Â
show 3 more comments
1
$x^TQxleq 0$ where $Q$ is positive semidefinite is a bit silly, as that simply means $x$ has to be in the null-space of $Q$, i.e. it is a linear constraint.
– Johan Löfberg
Aug 11 at 12:57
1
I think you can use the eigenvalue decomposition and write it as $Q=VD^1/2D^1/2V^T=(VD^1/2)(VD^1/2)^T$.
– David M.
Aug 12 at 2:27
1
Also, the Cholesky decomposition is indeed defined for positive semidefinite matrices (see wiki page, for example), you just can't use the same algorithm to compute it. An $L D L^mathsfT$ decomposition of $Q$ can give a semidefinite Cholesky by breaking up the $D$ into $(D^1/2)^2$.
– cdipaolo
Aug 12 at 4:05
1
Just use any factorization based on, e.g., eigenvalue decomposition, SVD, or LDL. You will have zeros in the diagonal in the middle matrix, indicating that you can remove some of the rows and thus use a compressed factorization $Q=M^TM$ where $M$ is fat.
– Johan Löfberg
Aug 12 at 7:31
1
@aslv95 Not quite — my comment was about getting a bonafide Cholesky decomposition since L is lower triangular, but both solutions work equally well in theory.
– cdipaolo
Aug 12 at 16:19
1
1
$x^TQxleq 0$ where $Q$ is positive semidefinite is a bit silly, as that simply means $x$ has to be in the null-space of $Q$, i.e. it is a linear constraint.
– Johan Löfberg
Aug 11 at 12:57
$x^TQxleq 0$ where $Q$ is positive semidefinite is a bit silly, as that simply means $x$ has to be in the null-space of $Q$, i.e. it is a linear constraint.
– Johan Löfberg
Aug 11 at 12:57
1
1
I think you can use the eigenvalue decomposition and write it as $Q=VD^1/2D^1/2V^T=(VD^1/2)(VD^1/2)^T$.
– David M.
Aug 12 at 2:27
I think you can use the eigenvalue decomposition and write it as $Q=VD^1/2D^1/2V^T=(VD^1/2)(VD^1/2)^T$.
– David M.
Aug 12 at 2:27
1
1
Also, the Cholesky decomposition is indeed defined for positive semidefinite matrices (see wiki page, for example), you just can't use the same algorithm to compute it. An $L D L^mathsfT$ decomposition of $Q$ can give a semidefinite Cholesky by breaking up the $D$ into $(D^1/2)^2$.
– cdipaolo
Aug 12 at 4:05
Also, the Cholesky decomposition is indeed defined for positive semidefinite matrices (see wiki page, for example), you just can't use the same algorithm to compute it. An $L D L^mathsfT$ decomposition of $Q$ can give a semidefinite Cholesky by breaking up the $D$ into $(D^1/2)^2$.
– cdipaolo
Aug 12 at 4:05
1
1
Just use any factorization based on, e.g., eigenvalue decomposition, SVD, or LDL. You will have zeros in the diagonal in the middle matrix, indicating that you can remove some of the rows and thus use a compressed factorization $Q=M^TM$ where $M$ is fat.
– Johan Löfberg
Aug 12 at 7:31
Just use any factorization based on, e.g., eigenvalue decomposition, SVD, or LDL. You will have zeros in the diagonal in the middle matrix, indicating that you can remove some of the rows and thus use a compressed factorization $Q=M^TM$ where $M$ is fat.
– Johan Löfberg
Aug 12 at 7:31
1
1
@aslv95 Not quite — my comment was about getting a bonafide Cholesky decomposition since L is lower triangular, but both solutions work equally well in theory.
– cdipaolo
Aug 12 at 16:19
@aslv95 Not quite — my comment was about getting a bonafide Cholesky decomposition since L is lower triangular, but both solutions work equally well in theory.
– cdipaolo
Aug 12 at 16:19
 |Â
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
As mentioned in the comments, your approach using the eigenvalue decomposition is correct. In this case, we have that
$$ Q=VDV^T$$
which can be written as
$$ Q=(VD^1/2)(VD^1/2)^T. $$
(As noted in the comments, other decompositions could work as well, but I'll use this one, since it's the one you mention). Your concern is that, if $Q$ is a positive definite matrix, then the matrix $L$ obtained by taking the Cholesky decomposition isn't the same as the matrix $VD^1/2$ obtained above. However, this doesn't mean that the resulting reformulation doesn't yield the same result in both cases.
Consider your example
$$ Q=beginpmatrix2&-5/2\-5/2&4endpmatrix.$$
If we take the Cholesky decomposition, then, to a few digits of accuracy,
$$ L=beginpmatrix1.414&0\-1.768&0.935endpmatrix. $$
If we take the eigenvalue decomposition, then, to a few digits of accuracy,
$$ VD^1/2=beginpmatrix-0.459&1.338\-0.311&-1.976endpmatrix. $$
Indeed, $LneqVD^1/2$. However, let's look at the plots of the level sets for all three formulations:
VoilÃÂ
Edit: A note on why this is true: essentially, we are employing this theorem:
Theorem: Let $QinmathbbR^ntimesn$ be positive semidefinite, and let $binmathbbR^n$, $cinmathbbR$. Let $LinmathbbR^ntimesn$ be any matrix such that $Q=L^TL$. Then the sets
$$ S_1=bigg x^TQx+b^Tx+cleqslant0bigg $$
and
$$ S_2=bigg_2leqslant(1-b^Tx-c)/2bigg $$
are equal.
This result makes no reference to the form of $L$, only that $Q=L^TL$. Hence, if there exist $L_1$ and $L_2$ such that $Q=L_1^TL_1$ and $Q=L_2^TL_2$, then the sets
$$ F_i=bigg_2leqslant(1-b^Tx-c)/2bigg $$
for $i=1,2$ are the same (as illustrated above), even though $L_1neqL_2$.
answered Aug 12 at 15:12
David M.
1,369318
1
Also, as Johan Löfberg notes, when you do this computationally with the eigenvalue decomposition, you can delete the columns of $V$ corresponding to zero eigenvalues ($0$ entries on the diagonal of $D$). This will save space and be more efficient.
– David M.
Aug 12 at 15:36
That seems like a great answer. Thank you.
– aslv95
Aug 12 at 16:26
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
As mentioned in the comments, your approach using the eigenvalue decomposition is correct. In this case, we have that
$$ Q=VDV^T$$
which can be written as
$$ Q=(VD^1/2)(VD^1/2)^T. $$
(As noted in the comments, other decompositions could work as well, but I'll use this one, since it's the one you mention). Your concern is that, if $Q$ is a positive definite matrix, then the matrix $L$ obtained by taking the Cholesky decomposition isn't the same as the matrix $VD^1/2$ obtained above. However, this doesn't mean that the resulting reformulation doesn't yield the same result in both cases.
Consider your example
$$ Q=beginpmatrix2&-5/2\-5/2&4endpmatrix.$$
If we take the Cholesky decomposition, then, to a few digits of accuracy,
$$ L=beginpmatrix1.414&0\-1.768&0.935endpmatrix. $$
If we take the eigenvalue decomposition, then, to a few digits of accuracy,
$$ VD^1/2=beginpmatrix-0.459&1.338\-0.311&-1.976endpmatrix. $$
Indeed, $LneqVD^1/2$. However, let's look at the plots of the level sets for all three formulations:
VoilÃÂ
Edit: A note on why this is true: essentially, we are employing this theorem:
Theorem: Let $QinmathbbR^ntimesn$ be positive semidefinite, and let $binmathbbR^n$, $cinmathbbR$. Let $LinmathbbR^ntimesn$ be any matrix such that $Q=L^TL$. Then the sets
$$ S_1=bigg x^TQx+b^Tx+cleqslant0bigg $$
and
$$ S_2=bigg_2leqslant(1-b^Tx-c)/2bigg $$
are equal.
This result makes no reference to the form of $L$, only that $Q=L^TL$. Hence, if there exist $L_1$ and $L_2$ such that $Q=L_1^TL_1$ and $Q=L_2^TL_2$, then the sets
$$ F_i=bigg_2leqslant(1-b^Tx-c)/2bigg $$
for $i=1,2$ are the same (as illustrated above), even though $L_1neqL_2$.
answered Aug 12 at 15:12
David M.
1,369318
1
Also, as Johan Löfberg notes, when you do this computationally with the eigenvalue decomposition, you can delete the columns of $V$ corresponding to zero eigenvalues ($0$ entries on the diagonal of $D$). This will save space and be more efficient.
– David M.
Aug 12 at 15:36
That seems like a great answer. Thank you.
– aslv95
Aug 12 at 16:26
add a comment |Â
up vote
1
down vote
accepted
As mentioned in the comments, your approach using the eigenvalue decomposition is correct. In this case, we have that
$$ Q=VDV^T$$
which can be written as
$$ Q=(VD^1/2)(VD^1/2)^T. $$
(As noted in the comments, other decompositions could work as well, but I'll use this one, since it's the one you mention). Your concern is that, if $Q$ is a positive definite matrix, then the matrix $L$ obtained by taking the Cholesky decomposition isn't the same as the matrix $VD^1/2$ obtained above. However, this doesn't mean that the resulting reformulation doesn't yield the same result in both cases.
Consider your example
$$ Q=beginpmatrix2&-5/2\-5/2&4endpmatrix.$$
If we take the Cholesky decomposition, then, to a few digits of accuracy,
$$ L=beginpmatrix1.414&0\-1.768&0.935endpmatrix. $$
If we take the eigenvalue decomposition, then, to a few digits of accuracy,
$$ VD^1/2=beginpmatrix-0.459&1.338\-0.311&-1.976endpmatrix. $$
Indeed, $LneqVD^1/2$. However, let's look at the plots of the level sets for all three formulations:
VoilÃÂ
Edit: A note on why this is true: essentially, we are employing this theorem:
Theorem: Let $QinmathbbR^ntimesn$ be positive semidefinite, and let $binmathbbR^n$, $cinmathbbR$. Let $LinmathbbR^ntimesn$ be any matrix such that $Q=L^TL$. Then the sets
$$ S_1=bigg x^TQx+b^Tx+cleqslant0bigg $$
and
$$ S_2=bigg_2leqslant(1-b^Tx-c)/2bigg $$
are equal.
This result makes no reference to the form of $L$, only that $Q=L^TL$. Hence, if there exist $L_1$ and $L_2$ such that $Q=L_1^TL_1$ and $Q=L_2^TL_2$, then the sets
$$ F_i=bigg_2leqslant(1-b^Tx-c)/2bigg $$
for $i=1,2$ are the same (as illustrated above), even though $L_1neqL_2$.
answered Aug 12 at 15:12
David M.
1,369318
1
Also, as Johan Löfberg notes, when you do this computationally with the eigenvalue decomposition, you can delete the columns of $V$ corresponding to zero eigenvalues ($0$ entries on the diagonal of $D$). This will save space and be more efficient.
– David M.
Aug 12 at 15:36
That seems like a great answer. Thank you.
– aslv95
Aug 12 at 16:26
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
As mentioned in the comments, your approach using the eigenvalue decomposition is correct. In this case, we have that
$$ Q=VDV^T$$
which can be written as
$$ Q=(VD^1/2)(VD^1/2)^T. $$
(As noted in the comments, other decompositions could work as well, but I'll use this one, since it's the one you mention). Your concern is that, if $Q$ is a positive definite matrix, then the matrix $L$ obtained by taking the Cholesky decomposition isn't the same as the matrix $VD^1/2$ obtained above. However, this doesn't mean that the resulting reformulation doesn't yield the same result in both cases.
Consider your example
$$ Q=beginpmatrix2&-5/2\-5/2&4endpmatrix.$$
If we take the Cholesky decomposition, then, to a few digits of accuracy,
$$ L=beginpmatrix1.414&0\-1.768&0.935endpmatrix. $$
If we take the eigenvalue decomposition, then, to a few digits of accuracy,
$$ VD^1/2=beginpmatrix-0.459&1.338\-0.311&-1.976endpmatrix. $$
Indeed, $LneqVD^1/2$. However, let's look at the plots of the level sets for all three formulations:
VoilÃÂ
Edit: A note on why this is true: essentially, we are employing this theorem:
Theorem: Let $QinmathbbR^ntimesn$ be positive semidefinite, and let $binmathbbR^n$, $cinmathbbR$. Let $LinmathbbR^ntimesn$ be any matrix such that $Q=L^TL$. Then the sets
$$ S_1=bigg x^TQx+b^Tx+cleqslant0bigg $$
and
$$ S_2=bigg_2leqslant(1-b^Tx-c)/2bigg $$
are equal.
This result makes no reference to the form of $L$, only that $Q=L^TL$. Hence, if there exist $L_1$ and $L_2$ such that $Q=L_1^TL_1$ and $Q=L_2^TL_2$, then the sets
$$ F_i=bigg_2leqslant(1-b^Tx-c)/2bigg $$
for $i=1,2$ are the same (as illustrated above), even though $L_1neqL_2$.
answered Aug 12 at 15:12
David M.
1,369318
As mentioned in the comments, your approach using the eigenvalue decomposition is correct. In this case, we have that
$$ Q=VDV^T$$
which can be written as
$$ Q=(VD^1/2)(VD^1/2)^T. $$
(As noted in the comments, other decompositions could work as well, but I'll use this one, since it's the one you mention). Your concern is that, if $Q$ is a positive definite matrix, then the matrix $L$ obtained by taking the Cholesky decomposition isn't the same as the matrix $VD^1/2$ obtained above. However, this doesn't mean that the resulting reformulation doesn't yield the same result in both cases.
Consider your example
$$ Q=beginpmatrix2&-5/2\-5/2&4endpmatrix.$$
If we take the Cholesky decomposition, then, to a few digits of accuracy,
$$ L=beginpmatrix1.414&0\-1.768&0.935endpmatrix. $$
If we take the eigenvalue decomposition, then, to a few digits of accuracy,
$$ VD^1/2=beginpmatrix-0.459&1.338\-0.311&-1.976endpmatrix. $$
Indeed, $LneqVD^1/2$. However, let's look at the plots of the level sets for all three formulations:
VoilÃÂ
Edit: A note on why this is true: essentially, we are employing this theorem:
Theorem: Let $QinmathbbR^ntimesn$ be positive semidefinite, and let $binmathbbR^n$, $cinmathbbR$. Let $LinmathbbR^ntimesn$ be any matrix such that $Q=L^TL$. Then the sets
$$ S_1=bigg x^TQx+b^Tx+cleqslant0bigg $$
and
$$ S_2=bigg_2leqslant(1-b^Tx-c)/2bigg $$
are equal.
This result makes no reference to the form of $L$, only that $Q=L^TL$. Hence, if there exist $L_1$ and $L_2$ such that $Q=L_1^TL_1$ and $Q=L_2^TL_2$, then the sets
$$ F_i=bigg_2leqslant(1-b^Tx-c)/2bigg $$
for $i=1,2$ are the same (as illustrated above), even though $L_1neqL_2$.
answered Aug 12 at 15:12
David M.
1,369318
edited Aug 12 at 15:33
answered Aug 12 at 15:12
David M.
1,369318
answered Aug 12 at 15:12
David M.
1,369318
answered Aug 12 at 15:12
David M.
1,369318
1,369318
1
Also, as Johan Löfberg notes, when you do this computationally with the eigenvalue decomposition, you can delete the columns of $V$ corresponding to zero eigenvalues ($0$ entries on the diagonal of $D$). This will save space and be more efficient.
– David M.
Aug 12 at 15:36
That seems like a great answer. Thank you.
– aslv95
Aug 12 at 16:26
add a comment |Â
1
Also, as Johan Löfberg notes, when you do this computationally with the eigenvalue decomposition, you can delete the columns of $V$ corresponding to zero eigenvalues ($0$ entries on the diagonal of $D$). This will save space and be more efficient.
– David M.
Aug 12 at 15:36
That seems like a great answer. Thank you.
– aslv95
Aug 12 at 16:26
1
1
Also, as Johan Löfberg notes, when you do this computationally with the eigenvalue decomposition, you can delete the columns of $V$ corresponding to zero eigenvalues ($0$ entries on the diagonal of $D$). This will save space and be more efficient.
– David M.
Aug 12 at 15:36
Also, as Johan Löfberg notes, when you do this computationally with the eigenvalue decomposition, you can delete the columns of $V$ corresponding to zero eigenvalues ($0$ entries on the diagonal of $D$). This will save space and be more efficient.
– David M.
Aug 12 at 15:36
That seems like a great answer. Thank you.
– aslv95
Aug 12 at 16:26
That seems like a great answer. Thank you.
– aslv95
Aug 12 at 16:26
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2878654%2fwriting-a-convex-quadratic-constraint-in-soc-form%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
$x^TQxleq 0$ where $Q$ is positive semidefinite is a bit silly, as that simply means $x$ has to be in the null-space of $Q$, i.e. it is a linear constraint.
– Johan Löfberg
Aug 11 at 12:57
1
I think you can use the eigenvalue decomposition and write it as $Q=VD^1/2D^1/2V^T=(VD^1/2)(VD^1/2)^T$.
– David M.
Aug 12 at 2:27
1
Also, the Cholesky decomposition is indeed defined for positive semidefinite matrices (see wiki page, for example), you just can't use the same algorithm to compute it. An $L D L^mathsfT$ decomposition of $Q$ can give a semidefinite Cholesky by breaking up the $D$ into $(D^1/2)^2$.
– cdipaolo
Aug 12 at 4:05
1
Just use any factorization based on, e.g., eigenvalue decomposition, SVD, or LDL. You will have zeros in the diagonal in the middle matrix, indicating that you can remove some of the rows and thus use a compressed factorization $Q=M^TM$ where $M$ is fat.
– Johan Löfberg
Aug 12 at 7:31
1
@aslv95 Not quite — my comment was about getting a bonafide Cholesky decomposition since L is lower triangular, but both solutions work equally well in theory.
– cdipaolo
Aug 12 at 16:19