ClusteredLowRankSolver.jl

A semidefinite programming solver for clustered low-rank SDPs
Author nanleij
Popularity
3 Stars
Updated Last
1 Year Ago
Started In
February 2022

ClusteredLowRankSolver

Dev Coverage

Clustered Low-Rank Semidefinite Programs

A clustered low-rank semidefinite program is a semidefinite program in equality form including free scalar variables, where the constraint matrices corresponding to positive semidefinite variables have a low-rank structure. The program is clustered in the sense that two constraints in different clusters do not use the same positive semidefinite matrix variables. An example where such a clustered low-rank SDP appears is by sampling (low-rank) sums-of-squares constraints. In the interface we focus on this application.

Installation

After installing Julia, run Julia and install the package with e.g.

]add ClusteredLowRankSolver

Press backspace to go back to the REPL from the package environment.

Usage

Use the package with using ClusteredLowRankSolver. See the documentation for instructions on using the interface. Below we show how to model a small polynomial optimization problem.

To use n threads, start Julia with the option -t n. On Windows using multiple threads may lead to crashes or wrong answers when using free variables.

Examples

Consider the problem of finding the minimum of a univariate polynomial p(x) over [-1,1], i.e., the maximal λ such that p(x)-λ >=0. Relaxing the constraint gives p(x)-λ = s_1(x) + (1-x^2) * s_2(x) , i.e., s_1(x) + (1-x^2) * s_2(x) + λ = p where s_i are sum-of-squares polynomials.

using ClusteredLowRankSolver, AbstractAlgebra
using BasesAndSamples # To generate the samples

# Set up the polynomial space and define the polynomial to be optimized:
R, (x,) = PolynomialRing(RealField,["x"])
p = 1-x-x^3+x^6
# The degree of the basis for the sums-of-squares polynomials we want to use:
d = 3

# For the constraint we consider the part for the free variables and the part for the
# positive semidefinite matrix variables separately
free_dict = Dict=> 1)  

# The matrix variables come from the sum-of-squares parts, since s_i(x) is a sum-of-squares
# if and only if s_i(x) = ⟨b(x)b(x)^T, Y⟩ for some Y ⪰ 0 and vector of basis polynomials b(x)
matrix_dict = Dict()
# Both SOS parts have the same total degree, but different weights
matrix_dict[Block(:SOS1)] = LowRankMatPol([R(1)], [[x^k for k=0:d]])
matrix_dict[Block(:SOS2)] = LowRankMatPol([1-x^2], [[x^k for k=0:d-1]])

# Chebyshev points in [-1,1]:
samples = sample_points_chebyshev(2d)
# Create the constraint:
con = Constraint(p, matrix_dict, free_dict, samples)

# we want to maximize λ
obj = Objective(0, Dict(), Dict=> 1))

# Maximize the objective with constraint `con`
sos = LowRankSOSProblem(true, obj, [con])
# Convert the SOS problem to a clustered low-rank SDP
sdp = ClusteredLowRankSDP(sos)
# Solve the sdp with the standard parameters
status, result = solvesdp(sdp)

More examples are available in the documentation. For the code examples described in the documentation and more, see the examples folder.

Citing ClusteredLowRankSolver

If you use ClusteredLowRankSolver.jl in a publication please consider citing

  • D. de Laat and N. Leijenhorst, Solving clustered low-rank semidefinite programs arising from polynomial optimization, Preprint (2022), arXiv:2202.12077

Used By Packages

No packages found.