Polynomial Optimization

Polynomial optimization concerns minimizing a polynomial subject to a tuple of polynomial inequality constraints and equality constraints, which in general takes the form:

\[\mathrm{inf}_{\mathbf{x}\in\mathbb{R}^n}\ f(\mathbf{x})\ \text{ s.t. }\ g_1(\mathbf{x})\ge0,\ldots,g_m(\mathbf{x})\ge0,h_1(\mathbf{x})=0,\ldots,h_{\ell}(\mathbf{x})=0,\]

where $f,g_1,\ldots,g_m,h_1,\ldots,h_{\ell}\in\mathbb{R}[\mathbf{x}]$ are polynomials in variables $\mathbf{x}$.

To illustrate how to solve a polynomial optimization problem with TSSOS, let us consider $f=1+x_1^4+x_2^4+x_3^4+x_1x_2x_3+x_2$ and $g=1-x_1^2-2x_2^2, h=x_2^2+x_3^2-1$.

@polyvar x[1:3]
f = 1 + x[1]^4 + x[2]^4 + x[3]^4 + x[1]*x[2]*x[3] + x[2]
g = 1 - x[1]^2 - 2*x[2]^2
h = x[2]^2 + x[3]^2 - 1
pop = [f, g, h]
d = 2 # set the relaxation order
opt,sol,data = tssos_first(pop, x, d, numeq=1, TS="MD") # compute the first TS step of the TSSOS hierarchy
opt,sol,data = tssos_higher!(data, TS="MD") # compute higher TS steps of the TSSOS hierarchy

Keyword arguments

Argument	Description	Default value
nb	Specify the first nb variables to be $\pm1$ binary variables	0
numeq	Specify the last numeq constraints to be equality constraints	0
quotient	Work in the quotient ring by computing a Gröbner basis	true
basis	Use customized monomial bases	[]
reducebasis	Reduce the monomial bases	false
TS	Types of chordal extensions used in term sparsity iterations: "block"(maximal chordal extension), "signsymmetry" (sign symmetries), "MD" (approximately smallest chordal extension), false (invalidating term sparsity exploitation)	"block"
normality	Impose normality condtions	false
NormalSparse	Exploit sparsity when imposing normality conditions	false
merge	Merge overlapping PSD blocks	false
md	Parameter for tunning the merging strength	3
MomentOne	add a first-order moment PSD constraint	false
solver	Specify an SDP solver: "Mosek" or "COSMO"	"Mosek"
cosmo_setting	Parameters for the COSMO solver: cosmopara(epsabs, epsrel, maxiter, time_limit)	cosmo_para(1e-5, 1e-5, 1e4, 0)
mosek_setting	Parameters for the Mosek solver: cosmopara(tolpfeas, toldfeas, tolrelgap, timelimit, numthreads)	mosek_para(1e-8, 1e-8, 1e-8, -1, 0)
QUIET	Silence the output	false
solve	Solve the SDP relaxation	true
dualize	Solve the dual SDP problem	false
Gram	Output Gram matrices	false
solution	Extract optimal solutions	false
tol	Tolerance for certifying global optimality	1e-4

Correlative sparsity

The following is an example where one exploits correlative sparsity and term sparsity simultaneously.

using DynamicPolynomials
n = 6
@polyvar x[1:n]
f = 1 + sum(x.^4) + x[1]*x[2]*x[3] + x[3]*x[4]*x[5] + x[3]*x[4]*x[6]+x[3]*x[5]*x[6] + x[4]*x[5]*x[6]
pop = [f, 1-sum(x[1:3].^2), 1-sum(x[3:6].^2)]
order = 2 # set the relaxation order
opt,sol,data = cs_tssos_first(pop, x, order, numeq=0, TS="MD") # compute the first TS step of the CS-TSSOS hierarchy
opt,sol,data = cs_tssos_higher!(data, TS="MD") # compute higher TS steps of the CS-TSSOS hierarchy

Keyword arguments

Argument	Description	Default value
nb	Specify the first nb variables to be $\pm1$ binary variables	0
numeq	Specify the last numeq constraints to be equality constraints	0
CS	Types of chordal extensions in exploiting correlative sparsity: "MF" (approximately smallest chordal extension), "NC" (not performing chordal extension), false (invalidating correlative sparsity exploitation)	"MF"
basis	Use customized monomial bases	[]
hbasis	Use customized monomial bases associated with equality constraints	[]
cliques	Use customized variable cliques	[]
TS	Types of chordal extensions used in term sparsity iterations: "block"(maximal chordal extension), "signsymmetry" (sign symmetries), "MD" (approximately smallest chordal extension), false (invalidating term sparsity iterations)	"block"
normality	Impose normality condtions	false
NormalSparse	Exploit sparsity when imposing normality conditions	false
merge	Merge overlapping PSD blocks	false
md	Parameter for tunning the merging strength	3
MomentOne	add a first-order moment PSD constraint for each variable clique	false
solver	Specify an SDP solver: "Mosek" or "COSMO"	"Mosek"
cosmo_setting	Parameters for the COSMO solver: cosmopara(epsabs, epsrel, maxiter, time_limit)	cosmo_para(1e-5, 1e-5, 1e4, 0)
mosek_setting	Parameters for the Mosek solver: cosmopara(tolpfeas, toldfeas, tolrelgap, timelimit, numthreads)	mosek_para(1e-8, 1e-8, 1e-8, -1, 0)
QUIET	Silence the output	false
solve	Solve the SDP relaxation	true
dualize	Solve the dual SDP problem	false
Gram	Output Gram matrices	false
Mommat	Output moment matrices	false
solution	Extract an approximately optimal solution	false
tol	Tolerance for certifying global optimality	1e-4

