I want to solve an optimization that minimize log_det( I + inv(X) ) under the semidefinite constraint and some linear constraints to X. For the background of this problem, see this reference.
As mentioned in this reference, though log_det( I + inv(X) ) is a convex function of X, numerically solving the problem is not easy.
I tried to express the function in CVX as log_det( I + inv(X) ) and log_det( X + I ) - log_det( X ). However, CVX cannot accept these expressions.
I want to know whether CVX is able to handle the function. If not, is there any other softwares that can handle the function?
The trick in the scalar case linked by @Mark_L_Stone is to rewrite the argument to the log-function as a harmonic mean, so the inversion can be used to flip the sign of the log-function, i.e.:
t >= log(1 + 1/x) = log(1 / (x / (x+1)) ) = log(1 / (1-1/(x+1)) )
so that it can be rewritten:
-t <= log( 1 - 1/(x+1) )
and then you just substitute out 1/(x+1) for a dummy variable using a quadratic cone.
This generalize to the matrix case step-by-step as follows:
t >= log(det( I + inv(X) )) = log(det( inv(X*inv(X+I)) ) = log(det( inv(I - inv(X+I)) ))
so that it can be rewritten:
-t <= log(det( I - inv(X+I) ))
but I am missing a matrix-equivalent for substituting out inv(X+I).
is equivalent to -t \leq \log(\det( I - {\rm inv}(X+I) ))
is equivalent to -t \leq \log(\det( I - U )) U \succeq {\rm inv}(X + I)
is equivalent to -t \leq \log(\det( I - U )) \left[\begin{array}{cc}X+I & I\\I & U\end{array}\right] \succeq 0
The first step follows from the scalar to matrix generalization above which you can prove more rigidly. The second step follows by applying \log(\det( I - U )) \leq \log(\det( I - V )) on I \succeq U \succeq V to our case with V = {\rm inv}(X + I). The last step is the Schur complement lemma.
Thanks @hfriberg. I implemented your idea in CVX and it worked.
The equivalent optimization problem is
\begin{align}
\mathrm{max} \ & \ \log \det ( I - U ) \\
\mathrm{s.t.} \ & \ X \succeq 0 \ \text{and some linear constrains to} \ X \\
& \ I - U \succeq 0 , \\
& \ \left[
\begin{array}{cc}
X + I & I \\ I & U
\end{array}
\right] \succeq 0
\end{align}
Here, I add I - U \succeq 0 to ensure continuity of the function.
At first I also considered to apply Schur complement and introduce a variable V \succeq X ^ {-1}, but the optimization became minimizing a log_det function, will is concave. The first equivalence in the trick converts the target to be maximing a log_det function. That’s really ingenious
The I - U \succeq 0 part is redundant in cvx and may lower performance. Arguments to log_det are implicitly constrained this way already, as you’ll find in the cvx reference:
When used inside a CVX specification, log_det constrains its argument to be symmetric (if real) or Hermitian (if complex) and positive definite.
Hello @hfriberg@Mark_L_Stone , I am having a similar problem, where my objective is to minimize -log(det(I-W inv(X) W'), W and X are both variables. The problem is convex both in W and X, as -logdet() is convex and nondecreasing, and inv(X) and XAX' are both convex functions in X. Is there a way to convert it into a standard SDP?
Edit: I misread the - as +. Presuming X > 0, the objective is convex for the scalar case, due to quad_over_lin
If X is a matrix, but W is a row vector (so that I is just the scalar 1), then minimize(-log(1-matrix_frac(W',X))) can be used. or more simply minimize(matrix_frac(W',X)) to get the same argmin, But i don’t see how to generalize this for W being a matrix having more than 1 row.
@Mark_L_Stone The objective is -logdet(1-W^2/X) with a minus sign. Since -logdet(-x) is convex and nondecreasing, and both 1/x and w^2 are convex, the objective is convex in both x and w. Thanks!
By Schur’s formula, and presuming X should be constrained to psd (which my formulation will do), det([I W;W' X]) = det(X)*det(I - W*inv(X)*W')
However, this leads to -log_det(I - W*inv(X)*W') = -log_det([I W;W' X]) + log_det(X)
which will not work.
I have not yet reached a conclusion as to whether the objective is convex when X is a matrix and W is not a row vector (see my previous (edited) post for formulation when W is a row vector).
If the objective is convex, I’ll leave a possible reformulation for someone else to provide.
I think I got it. It’s very much inspired by the response from @hfriberg. If we introduce a slack variable U, then the problem is equivalent to min (-\log\det(I-U)), U-W*inv(X)*W >=0. The objective now is accepted by cvx, and the constraint is a SDP constraint by Schur complement.
