Techniques

Homogenization

Christoffel-Darboux Kernels

Here is the list of functions implemented in TSSOS that are based on computing Christoffel-Darboux kernels associated to a given POP:

TSSOS.run_H1 — Function

Performs iterative bound strengthening (i.e, implements H1) for a given POP.

Arguments

x::Vector: Initial vector of decision variables.
n::Int: Dimension or size of the problem.
d::Int: Degree of the relaxation.
dc::Int: Degree of the Christoffel polynomials relaxation. dc must be smaller than or equal to d.
N::Int: Maximum number of iterations to perform.
eps::Float64: Perturbation factor deciding the volume of CDK sublevel sets.
gap_tol::Float64 (optional): Threshold for optimality gap tolerance. Default is 0.5.
beta::Float64 (optional): Threshold beta controlling the strength of the Tikhonov regularization of CDK. Default is 0.001.

Returns

A list with the following elements:

OPT: Relaxation bound from each iteration.
gap_history: A history of the optimality gaps at each iteration.
Moment_matrices: Moment matrices computed during each iterations used to construct CDK sublevel constraints.
K: Parameter to keep track of the rank of the moment matrices for each iteration.
Certain_overrestriction: A measure or flag for over-restriction (when H1 is sure that further feasible set reductions would yield an invalid bound).
ubRef: Upper bounds with respect to which the optimality gap is measured.

source

Missing docstring.

Missing docstring for run_H1CS. Check Documenter's build log for details.

TSSOS.run_H2 — Function

Applies H2 algorithm to a given POP instance

Arguments

pop::Vector: Vector defining the problem, the first element being the objective function, the others being constraints.
x::Vector: Initial vector of decision variables
d::Int: - Degree of the relaxation
dc::Int: - Degree of the marginal Christoffel polynomials (has to be smaller than or equal to d - order of the moment matrix)
local_sol::Vector: Available solution (here obtained from an external local optimizer IPOPT).
tau::Float64: Filtering parameter
beta::Float64 (optional): Threshold beta controling the strength of the Tikhonov regularization of marginal Christoffel polynomials. Default is 0.001.

Returns

A tuple of the following:

[opt, optcdk]: A pair containing the optimal solutions of moment relaxation before and after CDK strengthening via H2.
[initial_gap, gapcdk]: Relative optimality gaps before and after CDK strengthening via H2.
Gammas: Thresholds used to construct sublevel sets of marginal Christoffel polynomials (CDK).
[ubRef, f(solcdk)]: The available upper bound before and after CDK strengthening via H2.
data.moment[1]: The moment matrix from which marginal CDK polynomials were constructed

source

TSSOS.run_H2CS — Function

Applies H2CS algorithm to a given POP instance

Arguments

pop::Vector: Vector defining the problem, the first element being the objective function, the others being constraints.
x::Vector: Initial vector of decision variables
d::Int: - Degree of the relaxation
dc::Int: - Degree of the marginal Christoffel polynomials (has to be smaller than or equal to d - order of the moment matrix)
local_sol::Vector: Available solution (here obtained from an external local optimizer IPOPT).
tau::Float64: Filtering parameter
beta::Float64 (optional): Threshold beta controling the strength of the Tikhonov regularization of marginal Christoffel polynomials. Default is 0.001.

Returns

A tuple of the following:

[opt, optcdk]: A pair containing the optimal solutions of the sparse moment relaxation before and after CDK strengthening via H2CS.
[initial_gap, gapcdk]: Relative optimality gaps before and after CDK strengthening via H2CS.
Gammas: Thresholds used to construct sublevel sets of marginal Christoffel polynomials (CDK).
[ubRef, f(solcdk)]: The available upper bound before and after CDK strengthening via H2CS.
data.moment[1]: The moment matrix from which marginal CDK polynomials were constructed.

source

TSSOS.construct_CDK — Function

Constructs Christoffel polynomial of order d (CDK) using Singular Value Decomposition (SVD) for the input moment matrix `Mm` of order smaller or equal than d.

Arguments

