Session: Convex approaches to SDP
Chair: Richard Zhang
Cluster: Conic and Semidefinite Optimization
Talk 1: Fitting Tractable Convex Sets to Support Function Data
Speaker: Venkat Chandrasekaran
Abstract: The geometric problem of estimating an unknown compact convex set from evaluations of its support function arises in a range of scientific and engineering applications. Traditional approaches typically rely on estimators that minimize the error over all possible compact convex sets; in particular, these methods do not allow for much incorporation of prior structural information about the underlying set and the resulting estimates become increasingly more complicated to describe as the number of measurements available grows. We address both of these shortcomings by describing a new framework for estimating tractably specified convex sets from support function evaluations. Along the way, we also present new bounds on how well arbitrary convex bodies can be approximated by elements from structured non-polyhedral families of convex sets. Our numerical experiments highlight the utility of our framework over previous approaches in settings in which the measurements available are noisy or small in number as well as those in which the underlying set to be reconstructed is non-polyhedral. (Joint work with Yong Sheng Soh and Eliza O'Reilly.)
Talk 2: Iterative methods for primal-dual scalings in conic optimization
Speaker: Lieven Vandenberghe
Abstract: A central element in the design of primal-dual interior-point methods for conic optimization is the definition of a suitable primal-dual scaling or metric. The talk will discuss simple iterative methods for computing primal-dual scalings. We will consider the Nesterov-Todd scaling for symmetric cones and extensions to sparse positive semidefinite matrix cones.
Talk 3: Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
Speaker: Nathan Benedetto Proenca
Abstract: We provide a primal-dual framework for randomized approximation algorithms utilizing semidefinite programming (SDP) relaxations. Our framework pairs a continuum of APX-complete problems including MaxCut, Max2Sat, MaxDicut, and more generally, Max-Boolean Constraint Satisfaction and MaxQ (maximization of a positive semidefinite quadratic form over the hypercube) with new APX-complete problems which are stated as convex optimization problems with exponentially many variables. These new dual counterparts, based on what we call Grothendieck covers, range from fractional cut covering problems (for MaxCut) to tensor sign covering problems (for MaxQ). For each of these problem pairs, our framework transforms the randomized approximation algorithms with the best known approximation factors for the primal problems to randomized approximation algorithms for their dual counterparts with reciprocal approximation factors which are tight with respect to the Unique Games Conjecture. For each APX-complete pair, our algorithms solve a single SDP relaxation and generate feasible solutions for both problems which also provide approximate optimality certificates for each other. Our work utilizes techniques from areas of randomized approximation algorithms, convex optimization, spectral sparsification, as well as Chernoff-type concentration results for random matrices.
