Optimization and SOS - GeomScale/gsoc20 GitHub Wiki

Overview

The projects targets in optimization over the Sum-Of-Squares (SOS). A classical approach it to represent your problem as an semidefinite program (SDP) and solve the latter using a state-of-the-art solver. However, this approach increases a lot the number of variables, hence it is better to optimize directly in the SOS cone.

Related work

The main goal is to implement the homogeneous interior point algorithm for non-symmetric convex optimization from [B1] and [B2]. Then we will use this tool to implement an optimization algorithm over the cone of SOS polynomial [B3]. There exists an implementation of both algorithms in Matlab here. We will also provide a comparison against existing tools for SOS optimization and writing a positive polynomial as an SOS.

References:

[B1] A. Skajaa and Y. Ye, A homogeneous interior-point algorithm for nonsymmetric convex conic optimization, Mathematical Programming Ser. A, 150 (2015), pp. 391-422.

[B2] D. Papp and S. Yıldız. On “A homogeneous interior-point algorithm for nonsymmetric convex conic optimization”. https://arxiv.org/abs/1712.00492

[B3] Papp, D; Yildiz, S: Sum-of-squares optimization without semidefinite programming. SIAM Journal on Optimization 29(1), 2019, pp. 822-851.

Details of your coding project

The project concerns the implementation of an interior point algorithm over the cone of SOS polynomials and experiments against existing software. The code will be in C++ with R interfaces using Rcpp, following volesti structure. Basic documentation for the R version is required.

Expected impact

The projects opts to deliver the best and fastest software for computing/optimizing with sum-of-squares polynomials.

Mentors

  • 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).

  • Fabrice Rouillier <fabrice.rouillier at inria.fr> is an expert in computational algebra, geometry, and mathematical software. He has contributed to the implementation of several state-of-the-art software tools for computing with intervals and polynomials.

  • Elias Tsigaridas <elias.tsigaridas at inria.fr> is an 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 and has previous GSOC mentoring experience with the R-project (2019).

Students, please contact the first and the third mentor after completing at least one of the tests below.

Tests

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

  • Easy: compile and run VolEsti. Use the R extension to visualize sampling in a polytope.
  • Medium: Extent the hit-and-run algorithm to sample from the boundary of the spectrahedron (feasible region of an SDP).
  • Medium: Implement an algorithm based on SDP for writing a positive multivariate polynomial as SOS.
  • Hard: Implement an interior point algorithm for linear programming.

Solutions of tests

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

  • EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.