NCTSSOS

NCTSSOS aims to provide a user-friendly and efficient tool for solving optimization problems with non-commutative/trace/state polynomials, which is based on the structured moment-SOHS hierarchy. To use NCTSSOS in Julia, run

pkg> add https://github.com/wangjie212/NCTSSOS

Documentation

Dependencies

• Julia
• JuMP
• Mosek or COSMO
• ChordalGraph

NCTSSOS has been tested on Ubuntu and Windows.

Usage

Unconstrained non-commutative polynomial optimization

Taking $f=1+x_1^4+x_2^4+x_3^4+x_1x_2+x_2x_1+x_2x_3+x_3x_2$ as an example, to compute the first step of the NCTSSOS hierarchy, run

using NCTSSOS
using DynamicPolynomials
@ncpolyvar x[1:3]
f = 1 + x[1]^4 + x[2]^4 + x[3]^4 + x[1]*x[2] + x[2]*x[1] + x[2]*x[3] + x[3]*x[2]
opt,data = nctssos_first(f, x, obj="eigen")

To sovle higher steps of the NCTSSOS hierarchy, repeatedly run

opt,data = nctssos_higher!(data)

Options:
obj: "eigen" by default (perform eigenvalue minimization), "trace" (perform trace minimization)
TS: "block" by default (maximal chordal extension), "MD" (approximately smallest chordal extension), false (invalidating term sparsity iterations)

Constrained non-commutative polynomial optimization

Taking the objective $f=2-x_1^2+x_1x_2^2x_1-x_2^2$ and constraints $g=4-x_1^2-x_2^2\ge0$, $h=x_1x_2+x_2x_1-2=0$ as an example, to solve the first step of the NCTSSOS hierarchy, run

@ncpolyvar x[1:2]
f = 2 - x[1]^2 + x[1]*x[2]^2*x[1] - x[2]^2
ineq = [4 - x[1]^2 - x[2]^2]
eq = [x[1]*x[2] + x[2]*x[1] - 2]
pop = [f; ineq; eq]
d = 2 # set the relaxation order
opt,data = nctssos_first(pop, x, d, numeq=1, obj="eigen")

To solve higher steps of the NCTSSOS hierarchy, repeatedly run

opt,data = nctssos_higher!(data)

Options:
obj: "eigen" by default (perform eigenvalue minimization), "trace" (perform trace minimization)
TS: "block" by default (maximal chordal extension), "MD" (approximately smallest chordal extension), false (invalidating term sparsity iterations)

To exploit correlative sparsity and term sparsity simultaneously, run

opt,data = cs_nctssos_first(pop, x, d, obj="eigen")
opt,data = cs_nctssos_higher!(data)

Trace polynomial optimization

Check out /examples/traceopt.jl.

State polynomial optimization

Check out /examples/stateopt.jl for state polynomial optimization over real numbers and /examples/state_complex.jl for state polynomial optimization over complex numbers.

References

[1] Exploiting Term Sparsity in Noncommutative Polynomial Optimization, 2021.
[2] Sparse polynomial optimization: theory and practice, 2023.
[3] State polynomials: positivity, optimization and nonlinear Bell inequalities, 2023.

Contact

Jie Wang: [email protected]