Compute a locally optimal solution

Moment-SOS relaxations provide lower bounds on the optimum of the polynomial optimization problem. As the complementary side, one could compute a locally optimal solution which provides an upper bound on the optimum of the polynomial optimization problem. The upper bound is useful in evaluating the quality (tightness) of those lower bounds provided by moment-SOS relaxations. In TSSOS, for a given polynomial optimization problem, a locally optimal solution could be obtained via the nonlinear programming solver Ipopt:

obj,sol,status = local_solution(data.n, data.m, data.supp, data.coe, numeq=data.numeq, startpoint=rand(data.n))

Methods

TSSOS.tssos_first — Function

opt,sol,data = tssos_first(f, x; nb=0, newton=true, reducebasis=false, TS="block", merge=false,
md=3, feasible=false, solver="Mosek", QUIET=false, solve=true, MomentOne=false, Gram=false, solution=false, tol=1e-4)

Compute the first TS step of the TSSOS hierarchy for unconstrained polynomial optimization. If newton=true, then compute a monomial basis by the Newton polytope method. If reducebasis=true, then remove monomials from the monomial basis by diagonal inconsistency. If TS="block", use maximal chordal extensions; if TS="MD", use approximately smallest chordal extensions. If merge=true, perform the PSD block merging. If feasible=true, then solve the feasibility problem. If solve=false, then do not solve the SDP. If Gram=true, then output the Gram matrix. If MomentOne=true, add an extra first-order moment PSD constraint to the moment relaxation.

Input arguments

f: objective
x: POP variables
nb: number of binary variables in x
TS: type of term sparsity ("block", "signsymmetry", "MD", "MF", false)
md: tunable parameter for merging blocks
QUIET: run in the quiet mode (true, false)
tol: relative tolerance to certify global optimality

Output arguments

opt: optimum
sol: (near) optimal solution (if solution=true)
data: other auxiliary data

source

opt,sol,data = tssos_first(pop, x, d; nb=0, numeq=0, quotient=true, basis=[],
reducebasis=false, TS="block", merge=false, md=3, solver="Mosek", QUIET=false, solve=true,
MomentOne=false, Gram=false, solution=false, tol=1e-4)

Compute the first TS step of the TSSOS hierarchy for constrained polynomial optimization. If quotient=true, then exploit the quotient ring structure defined by the equality constraints. If merge=true, perform the PSD block merging. If solve=false, then do not solve the SDP. If Gram=true, then output the Gram matrix. If MomentOne=true, add an extra first-order moment PSD constraint to the moment relaxation.

Input arguments

pop: vector of the objective, inequality constraints, and equality constraints
x: POP variables
d: relaxation order
nb: number of binary variables in x
numeq: number of equality constraints
TS: type of term sparsity ("block", "signsymmetry", "MD", "MF", false)
md: tunable parameter for merging blocks
normality: impose the normality condtions (true, false)
QUIET: run in the quiet mode (true, false)
tol: relative tolerance to certify global optimality

Output arguments

opt: optimum
sol: (near) optimal solution (if solution=true)
data: other auxiliary data

source

TSSOS.tssos_higher! — Function

opt,sol,data = tssos_higher!(data; TS="block", merge=false, md=3, QUIET=false, solve=true,
MomentOne=false, solution=false, tol=1e-4)

Compute higher TS steps of the TSSOS hierarchy.

source

TSSOS.cs_tssos_first — Function

opt,sol,data = cs_tssos_first(pop, x, d; nb=0, numeq=0, CS="MF", cliques=[], TS="block", merge=false, md=3, solver="Mosek", QUIET=false, solve=true, solution=false,
Gram=false, MomentOne=false, Mommat=false, tol=1e-4)

Compute the first TS step of the CS-TSSOS hierarchy for constrained polynomial optimization. If merge=true, perform the PSD block merging. If solve=false, then do not solve the SDP. If Gram=true, then output the Gram matrix. If Mommat=true, then output the moment matrix. If MomentOne=true, add an extra first-order moment PSD constraint to the moment relaxation.

Input arguments

pop: vector of the objective, inequality constraints, and equality constraints
x: POP variables
d: relaxation order
nb: number of binary variables in x
numeq: number of equality constraints
CS: method of chordal extension for correlative sparsity ("MF", "MD", "NC", false)
cliques: the set of cliques used in correlative sparsity
TS: type of term sparsity ("block", "signsymmetry", "MD", "MF", false)
md: tunable parameter for merging blocks
normality: impose the normality condtions (true, false)
QUIET: run in the quiet mode (true, false)
tol: relative tolerance to certify global optimality

