Skip to content

Geometric sampling, volume and optimization

Jump to bottom Edit New page
Panagiotis Repouskos edited this page Mar 27, 2019 · 9 revisions

Background

Convex optimization and volume computation are fundamental problems in mathematics and computer science with many applications that span the whole spectrum of sciences and engineering. It appears, for example, in problems in statistics, biology, and economics, to name a few concrete application areas.

Related work

The R package 'geometry' makes the qhull library (www.qhull.org) available in R. Qhull can compute volumes of convex polytopes but scales only to low dimensions (typically less than 10). For convex optimization there are many R packages see for example here for an overview. The method proposed by this project has the advantages of being novel, not implemented in R (or a similar environment) and thus it is open whether it will be competitive to current methods in R.

Details of your coding project

VolEsti (https://github.com/GeomScale/volume_approximation) is a C++ package with an R interface that performs efficient high dimensional sampling and volume computation. It supports a variety of convex polytope representations and scales to high (i.e., a few hundred) dimensions. To our knowledge it is the only software that combines the above features.

The main purpose of this year’s projects is to extent VolEsti’s functionality and as a consequence to provide state-of-the-art algorithms for sampling and volume computations to the R-project. We propose the following projects:

Project 1. Sampling scalability

This project contains the empirical study of random walks for convex polytopes (mainly given by a set of linear inequalities). Currently variations of hit-and-run random walks are used but there are methods in bibliography with better mixing time; most notably the hamiltonian walk https://arxiv.org/pdf/1710.06261.pdf. We expect that an efficient implementation of such a method to have a dramatic effect in the scaling of the underlying algorithms (mainly sampling and volume computations, but there are also connections to convex optimization). We set the ultimate goal in one sentence: “scale from a few hundred dimensions to a few thousand”.

We can divide the coding project in the following steps:

  • Understand the code structure and design of VolEsti.
  • Create prototypes for new sampling algorithms (the main focus will be in Hamiltonian walk but we may investigate others too).
  • Implement the best representatives from the previous step in VolEsti and create R interfaces.
  • Write tests and documentation.

Project 2. Sampling and volume of spectahedra

This is a non-linear extension for VolEsti. Spectahedra are feasible regions of semidefinite programs and are known to be convex. They play an important role in optimization since they are the “next more understandable” convex objects after polytopes. Offering algorithms for sampling and volume computation will shed more light towards their study.

The coding project consists in the following steps:

  • Understand the code structure and design of VolEsti. Understand the basics for spectahedra from bibliography.
  • Implement a new convex body type and boundary oracle for spectahedra.
  • Work on extensions of the problem such as replacing spectahedra by a spectahedral shadow.
  • Write tests and documentation.

Project 3. Convex optimization with randomized algorithms

A very related topic to volume approximation via sampling is convex optimization. This project proposes the design and implementation of optimization algorithms (available in relevant bibliography) in VolEsti that utilize sampling (already available in the library) as a main subroutine.

  • Understand the code structure and design of VolEsti.
  • Implement optimization algorithms. A good place to start is www.optimization-online.org/DB_FILE/2008/12/2161.pdf
  • Test implementations with various random walks available in VolEsti
  • Write tests and documentation

Expected impact

A lot of users such as practitioners or researchers from a variety of scientific fields ranging from biogeography to economics need a high level programming or scripting environment to test volume computation or sampling algorithms. With the successful completion of the current proposed projects the library and thus the R-project will benefit from (a) faster and more scalable sampling methods, (b) support for non-linear objects, (c) support for optimization algorithms. The above benefits will enhance the experience of current users but more importantly it will attract new users since we expect that the library will be used to solve problems that cannot be solved today with available software tools.

There are practical and theoretical consequences. From a theoretical point of view we will be able to study the volume of the feasible region of SDP and experiment with theta bodies, thus we will provide a robust for experimentation in convex optimization. From a practical point of view we expect that the library will find use in the computation of equilibria in thermodynamics, in biology for understanding the evolution of coding sequences, in material sciences; these application require robust volume computations of convex bodies.

Students

Students should have a solid background in C++, algorithms and linear algebra. Knowledge of computational geometry, optimization or statistical computing will be a plus.

Mentors

Students, please contact mentors below after completing at least one of the tests below.

  • Vissarion Fisikopoulos <vissarion.fisikopoulos at gmail.com> is an international expert in mathematical software, computational geometry and optimization, and has previous GSOC mentoring experience with Boost C++ libraries (2016-2017) and the R-project (2017).

  • Elias Tsigaridas <elias.tsigaridas at inria.fr> is an international expert in computational nonlinear algebra and geometry with experience in mathematical software. He has contributed to the implementation, in C and C++, of several solving algorithms for various open source computer algebra libraries.

  • Zafeirakis Zafeirakopoulos is an expert in implementing and benchmarking geometric and algebraic algorithms and has previous GSOC experience with the R-project (2017).

Tests

Students, please do one or more of the following tests before contacting the mentors above.

Solutions of tests

Students, please post a link to your test results here.
Apostolos Chalkis

Repouskos Panagiotis

Add a custom footer
Add a custom sidebar
Clone this wiki locally