Efficient Algorithms for Geometric Optimization and Symmetric Cone Programming
COM1 Level 2
SR9, COM1-02-09
Abstract:
Geometric optimization is an important topic that attracts significant interest across many research areas, including computational geometry, machine learning, optimization, and computer graphics. A classic example of geometric optimization is the polytope distance (PD) problem, which involves finding the minimum distance between two convex polytopes, and is known to be the dual of the support vector machine (SVM) problem. Many geometric optimization problems can also be formulated as mathematical optimization problems and solved using techniques from optimization. In this thesis, we study efficient approximation algorithms for several geometric optimization problems and a versatile mathematical optimization model known as the symmetric cone program (SCP).
Our study begins by introducing a novel algorithmic framework -- the symmetric cone game (SCG) -- a zero-sum game over symmetric cones formulated in the language of Euclidean Jordan algebras (EJAs). We show that the SCG problem is equivalent to the problem of minimizing the largest eigenvalue in EJAs. Two algorithms are proposed to solve the SCG approximately, based respectively on online learning techniques and saddle-point theory. The theory and algorithms for SCG form the foundation of our discussions on geometric optimization and symmetric cone programming. In the future, the SCG framework holds great potential for broader applications in algorithm design.
Building on the SCG framework, we develop novel approximation algorithms for four geometric optimization problems: shortest connector (SC), smallest enclosing ball (SEB), smallest intersecting ball (SIB), and a soft-margin variant of SIB (Soft-SIB). In many cases, our algorithms are the first results in high-dimensional spaces, and are also the first fully polynomial-time approximation schemes (FPTAS). We also discuss the connections between these four problems and many other important problems in computational geometry and machine learning, including intersection radius, geometric median, hard-margin SVM, L1-SVM, and support vector data description (SVDD). This thesis then turns to the study of the mathematical optimization problem SCP. The problem generalizes the concepts of linear program (LP), semidefinite program (SDP), and second-order cone program (SOCP), and provides a unified language to study LPs, SDPs, and SOCPs. We propose two approximation algorithms for solving SCPs: one is primal-dual and the other is primal-only. They extend the LP approximation algorithm of Plotkin et al.~and the SDP algorithm of Arora and Kale.
Finally, we demonstrate that all the algorithms introduced in this thesis can be effectively parallelized, and are also efficient in practice. We show that the parallel versions of these algorithms achieve parallel depths that are polylogarithmic in the input size. From a practical perspective, we implemented our algorithm for the SIB problem in C++. To the best of our knowledge, this is the first software capable of computing SIBs for non-singleton inputs. Moreover, the algorithms for the PD/SVM and SEB problems are implemented in both sequential (CPU) and parallel (GPU) settings. Extensive experiments have shown that our parallel algorithms are GPU-friendly and possess fairly large parallelism. For large-scale input instances, our GPU solvers outperform the sophisticated solvers implemented in CGAL, Cplex, and Gurobi in these two problems.