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.