Jon Lee

The 0/1 D-optimality problem and the maximum-entropy sampling problem are two well-known NP-hard discrete maximization problems in experimental design. Algorithms for exact optimization (of moderate-sized instances) are based on branch-and-bound. The best upper-bounding methods are based on convex relaxation. We present ADMM (Alternating Direction Method of Multipliers) algorithms for solving these relaxations and experimentally demonstrate their practical value.

Circuits are fundamental objects in linear programming and oriented matroid theory, representing the elementary difference vectors of a polyhedron between points in its affine space. A recent concept introduced by Ekbatani, Natura, and Végh, the circuit imbalance, serves as a complexity measure relevant to iteration bounds for circuit-based augmentation and circuit diameters, as well as the general interpretability of circuits in terms of the underlying application. In this paper, we analyze linear programming formulations of relaxed combinatorial optimization problems to prove two contrasting types of results related to the circuit imbalance. On one hand, we identify simple and common constraint structures, in particular arising in graph-theoretic problems, that inherently lead to an exponential circuit imbalance. These constructions show that, in quite general situations, working with the entire set of circuits poses significant challenges for an application of circuit augmentation or the study of circuit diameters. On the other hand, through a case study of two classic graph-theoretic problems with exponential imbalance, the vertex graph coloring problem and the maximum weight forest problem, we exhibit the existence of sets and subsets of highly interpretable circuits of (best-case) imbalance 1. These sets correspond to the recoloring of vertices or to the addition or removal of edges, respectively, for example generalizing classic concepts of Kempe dynamics in coloring. Their interpretability in terms of the underlying application facilitates a study of circuit walks in the corresponding polytopes. We prove that a restriction of circuit walks to these sets suffices to not only guarantee reachability of the integral extreme-points of the skeleton, but leads to linear and constant circuit diameter bounds, respectively.

We give sparsity results and present algorithms for calculating minimum (vector) 1-norm universal solvers connected to least-squares problems. In particular, besides universal least-squares solvers, we consider minimum-rank universal least-squares solvers, and simultaneous universal minimum-norm/least-squares solvers. For all of these, we present and compare several new alternative linear-optimization formulations and very effective proximal-point algorithms. Overall, we found that our new Douglas-Rachford splitting algorithms for these problems performed best.