SPECTRA - Semidefinite Programming solved Exactly with Computational Tools of Real Algebra

Developed by Simone Naldi. Design, architecture and calibration of the software by Didier Henrion, Simone Naldi and Mohab Safey El Din.

Given rational symmetric matrices A0, A1, .., An of size m, let S denote the set of real points x = (x1, .. ,xn) such that the matrix A(x) = A0 + A1 x1 + .. + An xn is positive semidefinite. The set S is a convex semialgebraic set called a spectrahedron, it is described by a Linear Matrix Inequality, an LMI. The above figure represents a specific spectrahedron S for n=3 and m=5. The boundary of S is in red. The determinant of A(x) vanishes on this red surface, but also on the blue surface.

SPECTRA is a Maple library which aims at finding at least one point in S, using exact arithmetic.

SPECTRA should be used when the number n of variables or the size m of the LMI are small. It should not be considered as a competitor to numerical algorithms such as interior-point methods for semidefinite programming (SDP).

Contrary to numerical algorithms which are based on approximate computations and floating point arithmetic, SPECTRA is exclusively based on computations with exact arithmetic, and hence it should be primarily used either in potentially degenerate situations, for example when it is expected that S has empty interior, or when a rigorous certificate of infeasibility or feasibility is required.


Download

SPECTRA 1.0 (5 November 2016) is freely available as a Maple library. It can be downloaded in the form of a single binary file called SPECTRA.mla

SPECTRA relies on FGb, a library for fast computation of Groebner bases, whose Maple interface must be installed.


Documentation

A light documentation of SPECTRA including simple examples is available here:

  • D. Henrion, S. Naldi, M. Safey El Din. SPECTRA - a Maple library for solving linear matrix inequalities in exact arithmetic. arXiv:1611.01947 version 1, Nov. 2016.

    A more detailed documentation introducing the theoretical background and including more sophisticated examples is available here:

  • D. Henrion, S. Naldi, M. Safey El Din. SPECTRA - a Maple library for solving linear matrix inequalities in exact arithmetic. To appear in Optimization Methods and Software, 2017.

    SPECTRA is based on the mathematical theory and the computer algebra algorithm described comprehensively in the following documents:

  • D. Henrion, S. Naldi, M. Safey El Din. Exact algorithms for linear matrix inequalities. SIAM Journal on Optimization, Vol. 26, No. 4, pp. 2512-2539, 2016.

  • S. Naldi. Exact algorithms for determinantal varieties and semidefinite programming. PhD thesis, Univ. Toulouse and Univ. Pierre et Marie Curie Paris. Oct. 2015.


    Please forward comments, suggestions and bug reports to Didier Henrion, Simone Naldi and Mohab Safey El Din.