2
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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.? $\endgroup$ Feb 16, 2013 at 12:26
  • $\begingroup$ @ElmarZander $K_1$ and $K_2$ are high-dimensional (about several hundreds), sparse and diagonally dominant matrices $\endgroup$
    – Hugo
    Feb 17, 2013 at 7:55

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Hugo
    Feb 17, 2013 at 6:09
  • $\begingroup$ 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.) $\endgroup$
    – passerby51
    Feb 17, 2013 at 12:19
  • $\begingroup$ True, but computing the spectral decomposition isn't cheap either, if $K_1$ and $K_2$ are large. $\endgroup$ Feb 18, 2013 at 13:44
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .