SageMath Google Summer of Code 2018 Proposal

Google Summer of Code is an annual global program focused on bringing more student developers into open source software development. It was first held from May to August 2005, and to date more than 600 open source organizations have taken part.

Within the SageMath mathematics software system, I’m looking forward to be a mentor of the project Polynomial optimisation and sums of squares, together with Dr. Dima Pasechnik. This projects touches the area of semidefinite programming (SDP) in Sage. See below the full description for further details.

Skills: algebra, Python, C/C++, Cython, linear/nonlinear optimisation, numerical analysis (MSc/PhD level)

Abstract: Optimisation problems with polynomial constraints are efficiently, in practice, solved by building an increasingly tight sequence of semidefinite programming (SDP) relaxations, one of them known as Lasserre hierarchy.

Description: While Sagemath already has an ability to solve SDPs, more work has to be done in particular to implement moment matrices for polynomials and sums of squares approximations of nonnegative polynomials, and a frontend allowing to define systems of polynomial inequalities using natural syntax, similar to what already can be done with systems of linear inequalities. Another related topic would be to interface to Sagemath more SDP solvers (currently only CVXOPT is available), and possibly prototype an arbitrary precision SDP solver to avoid typical numerical difficulties arising in sums of squares-based SDP relaxations, e.g. implementing a version of the algorithm from Klerk and Vallentin.

See also all the projects of the SageMath organization following this link.