Unit:
Κατεύθυνση Θεμελιώσεις Πληροφορικής και ΕφαρμογέςΠληροφορική
Author:
Repouskos Panagiotis
Supervisors info:
Ioannis Emiris, Professor, Department of Informatics & Telecoms, National & Kapodistrian University of Athens
Vassilis Zissimopoulos, Professor, Department of Informatics & Telecoms, National & Kapodistrian University of Athens
Gregory Karagiorgos, Associate Professor, Department of Informatics & Telecoms, University of Peloponnese
Original Title:
Sampling Methods, Spectrahedra and Convex Optimization
Translated title:
Sampling Methods, Spectrahedra and Convex Optimization
Summary:
We present algorithmic, complexity, and implementation results on the problem of sampling
points in the interior and the boundary of a spectrahedron, that is the feasible region of a
semidefinite program.
Our main tool is random walks. We define and analyze a set of primitive geometric
operations that exploits the algebraic properties of spectrahedra and the polynomial eigenvalue
problem, and leads to the realization of a broad collection of efficient random walks. We
demonstrate random walks that experimentally show faster mixing time than the ones
used previously for sampling from spectrahedra in theory or applications, for example Hit
and Run. Consecutively, the variety of random walks allows us to sample from general
probability distributions, for example the family of log-concave distributions which arise
frequently in numerous applications.
We apply our tools to specialize a randomized convex optimization algorithm for spectrahedra,
that is to solve semidefinite programs. We provide a C++ open source implementation
of several random walks that scale efficiently to a high number of dimensions (in our
experiments we tested till 300 dimensions) and of the convex optimization algorithm tailored
for spectrahedra.
Main subject category:
Technology - Computer science
Keywords:
sampling, convex optimization, spectrahedra, linear matrix inequalities, geometric random walks, semidefinite programming
