5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Suvrit Apr 4 '17 at 2:58
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Apr 4 '17 at 7:06
  • $\begingroup$ @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. $\endgroup$ – ZPascal Apr 4 '17 at 13:32
  • $\begingroup$ @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. $\endgroup$ – ZPascal Apr 4 '17 at 13:36
  • 1
    $\begingroup$ 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 $\endgroup$ – Suvrit Apr 4 '17 at 15:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ZPascal Apr 5 '17 at 18:22
  • $\begingroup$ Nice! Appreciate! $\endgroup$ – ZPascal Apr 28 '17 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.