I am interested in maximizing a quadratic form which looks like $$f(\Sigma) = E(\operatorname{trace}(SJ)) = E(1^{\top} S 1)$$ where $J$ is a matrix of $1$'s, $S= \Sigma_{mm} - \Sigma_{mo} \Sigma_{oo}^{-1} \Sigma_{om}$ is the Schur complement in a covariance matrix $$\Sigma = \begin{pmatrix} \Sigma_{oo} & \Sigma_{om} \\ \Sigma_{mo} & \Sigma_{mm} \end{pmatrix}$$ and $E(\cdot)$ is an expectation operator which randomizes the indicies of $\Sigma$. If $\Sigma$ is $n \times n$, then $\{o, m\}$ is a partition of $\{1, \ldots, n\}$ such that $\Sigma_{oo} = \{\Sigma_{ij} : i, j \in o\}$, and similarly for $\Sigma_{om}, \Sigma_{mo}, \Sigma_{mm}$. For each $i$, the probability that $i \in m$ is $w_i$; for concreteness, let $n = 100$ and $w_i$ evenly spaced on a grid from $0.5$ to $0.9$. We also impose the constraint $\Sigma_{ii} = 1$ so that the problem is solvable. Note that I'm being sloppy in how I defined $\Sigma$, since $\Sigma$ is fixed but $\{o,m\}$ is random; hopefully it is clear what I mean.

In a perfect world, I would be able to optimize $\Sigma$ analytically. A numerical solution would also be helpful. I have been attempting to optimize $f(\Sigma)$ using a Robbins-Monro type stochastic approximation algorithm. This involves alternating between sampling $\{o,m\}$ and then moving along the gradient of the objective, with a Lagrangian term to attempt to stop from violating the positive semidefinite constraint, or that $\Sigma_{ii} = 1$. This seems to work OK. The main trouble is that the solutions depend heavily on the initialization, and can lead to violations of the positive-definite requirement for $\Sigma$. But it did lead to finding some $\Sigma$'s which disproved some conjectures I had. (My personal record is $f(\Sigma) \ge 200$ for my concrete version.)

In summary, if it isn't obvious, I am mostly clueless on this problem. If not solutions, pointers to any relevant literature are greatly appreciated.

  • $\begingroup$ Does this problem pertain to a real-world problem or application? $\endgroup$ Jul 19, 2017 at 0:23
  • $\begingroup$ @MarkL.Stone It is motivated by a statistical problem. Suppose I have a vector $\mu$ and I want to estimate $\psi=n^{-1}\sum_i\mu_i$. The probability of observing $\mu_i$ is $1-w_i$. A standard way to cook up good estimators is to derive the Bayes estimator of $\psi$ under a "least favorable" prior. Given a Gaussian prior with mean $0$ and covariance $\Sigma$, the expression $f(\Sigma)$ is the expected posterior variance of $\psi$ (the Bayes risk under squared error loss), and optimizing wrt $\Sigma$ gives the least favorable prior within the class of Gaussian priors with $\Sigma_{ii} = 1$. $\endgroup$
    – tony
    Jul 19, 2017 at 2:30
  • $\begingroup$ @MarkL.Stone If you are asking whether I have a particular real problem in-hand, my interest is academic. $\endgroup$
    – tony
    Jul 19, 2017 at 2:39
  • $\begingroup$ How is $S$ defined for a sample in which $m$ is empty? Is $S$ considered to be an empty matrix and therefore the contribution toward the objective function is $0$ for that sample? Or is such a sample disallowed, i.e., do acceptance/rejection, and samples having $m$ empty are the only samples which are rejected? Or if something else, please specify. $\endgroup$ Aug 8, 2017 at 19:04
  • $\begingroup$ @MarkL.Stone when $m$ is empty, the contribution to the objective is zero. The probability of this happening is exponentially small, so it should not matter. As of the last time I worked on this, I have been moving along the stochastic gradient and then contracting back onto the cone of PSD matrices by setting any negative eigenvalues of $\Sigma$ to $0$. $\endgroup$
    – tony
    Aug 9, 2017 at 20:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.