Two player zero sum continuous games with an SOS solver - GeomScale/gsoc21 GitHub Wiki

Overview

This project aims to expand the usability of the experimental (interior point) optimization solver for SOS (sum of squares) polynomials by providing adequate parsers and a database of reference data for experiments coming from 2-player 0-sum continuous games [B5].

Related work

In GSoC 2020 there was a project that resulted an implementation of the homogeneous interior point algorithm for non-symmetric convex optimization from [B1] and [B2]. This leads to an optimization algorithm over the cone of SOS polynomial [B3].

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.

[B4] https://github.com/bentonatura/volume_approximation/blob/sos/include/sos/README.md

[B5] Parrilo, P. A. (2006, December). Polynomial games and sum of squares optimization. In Proceedings of the 45th IEEE Conference on Decision and Control (pp. 2855-2860). IEEE.

Details of your coding project

The project targets efficient parsers for univariate and multivariate polynomials to be used as an input to the SOS solver. Various, user-friendly, input formats should be considered. In addition, we aim to build a data base of optimization problems for SOS, mainly coming for (2-player) continuous games, that we will use to perform extensive experiments to fine tune the existing implementation.

Expected impact

The projects will provide GeomScale with state-of-the-art SOS solver for SOS programs that will be the software of reference for the problem. A thorough study for problems coming from game theory is also expected.

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

  • 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 mentors 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 and the SOS solver and run some easy experiments.
  • Medium: Modify the solver to use a matrix library other than MKL and Eigen.

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.