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="block", solution=true) # compute the first TS step of the TSSOS hierarchy
opt,sol,data = tssos_higher!(data, TS="block", solution=true) # 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
GroebnerBasis	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
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: cosmo_para(eps_abs, eps_rel, max_iter, time_limit)	cosmo_para(1e-5, 1e-5, 1e4, 0)
mosek_setting	Parameters for the Mosek solver: mosek_para(tol_pfeas, tol_dfeas, tol_relgap, time_limit, num_threads)	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
rtol	tolerance for rank	1e-2
gtol	tolerance for global optimality gap	1e-2
ftol	tolerance for feasibility	1e-3

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", solution=true) # compute the first TS step of the CS-TSSOS hierarchy
opt,sol,data = cs_tssos_higher!(data, TS="MD", solution=true) # 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"
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: cosmo_para(eps_abs, eps_rel, max_iter, time_limit)	cosmo_para(1e-5, 1e-5, 1e4, 0)
mosek_setting	Parameters for the Mosek solver: mosek_para(tol_pfeas, tol_dfeas, tol_relgap, time_limit, num_threads)	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 an optimal solution	false
rtol	tolerance for rank	1e-2
gtol	tolerance for global optimality gap	1e-2
ftol	tolerance for feasibility	1e-3

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(pop, x, d; nb=0, numeq=0, GroebnerBasis=true, basis=[], reducebasis=false, TS="block", 
merge=false, md=3, solver="Mosek", QUIET=false, solve=true, MomentOne=false, Gram=false, solution=false, 
cosmo_setting=cosmo_para(), mosek_setting=mosek_para(), normality=false, rtol=1e-2, gtol=1e-2, ftol=1e-3)

Compute the first TS step of the TSSOS hierarchy for constrained polynomial optimization. If reducebasis=true, then remove monomials from the monomial basis by diagonal inconsistency. If GroebnerBasis=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)
rtol: tolerance for rank
gtol: tolerance for global optimality gap
ftol: tolerance for feasibility

Output arguments

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

source

opt,sol,data = tssos_first(f, x; newton=true, reducebasis=false, TS="block", merge=false, md=3, feasibility=false, solver="Mosek", QUIET=false, solve=true, 
dualize=false, MomentOne=false, Gram=false, solution=false, cosmo_setting=cosmo_para(), mosek_setting=mosek_para(), rtol=1e-2, gtol=1e-2, ftol=1e-3)

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 feasibility=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
TS: type of term sparsity ("block", "signsymmetry", "MD", "MF", false)
md: tunable parameter for merging blocks
QUIET: run in the quiet mode (true, false)
rtol: tolerance for rank
gtol: tolerance for global optimality gap
ftol: tolerance for feasibility

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, feasibility=false, dualize=false, Gram=false,
MomentOne=false, solution=false, cosmo_setting=cosmo_para(), mosek_setting=mosek_para(), normality=false)

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=[], basis=[], ebasis=[], TS="block", merge=false, md=3, solver="Mosek", 
dualize=false, QUIET=false, solve=true, solution=false, Gram=false, MomentOne=false, cosmo_setting=cosmo_para(), mosek_setting=mosek_para(), 
rtol=1e-2, gtol=1e-2, ftol=1e-3)

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 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
QUIET: run in the quiet mode (true, false)
rtol: tolerance for rank
gtol: tolerance for global optimality gap
ftol: tolerance for feasibility

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=[], basis=[], ebasis=[], TS="block", 
merge=false, md=3, QUIET=false, solver="Mosek", dualize=false, solve=true, solution=false, Gram=false, MomentOne=false, 
cosmo_setting=cosmo_para(), mosek_setting=mosek_para(), rtol=1e-2, gtol=1e-2, ftol=1e-3)

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

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, dualize=false, 
MomentOne=false, cosmo_setting=cosmo_para(), mosek_setting=mosek_para())

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-2)

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(moment, d; pop=nothing, x=nothing, lb=nothing, numeq=0, nb=0, rtol=1e-2, gtol=1e-2, ftol=1e-3)

Extract a tuple of solutions from the moment matrix using Henrion-Lasserre's algorithm.

Input arguments

moment: moment matrix
d: relaxation order
pop: polynomial optimization problem
x: set of variables
lb: SDP lower bound
numeq: number of equality constraints
nb: number of binary variables
rtol: tolerance for rank
gtol: tolerance for global optimality gap
ftol: tolerance for feasibility

Output arguments

sol: a tuple of solutions

source

TSSOS.extract_solutions_robust — Function

sol = extract_solutions_robust(moment, n, d; pop=nothing, x=nothing, lb=nothing, numeq=0, nb=0, rtol=1e-2, gtol=1e-2, ftol=1e-3)

Extract a tuple of solutions from the moment matrix using the GNS robust algorithm.

Input arguments

moment: moment matrix
n: number of variables
d: relaxation order
pop: polynomial optimization problem
x: set of variables
lb: SDP lower bound
numeq: number of equality constraints
nb: number of binary variables
rtol: tolerance for rank
gtol: tolerance for global optimality gap
ftol: tolerance for feasibility

Output arguments

sol: a tuple of solutions
w: weight vector

source