Output arguments

opt: optimum
sol: (near) optimal solution (if solution=true)
data: other auxiliary data

source

opt,sol,data = cs_tssos_first(supp::Vector{Vector{Vector{UInt16}}}, coe, n, d; nb=0, numeq=0, CS="MF", cliques=[], TS="block", 
merge=false, md=3, QUIET=false, solver="Mosek", solve=true, solution=false, Gram=false, MomentOne=false, Mommat=false, tol=1e-4)

Compute the first TS step of the CS-TSSOS hierarchy for constrained polynomial optimization. Here the polynomial optimization problem is defined by supp and coe, corresponding to the supports and coeffients of pop respectively.

source

opt,sol,data = cs_tssos_first(pop, z, n, d; nb=0, numeq=0, CS="MF", cliques=[], TS="block", ipart=true, merge=false, md=3, 
solver="Mosek", QUIET=false, solve=true, Gram=false, Mommat=false, MomentOne=false)

Compute the first TS step of the CS-TSSOS hierarchy for constrained complex polynomial optimization. If merge=true, perform the PSD block merging. If ipart=false, then use the real moment-HSOS hierarchy. If solve=false, then do not solve the SDP. If Gram=true, then output the Gram matrix. If Mommat=true, then output the moment matrix. If MomentOne=true, add an extra first-order moment PSD constraint to the moment relaxation.

Input arguments

pop: vector of the objective, inequality constraints, and equality constraints
z: CPOP variables and their conjugate
n: number of CPOP variables
d: relaxation order
nb: number of unit-norm variables in x
numeq: number of equality constraints
CS: method of chordal extension for correlative sparsity ("MF", "MD", false)
cliques: the set of cliques used in correlative sparsity
TS: type of term sparsity ("block", "MD", "MF", false)
md: tunable parameter for merging blocks
normality: normal order
QUIET: run in the quiet mode (true, false)

Output arguments

opt: optimum
sol: (near) optimal solution (if solution=true)
data: other auxiliary data

source

opt,sol,data = cs_tssos_first(supp::Vector{Vector{Vector{Vector{UInt16}}}}, coe::Vector{Vector{ComplexF64}},
n, d; nb=0, numeq=0, CS="MF", cliques=[], TS="block", ipart=true, merge=false, md=3, solver="Mosek",
QUIET=false, solve=true, Gram=false, Mommat=false, MomentOne=false)

Compute the first TS step of the CS-TSSOS hierarchy for constrained complex polynomial optimization. Here the complex polynomial optimization problem is defined by supp and coe, corresponding to the supports and coeffients of pop respectively.

source

TSSOS.cs_tssos_higher! — Function

opt,sol,data = cs_tssos_higher!(data; TS="block", merge=false, md=3, QUIET=false, solve=true,
solution=false, Gram=false, Mommat=false, MomentOne=false)

Compute higher TS steps of the CS-TSSOS hierarchy.

source

opt,sol,data = cs_tssos_higher!(data; TS="block", merge=false, md=3, QUIET=false, solve=true,
solution=false, Gram=false, Mommat=false, MomentOne=false)

Compute higher TS steps of the CS-TSSOS hierarchy.

source

TSSOS.local_solution — Function

obj,sol,status = local_solution(n, m, supp::Vector{Union{Vector{Vector{UInt16}}, Array{UInt8, 2}}}, coe; nb=0, numeq=0,
startpoint=[], QUIET=false)

Compute a local solution by a local solver.

Input arguments

n: number of POP variables
m: number of POP constraints
supp: supports of the POP
coe: coefficients of the POP
nb: number of binary variables
numeq: number of equality constraints
startpoint: provide a start point
QUIET: run in the quiet mode or not (true, false)

Output arguments

obj: local optimum
sol: local solution
status: solver termination status

source

TSSOS.refine_sol — Function

ref_sol,flag = refine_sol(opt, sol, data, QUIET=false, tol=1e-4)

Refine the obtained solution by a local solver. Return the refined solution, and flag=0 if global optimality is certified, flag=1 otherwise.

source

TSSOS.extract_solutions — Function

sol = extract_solutions(pop, x, d, opt, moment; numeq=0, nb=0, tol=1e-4)

Extract a set of solutions for the polynomial optimization problem.

Input arguments

pop: polynomial optimization problem
x: set of variables
d: relaxation order
opt: optimum
moment: moment matrix
numeq: number of equality constraints
nb: number of binary variables
tol: tolerance to obtain the column echelon form

Output arguments

sol: a set of solutions

source

TSSOS.extract_solutions_robust — Function

sol = extract_solutions_robust(n, d, moment; tol=1e-2)

Extract a set of solutions for the polynomial optimization problem.

Input arguments

n: number of variables
d: relaxation order
moment: moment matrix
tol: tolerance to obtain the column echelon form

Output arguments

sol: a set of solutions

source