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

where the objective function to be maximized is *concave*. Were it not for the Boolean constraints, we would have a convex optimization problem. Let us find bounds on the maximum.

### A naive lower bound

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

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

### An upper bound

Replacing the (non-convex) Boolean constraints $z_i \in \{0,1\}$ with the (convex) inequality constraints $z_i \in [0,1]$, the following convex relaxation of the original optimization problem

$$\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}$$

provides an **upper bound** on the maximum. In [0], Joshi & Boyd used Newton's method to solve the following approximation of the relaxed problem

$$\begin{array}{ll} \text{maximize} & \log \det \left( \displaystyle\sum_{i=1}^n z_i \mathrm W_i \right) + \gamma \displaystyle\sum_{i=1}^n \left( \log (z_i) + \log (1 - z_i) \right)\\ \text{subject to} & \displaystyle\sum_{i=1}^n z_i = s\end{array}$$

where $\gamma > 0$. Note that the latter is devoid of inequality constraints.

### Reference

[0] Siddharth Joshi, Stephen Boyd, Sensor Selection via Convex Optimization, IEEE Transactions on Signal Processing, Vol. 57, No. 2, pages 451-462, February 2009.

2more comments