vars: vector of variables, e.g., @polyvar x[1:5]
dc: degree of the CDK (has to be smaller than or equal to the order of the moment matrix)
Mm::Matrix: The input moment matrix from which which the CDK is constructed.
threshold::Float64 (optional): A threshold value for filtering eigenvalues (i.e., deciding the numerical rank of Mm) . Default is 0.001.

Returns

p_alpha_squared[1:negativeEV]: Polynomials in the kernel of the moment matrix.
cdk: The constructed CDK (positive part of the moment matrix).
positiveEV: The number of positive eigenvalues of the moment matrix.
minimum(Qval): The minimum eigenvalue of the moment matrix.
negativeEV: The number of negative eigenvalues of the moment matrix.

source

TSSOS.construct_marginal_CDK — Function

Constructs marginal Christoffel polynomials (CDK) using Singular Value Decomposition (SVD) for the input matrix `Mm`.

Arguments

vars: vector of variables, e.g., @polyvar x[1:5].
k::vector - Index of the decision variable for which CDK needs to be constructed.
dc::Int: - Degree of the marginal Christoffel polynomials (has to be smaller than or equal to d - order of the moment matrix).
Mm::Matrix: The input moment matrix from which the marginal CDK is constructed.
threshold::Float64 (optional): A threshold value for filtering eigenvalue (i.e., deciding the numerical rank of Mm) . Default is 0.001.

Returns

cdk: The constructed marginal CDK.
p_alpha_squared[1:negativeEV]: Polynomials in the kernel of the marginal moment matrix.
positiveEV: The set of positive eigenvalues of the marginal moment matrix.
negativeEV: The set of negative eigenvalues of the marginal moment matrix.
minimum(Qval): The minimum eigenvalue of the marginal moment matrix.

source

TSSOS.construct_CDK_cs — Function

construct_CDK_cs(x, dc, Mm, cliques, threshold=0.001) -> Tuple
Construct the `Cdk`, kernel, and eigenvalue-related statistics for a given set of cliques and moment matrices.

Arguments

x::Vector: A vector of polynomial variables.
dc::Int: The degree of the Christoffel polynomial constraints. It must be <= than the order of relaxation d.
Mm::Vector: A vector of moment matrices, one for each clique.
cliques::Vector{Vector{Int}}: A list of cliques, where each clique is a vector of indices corresponding to variables in x.
threshold::Float64 (optional): A small positive value used to distinguish between eigenvalues considered positive and negative. Defaults to 0.001.

Returns

Tuple: A tuple containing:
Kernel::Vector: A vector of squared orthonormal polynomial values corresponding to the polynomials in the kernel of clique-based moment matrices.
Cdk::Vector: A vector of Christoffel poolynomials of degree 2*dc, one for each clique.
posEV::Vector: A vector of counts of eigenvalues above the threshold for each clique.
minEV::Vector: A vector of the smallest eigenvalue for each clique.
negEV::Vector: A vector of counts of eigenvalues below or equal to the threshold for each clique.

source

TSSOS.construct_marginal_CDK_cs — Function

construct_marginal_CDK_cs(vars, k, dc, Mm, cliques; threshold=0.001) -> Tuple

Constructs the marginal Christoffel polynomials (CDK) for a given variable x_k using eigenvalue decomposition, using clique-based moment matrices.

Arguments

vars::Vector: A vector of polynomial variables (e.g., created with @polyvar x[1:n]).
k::Int: The global index of the variable x_k for which the marginal CDK is to be constructed.
dc::Int: The degree of the marginal Christoffel polynomials. Must be less than or equal to the order of the associated moment matrix.
Mm::Vector{Matrix}: A vector of moment matrices, where each matrix corresponds to a clique.
cliques::Vector{Vector{Int}}: A list of cliques, where each clique is a subset of the indices of vars.
threshold::Float64 (optional): A threshold for filtering eigenvalues, used to determine the numerical rank of the moment matrix. Default is 0.001.

Returns

A tuple containing:

p_alpha_squared[1:negativeEV]::Vector: Polynomials in the kernel of the marginal moment matrix.
cdk::Float64: The constructed marginal Christoffel polynomial.
positiveEV::Int: The count of positive eigenvalues of the marginal moment matrix.
negativeEV::Int: The count of negative eigenvalues of the marginal moment matrix.
minimum(Qval)::Float64: The smallest eigenvalue of the marginal moment matrix.

