log(det(X)) in Semidefinite Programming

Question

I have been solving problems of the form $$max \ log(det(A)) \\ s.t. \ A = A^{T} \succeq 0, \\ p_{i}^{T}Ap_{i} \leq b_{i}$$ where $b_{i}$ and $p_{i}$ are input vectors (to be clear there is more than one vector $b_{i}$ and $p_{i}$), using CVXPY and SCS. What I am finding is that the transformation into canonical form takes a significant amount of time (in fact, it takes longer than actually solving the resulting SDP). My first thought was to do the transformation manually before hand (i.e. express the problem in the form SCS is expecting), but I'm having trouble figuring out how to express $log(det(A))$ in the form of $c^{T}x$.

For reference, SCS solves problems of the form $$min \ c^{T}x \\ s.t. Ax=b, \\ A \in K$$ where $K$ is a convex cone (in this case, the positive semidefinite cone).

My first thought was to define a new variable $L=log(A)$ and now calculate $tr(L)$, but $L=log(A)$ is not a linear constraint so that doesn't seem to get me anywhere. I know this can be done in some form (otherwise CVXPY wouldn't be able to send the problem to SCS in the first place) but it's very much opaque to me.

EDIT: Clarified that there is more than one input vector, and thus more than one constraint on the extent of $A$.

Answer 1

First of all, move the objective to the constraints by using the epigraph formulation

max t

subject to log_det(A) $\ge$ t

plus your other constraints.

Section 6.2.3 of the Mosek Modeling Cookbook https://docs.mosek.com/modeling-cookbook/sdo.html#semidefinite-modeling shows how to formulate log_det(A) $\ge$ t in terms of a combination of SDP and exponential cone constraints, both of which SCS supports.

However, in your case, you can just as well maximize the nth root of the determinant of A, which eliminates the log, thereby avoiding the exponential cone, in favor of power cone or Second Order Cone constraints. As per the tip at the end of section 6.2.3, you can use the formulation in section 4.2.4 https://docs.mosek.com/modeling-cookbook/powo.html to use SCS's power cone constraints to handle the geometric mean of the eigenvalues of A, which in turn are the diagonal elements of the matrix "Z" introduced for the SDP constraint as shown in section 6.2.3. Alternatively, you can formulate the geometric mean in terms of Second Order Cone constraints.

It's messy to type all this out, so I leave that to you.

Answer 2

The determinant is the product of all eigenvalues $\lambda_i(A)$, so its logarithm is the sum of the logarithms of the eigenvalues. As a consequence, you can write the objective function as follows: $$ \min_A \quad-\sum_i \log\lambda_i(A). $$ Now, assume you had an eigenvalue that tried to go to zero, then its logarithm would go to negative infinity and so its negative logarithm would go to positive infinity. In other words, the objective function is also implicitly a log barrier method ensuring positive definiteness of the matrix. Your first constraint them simplifies to $$ \text{s.t.}\quad A=A^T. $$ The second constraint implies that $$ \min_i \lambda_i(A) \le \frac{b}{\|p\|^2}. $$ This is a bit tricky to understand, but you can see this in the following way: Let's say you are given a matrix $A$ and $v_i$ are its eigenvectors. Then $$ p^T A p = \sum_i \lambda_i (p\cdot v_i)^2. $$ That's because the eigenvectors for a symmetric positive definite matrix form an orthogonal basis. As a consequence, $$ p^T A p \ge (\min_i \lambda_i) \|p\|^2. $$ The minimum is attained if $p \parallel v_\text{min}$.

So then here is how you would construct a matrix that maximizes your objective function (or minimizes mine):

• Pick a matrix with one eigenvector equal to $v_1=\frac{p}{\|p\|}$ and corresponding eigenvalue $\lambda_1=\frac{b}{\|p\|^2}$.
• Choose the remaining $n-1$ eigenvectors however you please but so that they form an orthonormal basis. Choose their eigenvalues as you please -- including larger than $\lambda_1$.

Because you can choose the other eigenvalues however you please, it is now clear that you can make your objective function as large as you like. In other words, the construction shows that the problem you posed does not have a solution: There is no maximum of the set of matrices you consider that could be attained.

(By way of example, choose $p=(1,0)^T$ and $b=1$. Then any matrix of the form $$ A=\begin{pmatrix}1 & 0 \\ 0 & \alpha\end{pmatrix} $$ satisfies your constraints with $\alpha>0$. The objective function you have is $\log\text{det}A=\log\alpha$, which you can make as large as you like.)