Skip to main content
1 of 7

Given $n$ symmetric positive definite matrices $\mathrm W_1, \mathrm W_2, \dots, \mathrm W_n \in \mathbb R^{m \times m}$ and $s \in \mathbb N$, where $s < n$,

$$\begin{array}{ll} \text{maximize} & \det \left( \displaystyle\sum_{i=1}^n z_i \mathrm W_i \right)\\ \text{subject to} & \displaystyle\sum_{i=1}^n z_i = s\\ & \mathrm z \in \{0,1\}^n\end{array}$$

Since the matrices are positive definite and $z_i \geq 0$,

$$\det \left( \displaystyle\sum_{i=1}^n z_i \mathrm W_i \right) \geq \displaystyle\sum_{i=1}^n \det \left( z_i \mathrm W_i \right) = \displaystyle\sum_{i=1}^n z_i^m \det \left( \mathrm W_i \right) = \displaystyle\sum_{i=1}^n z_i \det \left( \mathrm W_i \right)$$

Let $c_i := \det \left( \mathrm W_i \right)$. The following binary integer program (IP)

$$\begin{array}{ll} \text{maximize} & \displaystyle\sum_{i=1}^n c_i z_i\\ \text{subject to} & \displaystyle\sum_{i=1}^n z_i = s\\ & \mathrm z \in \{0,1\}^n\end{array}$$

provides a lower bound on the maximum of the original optimization problem. This lower bound may be too loose, however. It would be nice to relax the integrality constraint and obtain an upper bound on the maximum, too.