2
$\begingroup$

The problem

I want to solve the following problem for symmetric matrix $X$:

$$ \begin{aligned} \min_{X\succ 0} \; & -\log(\det(X)) & \\ \text{subject to} \; & \begin{pmatrix} X & X\bar A^T\\ \bar AX & X \end{pmatrix} \succeq 0 \\& 1-g_i^TXg_i\geq 0 \\ & 1-h_l^TKXK^Th_l\geq 0\\ & \alpha \mathcal{T}^{-1}\succeq X \end{aligned} $$

where $\bar A, K, \mathcal{T}=\mathcal{T}^T, G, H$ are matrices and $g_i, h_l$ are the $i^{th}, l^{th}$ rows of $G, H$ respectively and the indices $i, l$ range from 1 upto the number of rows in $G, H$ respectively.

My attempts

I have managed to solve this without the two semidefinite constraints (the working code is below) but I am not able to figure out how to incorporate the two semidefinite constraints.

Code without the semidefinite constraints

This code successfully solves the problem by using Cholesky decomposition, which would automatically ensure $X$ is positive definite if the diagonal elements of $L$ are positive.

Abar={{0., 1.}, {-0.000165779, 4.97343*10^-7}};
T={{0.104851, 0.00645711}, {0.00645711, 0.106041}};
K={{-56.8, 0.000029995}};
alpha=0.2;

X = With[{L = {{a, 0}, {b, c}}}, L.Transpose[L]];
MAT = (K.X.Transpose[K])[[1]][[1]];

cons=True;

G = {{1/15, 0}, {-1/15, 0}, {0, 1/100}, {0, -1/100}};
H = {{1/10}, {-1/10}}; 
Do[cons = cons && 1 - G[[i]].X.G[[i]] >= 0, {i, Dimensions[G][[1]]}];
Do[cons = cons && 1 - H[[i]][[1]]*MAT*H[[i]][[1]] >= 0, {i, Dimensions[H][[1]]}]; 


NMinimize[{-Log[Det[X]], cons && a \[Element] Reals && a > 0 && b \[Element] Reals && c\[Element]Reals && c > 0}, {a, b, c}]

The output is {-5.73644,{a->0.176056,b->0.0299951,c->100.}}.

Code with semidefinite constraints

Now this code doesn't work. I read this answer and used the Thread[Eigenvalues[M]>=0] for my semidefinite constraints since both matrices in those constraints are symmetric. But it doesn't work. The following is my code.

Abar={{0., 1.}, {-0.000165779, 4.97343*10^-7}};
T={{0.104851, 0.00645711}, {0.00645711, 0.106041}};
K={{-56.8, 0.000029995}};
alpha=0.2;

X = With[{L = {{a, 0}, {b, c}}}, L.Transpose[L]];
MAT = (K.X.Transpose[K])[[1]][[1]];

cons=Thread[Eigenvalues[alpha*Inverse[T]] - X] >= 0] && Thread[Eigenvalues[ArrayFlatten[{{X,X.Transpose@Abar}, {Abar.X, X}}]] >= 0];

G = {{1/15, 0}, {-1/15, 0}, {0, 1/100}, {0, -1/100}};
H = {{1/10}, {-1/10}}; 
Do[cons = cons && 1 - G[[i]].X.G[[i]] >= 0, {i, Dimensions[G][[1]]}];
Do[cons = cons && 1 - H[[i]][[1]]*MAT*H[[i]][[1]] >= 0, {i, Dimensions[H][[1]]}]; 


NMinimize[{-Log[Det[X]], cons && a \[Element] Reals && a > 0 && b \[Element] Reals && c\[Element]Reals && c > 0}, {a, b, c}]

The errors it gives are like GreaterEqual::nord: Invalid comparison with 1.25754 -1.57974i attempted. So for some reason, it seems to be getting imaginary eigenvalues or something which should happen since all matrices are symmetric.

Other thoughts

I tried thinking about using the $LDL^T$ decomposition of positive semidefinite matrices with the condition that diagonal terms of the unique $D$ are non-negative or the fact that all principal minors of a positive semidefinite matrix are non-negative but couldn't figure out a way to incorporate the first one and the second one doesn't seem promising because as a trial case, I put the constraint that all leading principal minors of the semidefinite matrix are non-negative but the output was just NMinimize[...], no errors nothing just the input copied as output.

I would be extremely grateful if someone could help me out here! Thank you very much.

$\endgroup$
0
$\begingroup$

I got it and am posting this answer for others who might have this question in future. Of course, I am a beginner and any comments and suggestions on this will be helpful and welcome.

The SemidefiniteOptimization function is the way to go. It allows one to specify semidefinite cone constraints, which is same as a positive semidefiniteness constraint. The objective needs to be linear though, which as stated in my problem, is not. But fortunately, this example (on minimization of ellipsoid area) in this function's documentation tackles exactly that and we can equivalently write the objective function negative of trace of X. One more caveat is that numerical solvers (many if not all) do not prefer positive definiteness constraints and it's no different for this function, in fact, there's no way to give a positive definiteness constraint directly (one may use Cholesky decomposition and stuff but it lead to quadratic objective function. There may be a way to make that work but I haven't put much thought into that). Instead we ensure positive definiteness with some margin. I did it by constraining $X-0.001I_{2\times 2}$ to be inside a second order semidefinite cone, i.e., positive semidefinite.

I further cross-checked the answer obtained here with that from the well-tested YALMIP package in MATLAB and they match upto 2-3 decimal places. Here is the code:

Abar={{0., 1.}, {-0.000165779, 4.97343*10^-7}};
T={{0.104851, 0.00645711}, {0.00645711, 0.106041}};
K={{-56.8, 0.000029995}};
alpha=0.2;

X = {{a, b}, {b, c}};
MAT = (K.X.Transpose[K])[[1]][[1]];

cons = VectorGreaterEqual[{ArrayFlatten[{{X, X.Transpose@Abar}, {Abar.X, X}}],0},{SemidefiniteCone,4}] && VectorGreaterEqual[{alpha*Inverse@T - X,0},{SemidefiniteCone,2}]
 && VectorGreaterEqual[{X - 1/1000*IdentityMatrix[n],0},{SemidefiniteCone,2}];

G = {{1/20, 0}, {-1/20, 0}, {0, 1/5}, {0, -1/5}}; 
H = {{1/30}, {-1/30}}; 
Do[cons = cons && 1 - G[[i]].X.G[[i]] >= 0, {i, Dimensions[G][[1]]}];
Do[cons = cons && 1 - H[[i]][[1]]*MAT*H[[i]][[1]] >= 0, {i, Dimensions[H][[1]]}]; 


X = X /. SemidefiniteOptimization[-Tr[X], cons && a \[Element] Reals && b \[Element]Reals && c \[Element] Reals, {a, b, c}];
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.