Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
A converter from polynomial optimization problems of either commuting or noncommuting variables to sparse SDP input formats.
branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
doc Documentation updated
examples Example for sparse chordal graph extension added
ncpol2sdpa
LICENSE First commit
MANIFEST.in Updated to reflect move to Sphinx
README.rst Documentation updated
TODO Unit testing should be done
setup.py Preparing for release 1.6

README.rst

Ncpol2sdpa

Ncpol2sdpa is a tool to convert a polynomial optimization problem of either commutative or noncommutative variables to a sparse semidefinite programming (SDP) problem that can be processed by the SDPA family of solvers, MOSEK, or further processed by PICOS to solve the problem by CVXOPT . The optimization problem can be unconstrained or constrained by equalities and inequalities.

The objective is to be able to solve very large scale optimization problems. Example applications include:

The implementation has an intuitive syntax for entering problems and it scales for a larger number of noncommutative variables using a sparse representation of the SDP problem.

Dependencies

The implementation requires SymPy and Numpy. The code is compatible with both Python 2 and 3, but using version 3 incurs a major decrease in performance.

While the default CPython interpreter is sufficient for small to medium-scale problems, execution time becomes excessive for larger problems. The code is compatible with Pypy. Using it yields a 10-20x speedup. If you use Pypy, you will need the Pypy fork of Numpy.

Optional dependencies include:

  • SciPy allows faster execution with the default CPython interpreter, and enables removal of equations and chordal graph extensions.
  • Chompack improves the sparsity of the chordal graph extension.
  • PICOS is necessary for converting the problem to a PICOS problem.
  • MOSEK Python module is necessary to work with the MOSEK converter.
  • Cvxopt is required by both Chompack and PICOS.

Usage

Documentation is available online. The following code replicates the toy example from Pironio, S.; Navascues, M. & Acin, A. Convergent relaxations of polynomial optimization problems with noncommuting variables SIAM Journal on Optimization, SIAM, 2010, 20, 2157-2180.

from ncpol2sdpa import generate_variables, SdpRelaxation, write_to_sdpa

# Number of Hermitian variables
n_vars = 2
# Level of relaxation
level = 2

# Get Hermitian variables
X = generate_variables(n_vars, hermitian=True)

# Define the objective function
obj = X[0] * X[1] + X[1] * X[0]

# Inequality constraints
inequalities = [-X[1] ** 2 + X[1] + 0.5]

# Simple monomial substitutions
monomial_substitution = {}
monomial_substitution[X[0] ** 2] = X[0]

# Obtain SDP relaxation
sdpRelaxation = SdpRelaxation(X)
sdpRelaxation.get_relaxation(level, objective=obj, inequalities=inequalities,
                             substitutions=monomial_substitution)
write_to_sdpa(sdpRelaxation, 'examplenc.dat-s')

Further instances are in the examples folder and also in the manual.

Installation

The code is available on PyPI, hence it can be installed by

$ sudo pip install ncpol2sdpa

If you want the latest git version, follow the standard procedure for installing Python modules:

$ sudo python setup.py install

Acknowledgment

This work is supported by the European Commission Seventh Framework Programme under Grant Agreement Number FP7-601138 PERICLES, by the Red Espanola de Supercomputacion grants number FI-2013-1-0008 and FI-2013-3-0004, and by the Swedish National Infrastructure for Computing project number SNIC 2014/2-7.

More Information

For more information refer to the following manuscript:

Wittek, P. (2015). Ncpol2sdpa -- Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables. To Appear in ACM Transactions on Mathematical Software.

Something went wrong with that request. Please try again.