source

We provide below some illustrations. Let us consider the following POP (Example 3.2 from [Sparse polynomial optimization: theory and practice]):

n = 6
@polyvar x[1:n]
f = x[2]*x[5] + x[3]*x[6] - x[2]*x[3] - x[5]*x[6] + x[1]*(-x[1] + x[2] + x[3] - x[4] + x[5] + x[6])
g = [(6.36 - x[i]) * (x[i] - 4) for i in 1:6]
pop = [f, g...]
d = 1

We can solve the problem using the dense moment-SOS hierarchy:

opt, sol, data = cs_tssos_first(pop, x, d, TS=false, CS=false, solution=true)

Afterwards, one can try strenghtening the bound via H1:

N = 5
eps = 0.05
dc = 1
gap_tol = 0.1
resultH1 = run_H1(pop,x,d,dc,N,eps,gap_tol)

or via H2

dc = 1
local_sol = sol
tau = 1.1
resultH2 = run_H2(pop,x,d,dc,local_sol,tau)

Alternatively, the problem can be solved using the correlatively sparse moment-SOS hierarchy:

opt, sol, data = cs_tssos_first(pop, x, d, TS=false, solution=true)

Afterwards, the bound can be strengthened either via H1CS:

N = 5
eps = 0.05
dc = 1
gap_tol = 0.1
resultH1CS = run_H1CS(pop,x,d,dc,N,eps,gap_tol)

or via H2CS

dc = 1
local_sol = sol
tau = 1.1
resultH2CS = run_H2CS(pop,x,d,dc,local_sol,tau)

Moreover, here is how different Christoffel polynomials can be constructed using the output of the:

dense Moment-SOS relaxation of order 2

d = 2
opt, sol, data = cs_tssos_first(pop, x, d, TS=false, CS=false, solution=true, Mommat=true)

k = 4
dc = 1
CDK_order1 = construct_CDK(x, dc, data.moment[1])  # Constructs multivariate Christoffel polynomial of order dc=1 (quadratic CDK)
CDK_4_order1 = construct_marginal_CDK(x, k, dc, data.moment[1])  # Constructs marginal Christoffel polynomial, associated to x_4, of order dc=1 

dc = 2
CDK_order2 = construct_CDK(x, dc, data.moment[1])  # Construct multivariate Christoffel polynomial of order dc=2 (quartic CDK)
CDK_4_order2 = construct_marginal_CDK(x, k, dc, data.moment[1])  # Constructs marginal Christoffel polynomial, associated to x_4, of order dc=2

sparse Moment-SOS relaxation of order 2

d = 2
opt, sol, data = cs_tssos_first(pop, x, d, TS=false, solution=true, Mommat=true)

k = 4
dc = 1
CDK_sparse_order1 = construct_CDK_cs(x, dc, data.moment, data.cliques)  # Constructs multivariate Christoffel polynomial of order dc=1 for each identified clique.
CDK_sparse_4_order1 = construct_marginal_CDK_cs(x, k, dc, data.moment, data.cliques)  # Constructs marginal Christoffel polynomial, associated to x_4, of order dc=1 

dc = 2
CDK_sparse_order2 = construct_CDK_cs(x, dc, data.moment, data.cliques)  # Constructs multivariate Christoffel polynomial of order dc=2 for each identified clique.
CDK_sparse_4_order2 = construct_marginal_CDK_cs(x, k, dc, data.moment, data.cliques)  # Constructs marginal Christoffel polynomial, associated to x_4, of order dc=2

Tips for modelling polynomial optimization problems

When possible, explictly include a sphere/ball constraint (or multi-sphere/multi-ball constraints).
When the feasible set is unbounded, try the homogenization technique introduced in Homogenization for polynomial optimization with unbounded sets.
Scale the coefficients of the polynomial optimization problem to $[-1, 1]$.
Scale the variables so that they take values in $[-1, 1]$ or $[0, 1]$.
Try to include more (redundant) inequality constraints.