maximize log determinant subject to a linear constraint

Does anyone know any efficient method to solve the following problem?

$(\alpha,\beta) = \text{argmax} \log \det (\alpha K_1 + \beta K_2)$

s.t. $c_1 \alpha + c_2 \beta = c_3, \alpha\geq0, \beta\geq 0$

where $K_1$ and $K_2$ are known positive semi-definite matrix and $c_1$, $c_2$ and $c_3$ are known constant.

Many thanks!

• How big will $K_1$ and $K_2$ approximately be? In case they are large: are they sparse or do they have some other additional structure besides being s.p.d.? Feb 16, 2013 at 12:26
• @ElmarZander $K_1$ and $K_2$ are high-dimensional (about several hundreds), sparse and diagonally dominant matrices
– Hugo
Feb 17, 2013 at 7:55

Here is a simple starting point, say if $K_1$ is (strictly) positive definite. Since $$\det(\alpha K_1 + \beta K_2) = \det(K_2) \det(\alpha K_2^{-1} K_1 + \beta I),$$ the problem is reduced to the case where one of the matrices is identity.

Now, let $K_2^{-1} K_1 = U \Lambda U^T$ be a spectral decomposition, where $\Lambda = \text{diag}(\lambda_1,\dots,\lambda_n)$. Then, the problem is $$\max \sum_{i=1}^n \log(\alpha \lambda_i + \beta)$$ subject to constraints. Assuming that one of $c_1$ or $c_2$ is $>0$, say $c_1 > 0$, you can write $\alpha = c'_3 + c_2' \beta$ and turn the problem into a one dimensional problem on $\beta$.

If none of $K_1$ or $K_2$ is p.d., you might try adding a perturbation, say $K_2' = K_2 + \epsilon I$.

• That's indeed a very good starting point. However, $K_1$, $K_2$ here are large matrix, thus it's costly to compute the inverse. Sorry for the confusion.
– Hugo
Feb 17, 2013 at 6:09
• You don't need to compute the inverse. You only need to solve the generalized eigenvalue problem $K_1 v = \lambda K_2 v$. It might be possible to do this faster (not sure.) Feb 17, 2013 at 12:19
• True, but computing the spectral decomposition isn't cheap either, if $K_1$ and $K_2$ are large. Feb 18, 2013 at 13:44

I guess you can use below property:

The determinant behaves like a linear function on the rows of the matrix such as

$$det(\alpha K + \beta L)=\begin{vmatrix} \alpha K_{1,1}+\beta L_{1,1}&\alpha K_{1,2}+\beta L_{1,2}\\\alpha K_{2,1}+\beta L_{2,1}&\alpha K_{2,1}+\beta L_{2,2}\end{vmatrix}$$

$$\Rightarrow \alpha^2\begin{vmatrix} K_{1,1}&K_{1,2}\\K_{2,1} & K_{2,1}\end{vmatrix}+\alpha \beta\begin{vmatrix} K_{1,1}&K_{1,2}\\L_{2,1} & L_{2,1}\end{vmatrix}+\alpha \beta\begin{vmatrix} L_{1,1}&L_{1,2}\\K_{2,1} & K_{2,1}\end{vmatrix}+\beta^2\begin{vmatrix} L_{1,1}&L_{1,2}\\L_{2,1} & L_{2,1}\end{vmatrix}$$

It may be easier to construct the matrices than taking inverses.