This content will become publicly available on December 14, 2022

Globally Convergent Low Complexity Algorithms for Semidefinite Programming
Semidefinite programs (SDP) are a staple of today’s systems theory, with applications ranging from robust control to systems identification. However, current state-of-the art solution methods have poor scaling properties, and thus are limited to relatively moderate size problems. Recently, several approximations have been proposed where the original SDP is relaxed to a sequence of lower complexity problems (such as linear programs (LPs) or second order cone programs (SOCPs)). While successful in many cases, there is no guarantee that these relaxations converge to the global optimum of the original program. Indeed, examples exists where these relaxations "get stuck" at suboptimal solutions. To circumvent this difficulty in this paper we propose an algorithm to solve SDPs based on solving a sequence of LPs or SOCPs, guaranteed to converge in a finite number of steps to an ε-suboptimal solution of the original problem. We further provide a bound on the number of steps required, as a function of ε and the problem data.
Authors:
;
Award ID(s):
Publication Date:
NSF-PAR ID:
10349424
Journal Name:
60th IEEE Conf. Decision and Control
Page Range or eLocation-ID:
1709 to 1714
We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$$w:N\to {R}_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$${f}_{1},{f}_{2},\dots ,{f}_{r}$overNand requirements$$k_1,k_2,\ldots ,k_r$$${k}_{1},{k}_{2},\dots ,{k}_{r}$the goal is to find a minimum weight subset$$S \subseteq N$$$S\subseteq N$such that$$f_i(S) \ge k_i$$${f}_{i}\left(S\right)\ge {k}_{i}$for$$1 \le i \le r$$$1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$$r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$$O\left(log\left(kr\right)\right)$approximation where$$k = \sum _i k_i$$$k={\sum }_{i}{k}_{i}$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$$\left(1-1/e-\epsilon \right)$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$$O\left(\frac{1}{ϵ}logr\right)$in the cost. Second, we consider the special case when each$$f_i$$${f}_{i}$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraintsmore »