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

• seems like a good candidate for a greedy method (of course, here $N>n$, otherwise $z_i=1$ for all $i$ would be a valid solution)....you may benefit from searching the literature on greedy optimization of set functions. – Suvrit Apr 4 '17 at 2:58
• I would try tabu search or simulated annealing. But I suspect (depending on the choice of the matrices) this could be a very hard problem. – Robert Israel Apr 4 '17 at 7:06
• @Suvrit, thanks for replying. I forgot to mention that N is strictly much less than n due to my problem background. I have a glance at the set function optimization as you mentioned, not understanding too much but I will keep reading. Thanks. – ZPascal Apr 4 '17 at 13:32
• @RobertIsrael. Thanks for replying. Well, as I mentioned, I am looking for some "deterministic" optimization algorithm except 'random search' type method like GA, PSO, TABU, etc. A reason is: even a 'deterministic' algorithm can give only sub-optimal as well, however, its run time is estimable/deterministic not like 'random search' type method, sometimes you may get luck; sometimes it runs too long. In addition, all W_i matrices are given symmetric real positive semi-definite, that is why I doubt there might exist some beautiful algorithm to handle it. Thanks. – ZPascal Apr 4 '17 at 13:36
• Sorry, i meant $N<n$ :-) because $N>n$ is not achievable under the integer constraints! Have a look at Sagnol's PhD thesis for some hints: zib.de/sagnol – Suvrit Apr 4 '17 at 15:00

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 , 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

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

• Thank you. I have thought of this lower bound before, the reason why I did not go further on that because it is too simple: a greedy algorithm (pick the s largest c_i can solve it); After relaxing z_i to be continuous in [0,1]. As I mentioned previously, I have derived formula for first order derivative , i.e. gradient. Using algorithm like Conjugate gradient or BFGS type methods, etc., of which only exact analytic gradient formula is required but no need for exact analytic Hessian formula. – ZPascal Apr 5 '17 at 18:22
• Nice! Appreciate! – ZPascal Apr 28 '17 at 1:30