SymDPoly: Home

alt text

Current version: 0.7.6 for Scala 2.12.8.

SymDPoly solves polynomial optimization problems using symmetry-adapted semidefinite relaxations. The problems can involve either commutative or noncommutative variables, though SymDPoly is optimized for the latter. SymDPoly does not require a particular structure in the problem, as it works by brute combinatorial enumeration of equivalences. However, its processing routines are highly optimized and able to reduce around 100k monomials/second.

How to try SymDPoly

The easiest way is to install the Ammonite REPL, and then run one of the example scripts, for example examples/CHSH.sc from the command line using amm CHSH.sc.

See the Installation guide for additional instructions, including usage of Ammonite on Windows.

A simple example

An evaluation of the Tsirelson’s bound for the CHSH inequality can be done in a few lines of code. See the full explanation. Create a text file name CHSH.sc, and copy/paste first the following lines to define an Ammonite script.

interp.repositories() :+= coursier.MavenRepository("https://dl.bintray.com/denisrosset/maven")
@
import $ivy.`net.alasc::symdpoly-core:0.7.6`

Then, we define the free algebra for four operators A(0), A(1), B(0) and B(1), corresponding to measurements with outcomes +1 and -1. We import the operator families A and B in global scope.

import net.alasc.symdpoly._; 
import defaults._

object Free extends free.MonoDef(cyclotomicOrder = 2) { // allows signed monomials
  case class A(x: Int) extends HermitianOp
  object A extends HermitianOpFamily1(0 to 1)
  case class B(y: Int) extends HermitianOp
  object B extends HermitianOpFamily1(0 to 1)
  val families = Seq(A, B)
}

import Free.{A, B}

val Quotient = Free.quotientMonoid(quotient.pairs {
  case (A(x1), A(x2)) if x1 == x2 => Free.one
  case (B(y1), B(y2)) if y1 == y2 => Free.one
  case (B(y), A(x))               => A(x) * B(y)
})

val chsh = Quotient.quotient(A(0) * B(0) + A(0) * B(1) + A(1) * B(0) - A(1) * B(1))

val generatingSet = Quotient.quotient(GSet.onePlus(A, B))

val L = Quotient.eigenvalueEvaluator(real = true)

val (problem, symmetryGroup) = L(chsh).maximize.symmetrize()
val relaxation = problem.relaxation(generatingSet)

We then solve:

scala> println(relaxation.program.sdpa.solve())
OptimumFound(Some(2.8284270918417818),2.8284272228485476)

Work in progress

SymDPoly is a work-in-progress. We have support in the code for the following features, but they are not tested.

Equality constraints.
Operator semidefinite constraints.
Scalar inequality constraints.
Problems with complex SDP relaxations.

Why SymDPoly?

SymDPoly differs from existing semidefinite relaxation frameworks in a number of ways.

It supports both noncommutative and commutative variables.
It supports equality constraints through monomial rewriting, which leads to efficient formulations.
It discovers symmetries of the problem and creates symmetry-adapted relaxations.
It interfaces with a wide range of solvers.
It processes problems in exact arithmetic.
It is extremely fast.

Other libraries working on the same problem space include:

ncpol2sdpa, a package for Python (noncommutative/commutative).
NCSOSTools, a toolbox for MATLAB (noncommutative).
GloptiPoly, a package for MATLAB (commutative).
SparsePOP, a toolbox for MATLAB (commutative).
SOSTOOLS, a toolbox for MATLAB (commutative).

When using SymSDPoly as a library.

The current version is 0.7.6 for Scala 2.12.8.

It requires the following additions to the build.sbt file.

resolvers += Resolver.bintrayRepo("denisrosset", "maven")

libraryDependencies += "net.alasc" %% "symdpoly-core"    % "0.7.6"

You may want to add the symdpoly-mosek module for advanced Mosek integration, if you have access to the Mosek binaries.

When integrating SymDPoly with other Scala libraries, note that it is based on the Spire library spire version 0.16.0, which in turn depends on cats-kernel.

Documentation and Support

Chat it up on Gitter.
Check the tutorial.
Check the Scaladoc.

Contributors

SymDPoly and the group theory/linear algebra libraries it depends on were written by Denis Rosset. For the implementation of the cyclotomic number field, we acknowledge contributions from the GAP system project.

Feedback and suggestions are always welcome. We ask participants to follow the guidelines of the Typelevel Code of Conduct. Note that SymDPoly is not a Typelevel project, but some of its components, e.g. Spire are.

Symmetry-adapted moment relaxations for noncommutative polynomial optimization