Maximize the determinant of Boolean combinations of positive definite matrices

Question

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.

Answer 1

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.

Answer 2

Instead of requiring the solution $(z_1,\dots,z_n)$ to lie on a the vertices of a convex polyhedron or even the boundary of the complex polyhedron, a standard optimization algorithm is much more successful if we simply required $(z_1,\dots,z_n)\in S^{n-1}$. Or equivalently, we can just maximize $$\begin{equation}\log(|\det(\sum_{k=1}^nz_kA_k)|)-\frac{m}{2}\cdot\log(|z_1|^2+\dots+|z_n|^2).\end{equation}{\,\,\,(1)}$$

Suppose that $U$ is an open subset $K^n$ where $K\in\{\mathbb{R},\mathbb{C}\}$ and where if $\lambda\in K\setminus\{0\}$ and $\mathbf{z}\in U$, then $\lambda\mathbf{z}\in U$ as well. We say that a function $f:U\rightarrow\mathbb{R}$ is homogeneous of degree $d$ if $f(\lambda z_1,\dots,\lambda z_n)=\lambda^d f(z_1,\dots,z_n).$ As a general rule of thumb, if $f:U\rightarrow K^n$ is homogeneous of degree $d$, and $f$ came from linear algebra, then when you maximize $f(z_1,\dots,z_n)$ on the sphere $\{\mathbf{z}\in K^n:\|\mathbf{z}\|=1\}$ multiple times, the optimization process will often to converge to the same local maximum. At the very least, the probability distribution of optimized values $f(z_1,\dots,z_n)$ will often have low entropy, and the most common values of $f(z_1,\dots,z_n)$ will tend to be the highest possible values of $f(z_1,\dots,z_n)$.

If the matrices $(A_1,\dots,A_n)$ are all positive semidefinite, then the gradient ascent process that maximizes (1) will tend to converge to the same value if you maximize (1) multiple times. This no longer holds if we do not assume any positive semidefiniteness of $(A_1,\dots,A_n).$

Real or complex: For the problem of optimizing (1), if we set $K=\mathbb{R}$, then the set $\{(x_1,\dots,x_n)\in K^n\mid\det(\sum_{k=1}^nx_kA_k)\neq 0\}$ will not be connected and the global maximum may be on a different component than the initialization. This is not as bad as it seems because the gradient ascent process is good at jumping from one component to another component until it hits an optimal or nearly optimal local maximum, and if $K=\mathbb{C}$, then the set $\{(z_1,\dots,z_n)\in K^n\mid\det(\sum_{k=1}^nz_kA_k)\neq 0\}$ is connected, so there are no disconnectedness issues in the complex case; one may also initialize each $z_j$ to be positive to ensure convergence in the positive semidefinite case. If the matrices $(A_1,\dots,A_n)$ are all real or complex positive definite, and $(z_1,\dots,z_n)$ optimizes (1), then one will tend to be able to find a $\lambda$ where $\lambda z_j$ is positive for $1\leq j\leq n.$

I do not know of a good way of getting a Boolean solution from the spherical solution or even a solution where $z_1,\dots,z_n\in[0,1]$.