Maximize the determinant of Boolean combinations of positive definite matrices I have the following optimization problem.
$$\begin{array}{ll} \text{maximize} & \det \left(\sum^n_{i=1}z_i W_i \right)\\ \text{subject to} & \sum_{i=1}^n z_i = N\\ & z_i 
\in \{0,1\}\end{array}$$
where


*

*all $W_i$ are given; they are constant, symmetric, and positive definite matrices.

*$N$ is also given and strictly less than $n$ (typically much less than $n$---for example, if $n = 200$, then $5 \leq N \leq 20$).
1 A sub-optimal or near-optimal solution is acceptable for my problem;
2 the maximum size of $W_i$ can be around $100 \times 100$.
Here are the questions. 
1 Is there any existed analytically strict solver/algorithm to handle this except random search type (that is, of derivative-free type) algorithm (which I have already tried, but found to be too slow)?
2 Is there a reformulation technique to re-cast it as convex as possible?  
3 Is there a reformulation technique to re-cast it as smooth as possible? 
One trick is to relax the $z_i$ to be continuous variables with values in $[0,1]$ (let's call it relaxed-ver1; but even if we go through this, the relaxed-ver1 sill involves a sum of a series of matrices weighted by the decision variables $z_i$. 
Now, I can write  down the gradient of the objective function w.r.t $z_i$, that is,  $\frac{\partial W}{\partial z_i} $ (I will type it here later); but the Hessian involves a matrix derivative    for the adjunct (or adjugate) matrix adj(W), so I will just stop here:
$$\frac{\partial \text{adj}(W)}{\partial z_i},$$
where $W = \sum^n_{i=1} z_i W_i$.

Another possibility is to change the objective functions to some "similar type". For example, I have already thought about using (1) quadratic forms;  (2)  traces (e.g., $\text{trace}\sum^n_{i=1}z_i W_i$);  (3) minimum eigenvalues. But so far, no additional progress.
 A: 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.
