We study semidefinite relaxations of the problem of maximizing a concave function of quadratic forms on the unit sphere. When this function is a fractional power 0 < p < 1, we obtain tight approximation factors by analyzing a randomized rounding procedure. When p=1/2, this problem and its relaxation is equivalent to Max-Cut, and the approximation guarantees we obtain matches the best known factors, and can be interpreted as obtaining a generalization of Nesterov's 2/pi approximation result. When the solution of the semidefinite program has a low rank, our analysis obtains further improved bounds. We extend this analysis to other concave functions such as logarithms and entropy. Finally, we show that this rounding procedure and analysis can also be generalized to optimization on the Stiefel manifold.

If a sparse semidefinite program (SDP), specified over $n\times n$ matrices and subject to $m$ linear constraints, has an aggregate sparsity graph $G$ with small treewidth, then chordal conversion will frequently allow an interior-point method to solve the SDP in just $O(m+n)$ time per-iteration, which is a significant speedup over the $\Omega(n^{3})$ time per-iteration for a direct application of the interior-point method. Unfortunately, the speedup is not guaranteed by a small treewidth in $G$, as a diagonal SDP would have treewidth zero but can still necessitate up to $\Omega(n^{3})$ time per-iteration. Instead, we construct an extended aggregate sparsity graph $\overline{G}\supseteq G$ by forcing each constraint matrix $A_{i}$ to be its own clique in $G$. We prove that a small treewidth in $\overline{G}$ does indeed guarantee that chordal conversion will solve the SDP in $O(m+n)$ time per-iteration, to $\epsilon$-accuracy in at most $O(\sqrt{m+n}\log(1/\epsilon))$ iterations. This sufficient condition covers many successful applications of chordal conversion, including the MAX-$k$-CUT relaxation, the Lovász Theta problem, sensor network localization, polynomial optimization, and the AC optimal power flow relaxation, thus allowing theory to match practical experience.

We introduce convex optimization methods to find upper bounds on the expected independence number of a random graph. These upper bounds are inspired by the well known Lovász theta function, which bounds for the independence number of a deterministic graph using a semidefinite program. Specifically, we propose a hierarchy of semidefinite programs (SDPs) which depend on the probabilities that given subsets of vertices in the random graph are independent. These semidefinite programs have values which each upper bound the expected independence number of the random graph. We discuss cases in which this hierarchy offers a close approximation to the true expected independence number and cases in which it is far away from the true expected independence number. These semidefinite programming bounds are related to the usual Lasserre hierarchy for general boolean quadratic optimization. For symmetric random graphs, the last level of the hierarchy is equivalent to a linear program whose optimal value can often be calculated or approximated in closed form and which have close connections to combinatorics. We show that our methods provide good upper bounds in a number of examples, including Erdős-Rényi graphs, uniformly random spanning trees, and geometric random graphs. We also discuss empirical results.