Problem

The basic structure that describes a polynomial optimization problem. In order to perform optimizations on this problem, construct AbstractRelaxations from it. Note that the variables in a Problem are rewritten to internal data types, i.e., they will probably not display in the same way as the original variables (they are simply numbered consecutively).

This type is not exported.

See also poly_problem, poly_optimize, AbstractRelaxation.

poly_problem(objective; zero=[], nonneg=[], psd=[], perturbation=0.,
    factor_coercive=1, perturbation_coefficient=0., perturbation_form=0,
    noncompact=(0., 0), tighter=false, soscert=false, verbose=false,
    monomial_index_type=UInt)

Analyze a polynomial optimization problem and return a Problem that can be used for sparse analysis and optimization.

Arguments

Problem formulation

• objective::AbstractPolynomial: the objective that is to be minimized
• zero::AbstractVector{<:AbstractPolynomialLike}: a vector with all polynomials that should be constrained to be zero.
• nonneg::AbstractVector{<:AbstractPolynomialLike}: a vector with all polynomials that should be constrained to be nonnegative. The values of the polynomials must always be effectively real-valued (in the sense that their imaginary parts evaluate to zero even if no values are plugged in).
• psd::AbstractVector{<:AbstractMatrix{<:AbstractPolynomialLike}}: a vector of matrices that should be constrainted to be positive semidefinite. The matrices must be symmetric/hermitian.

Problem representation

• monomial_index_type::Type{<:Integer}: internally, whatever interface of MultivariatePolynomials is used, the data is converted to the efficient IntPolynomial representation. Every monomial is represented by a single number of the type given for this keyword argument. The default is usually a good choice, allowing quite large problems. For very small problems, the index type might be reduced (however, note that the index must be large enough to capture the monomial for every desired relaxation, and there will be no warning on overflow!); if the problem is extremely large, it might also be enlarged to UInt128 or BigInt, the latter in particular with potentially severe performance and memory consumption issues.

Problem modification

For unique solution extraction

• perturbation::Union{Float64, <:AbstractVector{Float64}}: adds a random linear perturbation with an absolute value not greater than this value to the objective for every variable (or, in the vector case, with different magnitudes for each variable). This will ensure that the result is unique and hence solution extraction will always work, at the cost of potentially reducing sparsity and slightly changing the actual result.

For noncompact sets

The following four parameters allow to automatically modify the problem according to a strategy by Mai, Lasserre, and Magron that was mainly developed for noncompact semialgebraic sets. It will modify the objective to

\[\mathrm{factor\_coercive} \bigl( \mathrm{objective} + \mathrm{perturbation\_coefficient} \cdot \mathrm{perturbation\_form} \bigr)\text.\]

Usually, perturbation_form and factor_coercive are both given by $1 + \lVert\mathrm{variables}\rVert^2$. If perturbation_coefficient is strictly positive, then for almost all degrees, the optimal value of the modified problem is then in $\bigl[f_{\mathrm{opt}}, f_{\mathrm{opt}} + \mathrm{perturbation\_coefficient} \cdot \mathrm{perturbation\_form}^{d_\mathrm o}(x_{\mathrm{opt}})\bigr]$. Often, this even works for a strictly zero coefficient (relatively generic conditions were found by Huang, Nie, and Yuan). Note that when modifying a problem in such a way, all sparsity methods provided by this package will be useless.

• factor_coercive::AbstractPolynomial: Let $k$ be divisible by $2r$, then this must be the dehomogenization of a coercive positive form in $n+1$ variables of degree $2r$ to the power $k/(2r)$. Be aware that using this parameter will multiply the objective by another polynomial and therefore require a higher total relaxation degree to model the problem! Set this factor to zero (or use the parameter soscert) in order to change the polynomial optimization problem into one of certifying membership in the cone of SOS polynomials.
• perturbation_coefficient::Float64: a nonnegative prefactor that determines the strength of the perturbation and whose inverse dictates the scaling of a sufficient lower degree bound that guarantees optimality.
• perturbation_form::AbstractPolynomial: must be the dehomogenization of a positive form in n+1 variables of degree 2(1+degree(objective)÷2).
• noncompact::Tuple{Real,Int}, now called $(\epsilon, k)$: this is a shorthand that will set the previous three parameters to their standard values, factor_coercive=(1 + sum(variables.^2))^k, perturbation_coefficient to the value passed to this parameter, and perturbation_form=(1 + sum(variables.^2))^maxhalfdegree(objective). Be aware that using this parameter will multiply the objective by another polynomial and therefore require a higher total relaxation degree to model the problem!

For convergence at earlier levels

Nie provides a way to add additional constraints based on optimality conditions to the problems. This can speed up or make possible convergence at all. However, not every problem can be tightened in such a way, and sometimes, tightening might also increase the minimal degree required to optimize the problem. Note that the problem will end up with more equality and inequality constraints than originally entered. The augmentation does not change the solution of the original problem in case the minimum is attained at a critical point; if it is not, tightening will lead to missing this minimum.

• tighter::Union{Bool,Symbol}: if set to a valid solver or true (= choose default), tries to automatically construct constraints using Nie's method. Note that the algorithm internally needs to create lots of dense polynomials of appropriate degrees before solving for the coefficients. It is therefore possible that for larger problems, this can take a very long time. For a list of supported solvers, see the solver reference. This parameter can also be called tighten; if any of those two is true, it is assumed that this was the intended value.

SOS membership

Usually, a problem constructed with poly_problem will minimize the given objective under the constraints. Instead, membership of the objective in the quadratic module generated by the constraints can also be checked.

• soscert::Bool: if set to true, disables the lower bound optimization. This is simply a shorthand for setting factor_coercive to zero.

Progress monitoring

• verbose::Bool: if set to true, information about the current state of the method is printed; this may be useful for large and complicated problems whose construction can take some time.

See also Problem, poly_optimize, Relaxation.AbstractRelaxation.

variables(problem::Union{Problem,<:AbstractRelaxation})

Returns the original variables (not their internal rewrites) associated to a given polynomial optimization problem. This defines the order in which solutions are returned. In the complex case, they do not contain conjugates.

See also poly_optimize, poly_solutions, poly_all_solutions.

nvariables(problem::Union{Problem,<:AbstractRelaxation})

Returns the number of variables associated to a given polynomial optimization problem. In the complex case, conjugates are not counted.

See also variables.

isreal(problem::Union{Problem,<:AbstractRelaxation})

Returns whether a given polynomial optimization problem contains only real-valued variables or also complex ones.

AbstractRelaxation

This is the general abstract type for any kind of relaxation of a polynomial optimization problem. Its concrete types can be used for analyzing and optimizing the problem.

See also poly_problem, Problem, poly_optimize.

poly_problem(relaxation::AbstractRelaxation)

Returns the original problem associated with a relaxation.

basis(relaxation::AbstractRelaxation[, clique::Int]) -> IntMonomialVector

Constructs the basis that is associated with a given polynomial relaxation. If clique is given, only the monomials that are relevant for the given clique must be returned.

degree(problem::AbstractRelaxation)

Returns the degree associated with the relaxation of a polynomial optimization problem.

See also poly_problem.

groupings(relaxation::AbstractRelaxation) -> RelaxationGroupings

Analyze the current state and return the bases and cliques as indicated by its relaxation in a RelaxationGroupings struct.

iterate!(relaxation::AbstractRelaxation)

Some sparse polynomial optimization relaxations allow to iterate their sparsity, which will lead to a more dense representation and might give better bounds at the expense of a more costly optimization. Return nothing if the iterations converged (state did not change any more), else return the new state. Note that state will be modified.

Relaxation.XXX(problem::Problem[, degree]; kwargs...)

This is a convenience wrapper for Relaxation.XXX(Relaxation.Dense(problem, degree)) that works for any AbstractRelaxation XXX. degree is the degree of the Lasserre relaxation, which must be larger or equal to the halfdegree of all polynomials that are involved. If degree is omitted, the minimum required degree will be used. Specifying a degree larger than the minimal only makes sense if there are inequality or PSD constraints present, else it needlessly complicates calculations without any benefit.

The keyword arguments will be passed on to the constructor of XXX.

RelaxationGroupings

Contains information about how the elements in a certain (sparse) polynomial optimization problem combine. Groupings are contained in the fields obj, zero, nonneg, and psd:

• $\sum_i \mathit{obj}_i^\top \sigma_i \overline{\mathit{obj}_i}$ is the SOS representation of the objective with $\sigma_i \succeq 0$
• $\sum_i \mathit{zero}_{k, i}^\top f_k$ is the prefactor for the kᵗʰ equality constraint with $f_k$ a free vector
• $\sum_i \mathit{nonneg}_{k, i}^\top \sigma_{k, i} \overline{\mathit{nonneg}_{k, i}}$ is the SOS representation of the prefactor of the kᵗʰ nonnegative constraint with $\sigma_{k, i} \succeq 0$
• $\sum_i (\mathit{psd}_{k, i}^\top \otimes \mathbb1) Z_{k, i} (\overline{\mathit{psd}_{k, i}} \otimes \mathbb1)$ is the SOS matrix representation of the prefactor of the kᵗʰ PSD constraint with $Z_{k, i} \succeq 0$

The field var_cliques contains a list of sets of variables, each corresponding to a variable clique in the total problem. In the complex case, only the declared variables are returned, not their conjugates.

AbstractRelaxationBasis{Prob} <: AbstractRelaxation{Prob}

An AbstractRelaxationBasis is a relaxation of a polynomial optimization problem that is built using a single basis for everything (objective and constraints). The groupings for the individual elements will come from a degree truncation of the same shared basis for all constituents of the problem (intersected with a parent grouping).

Dense(problem::Problem[, degree])

Constructs a full dense relaxation out of a polynomial optimization problem. This is the largest possible representation for a given degree bound, giving the best bounds. It is wasteful at the same time, as a Newton relaxation gives equally good bounds; but contrary to the Newton one, solution reconstruction works much better with a dense basis. degree is the degree of the Lasserre relaxation, which must be larger or equal to the halfdegree of all polynomials that are involved. If degree is omitted, the minimum required degree will be used. Specifying a degree larger than the minimal only makes sense if there are inequality or PSD constraints present, else it needlessly complicates calculations without any benefit.

Custom(problem::Problem, basis)

Constructs a relaxation out of a polynomial optimization problem for the case in which a suitable basis is already known.

AbstractRelaxationSparse{Prob} <: AbstractRelaxation{Prob}

An AbstractRelaxationSparse is a relaxation of a polynomial optimization problem that applies sparsity methods to reduce the size of the associated problem.

Newton(relaxation::AbstractRelaxation; [method,] parameters...)

Constructs a relaxation based on the Newton halfpolytope applied to another relaxation of a polynomial optimization problem. This will be a superset of the largest possible representation for a given degree bound, with no negative consequences for finding the optimum. It can be much smaller than a dense basis, but solution reconstruction may be harder.

When constraints are present, the polytope is determined based on the Putinar reformulation, where all constraints and the objective are moved to one side (comprising a new virtual objective). The groupings for the constraints are determined by the previous relaxation method and not affected by the Newton polytope.

Note that for the complex-valued hierarchy, strictly speaking there is no "Newton polytope"; as the representation of complex-valued polynomials is unique, the process is much simpler there; still, the size reduction is accomplished by using Newton.

The method determines which solver to use for determining the Newton polytope. If omitted, this will be the default solver (in the complex case, it must be :complex). The parameters are passed on to Newton.halfpolytope.

CliqueMerged(relaxation::AbstractRelaxation)

Performs clique merging on the parent relaxation. Clique merging may allow to reduce the solver time by merging together smaller blocks of variables with huge overlap into a single larger one; however, it comes at a significant cost itself. Basically, clique merging undoes some of the sparsity analysis performed before when it might be too excessive. This is is an equivalent reformulation that is as exact as relaxation itself.

SparsityCorrelative(relaxation::AbstractRelaxation; [high_order_zero,]
    [high_order_nonneg,] [high_order_psd,] [low_order_zero,] [low_order_nonneg,]
    [low_order_psd,] chordal_completion=CliqueTrees.MF(),
    [split_psd,] [join_psd,] verbose::Bool=false)

Analyze the correlative sparsity of a problem. Correlative sparsity is a variable-based sparsity analysis. It was first defined by Waki et al. in 2006 and extended by Josz and Molzahn in 2018. Variables are grouped into cliques based on the terms in the objective in which they appear together. Additional grouping is induced by variables that occur anywhere in a constraint of high order; or by variables that occur in a term in a constraint of low order. The parameters high_order_... allow to specify which constraints - identified by their indices - are of high order. If the parameter is omitted, all such constraints are of high order. Conversely, low_order_... can be used to specify that all but the listed constraints are of high order. Both parameters cannot be used simultaneously for the same set of constraints. Note that the order of the constraints is also influenced by the parent relaxation. If a correlative sparsity relaxation is applied to another relaxation that already limited the prefactor of a constraint to be of degree zero, it must necessarily be of low order. A PSD constraint is by default handled as one monolithic constraint. However, the groupings can also be constructed separately per index; then, only variables that occur in the kᵗʰ row or kᵗʰ column are put into a clique. This corresponds to setting the split_psd parameters to the indices of the constraints that should be separated in this way; the opposite effect (default) is achieved by join_psd. All values may also be true (to indicate all constraints) or false (to indicate none)

By default, the correlative sparsity graph is completed to a chordal graph before the cliques are determined, which guarantees that the maximal cliques can be determined quickly; however, this may degrade the sparsity and it may be favorable not to carry out the completion. The argument chordal_completion may be set to false for this; any of the allowed elimination algorithms from CliqueTrees.jl are other possible arguments. true (deprecated) defaults to MF().

If correlative and term sparsity are to be used together, use SparsityCorrelativeTerm instead of nesting the sparsity objects.

SparsityTerm

Common base class that term sparsity methods use or wrap. The SparsityTermBlock and SparsityTermChordal constructors are shorthands that create SparsityTerm objects with the method parameter appropriately set. SparsityCorrelativeTerm is a very thin wrapper around SparsityTerm.

SparsityTermBlock(relaxation::AbstractProblem; verbose::Bool=false)

Analyze the term sparsity of the problem. Term sparsity is a recent iterative sparsity analysis that groups terms with shared supports. Its last iteration will give the same optimal value as the original problem, although it may still be of a smaller size. Often, even the uniterated analysis already gives the same bound as the dense problem. The terms are grouped based on connected components of a graph; this can be improved by using the smallest chordal extension (see SparsityTermChordal), which will lead to even smaller problem sizes, but typically also worse bounds.

If correlative and term sparsity are to be used together, use SparsityCorrelativeTerm or nest the sparsity objects.

SparsityTermChordal(relaxation::AbstractProblem; chordal_completion=CliqueTrees.MF(), verbose=false)

Analyze the term sparsity of the problem using chordal cliques. Chordal term sparsity is a recent iterative sparsity analysis that groups terms with shared supports. Even in its last iteration, it may give strictly smaller values than the dense problem. The basis elements are grouped in terms of chordal cliques of the term sparsity graph. This uses maximal cliques; as obtaining maximal cliques of an arbitrary graph is not efficient, the graph is extended to a chordal graph if chordal_completion is a valid elimination algorithm from CliqueTrees or true (deprecated, equals CliqueTrees.MF()) using a heuristic. Disabling the chordal completion can lead to smaller problem sizes.

If correlative and term sparsity are to be used together, use SparsityCorrelativeTerm or nest the sparsity objects.

SparsityCorrelativeTerm(relaxation::AbstractRelaxation; method=TERM_MODE_BLOCK, kwargs...)

Analyze both the correlative as well as the term sparsity of the problem. This is the most versatile kind of sparsity analysis, combining the effects of correlative sparsity with term analysis per clique. However, it is nothing more than first performing correlative sparsity analysis, followed by term sparsity analysis. This constructor will take all keyword arguments and distribute them appropriately to the SparsityCorrelative and SparsityTerm constructors. The returned object will be a very thin wrapper around SparsityTerm, with the only difference in printing; SparsityCorrelativeTerm objects by default print the clique grouping. Note that the same can be achieved for any relaxation (or groupings of a relaxation) if the IO parameter bycliques is set to true.

See also SparsityCorrelative, SparsityTermBlock, SparsityTermChordal, TermMode.

SparsityCorrelativeTerm(relaxation::SparsityCorrelative; method=TERM_MODE_BLOCK, kwargs...)

This form allows to wrap an already created correlative sparsity pattern into a term sparsity pattern.

See also SparsityCorrelative, TermMode.

@enum TermMode TERM_MODE_DENSE TERM_MODE_BLOCK TERM_MODE_CLIQUES
    TERM_MODE_CHORDAL_CLIQUES TERM_MODE_NONE

Specifies which kind of completion procedure is used for the iteration of term sparsity pattern. Valid values are TERM_MODE_DENSE (Dense), TERM_MODE_BLOCK (SparsityTermBlock), TERM_MODE_CHORDAL_CLIQUES (SparsityTermChordal), and TERM_MODE_CLIQUES (SparsityTermChordal with chordal_completion = false). TERM_MODE_NONE can be used during iteration to disable the iteration of individual constraints.

iterate!(relaxation::Union{SparsityTerm,SparsityCorrelativeTerm}; [method,]
    objective=true, zero=true, nonneg=true, psd=true, varclique_methods=missing[,
    chordal_completion])

SparsityTerm implementations allow to customize the iteration procedure by the keyword arguments. The arguments objective, zero, nonneg, and psd can be boolean values (false means that these elements will not contribute to the iteration, true that they will). zero, nonneg, and psd can also be AbstractSets of integers, indicating that only the constraints with the indices specified in the set will contribute to the iteration. This all implies that the method used for their iteration will be given by method. Custom methods can be assigned if the parameters are set to a TermMode or a vector of TermModes. The elimination algorithm for chordal cliques may be overwritten by chordal_completion.

The parameter method therefore determines the default that is assigned to the elements, and if not specified, it will be determined by the default method with which relaxation was constructed. Instead of a single TermMode, method may also be a vector successively assigning modes to the objective, the first zero constraints, ..., the nonnegative constraints, the psd constraints (eliminating the need for the other keywords).

The parameter varclique_methods instead allows to assign custom methods to individual variable cliques. Note that a variable clique can cover the objective and all constraints; in the case of conflicting assignments, the clique assignment takes precedence (but a clique mode may also be missing individually, in which case the default is taken).

poly_optimize([method, ]relaxation::AbstractRelaxation; verbose=false,
    representation=RepresentationPSD(), [precision::Real], kwargs...)

Optimize a relaxed polynomial optimization problem that was construced via poly_problem and then wrapped into an AbstractRelaxation. Returns a Result object.

Instead of modeling the moment/SOS matrices as positive semidefinite, other representations such as the (scaled) diagonally dominant description are also possible. The representation parameter can be used to define a representation that is employed for the individual groupings. This may either be an instance of a RepresentationMethod - which requires the method to be independent of the dimension of the grouping - or a callable. In the latter case, it will be passed as a first parameter an identifier^[1] of the current conic variable, and as a second parameter the side dimension of its matrix. The method must then return a RepresentationMethod instance.

verbose=true will enable logging; this will print basic information about the relaxation itself as well as instruct the solver to output a detailed log. The PSD block sizes reported accurately represent the side dimensions of semidefinite variables and how many of these variables appear. The free block sizes are only very loose upper bounds on the maximal number of equality constraints that will be constructed by multiplying two elements from a block, as duplicates will be ignored. Any additional keyword argument is passed on to the solver.

For a list of supported methods, see the solver reference. If method is omitted, the default solver is used. Note that this depends on the loaded solver packages, and possibly also their loading order if no preferred solver has been loaded.

The keyword arguments are different for every solver; in general, if the solver permits access to its configuration options via a name, each option can be passed as a keyword argument. If the solver requires the use of integer constants (that are defined in some solver package), the options must be passed in the parameters keyword argument, which must be an iterable of pair-like elements. As the parameters for each solver are quite different, the optional precision argument will set some characteristic options related to the precision of the result (feasibility measures, duality gap) all to this value unless they are overwritten explicitly. However, be aware that each solver defines its own set of termination criteria, so the meaning of precision is not very strict.

See also RepresentationIAs.

poly_optimize([method, ]problem::Problem[, degree::Int]; kwargs...)

Construct a Relaxation.Dense by default.

poly_optimize(result::Result; [representation=IterateRepresentation(), ]kwargs...)

Re-optimizes a previously optimized polynomial optimization problem. This is usually pointless, as the employed optimizers will find globally optimal solutions. However, this method allows to change the representation used for the constraints (or objective). If representation is a callable, it will now receive as a third parameter the type of the RepresentationMethod used before for this constraint^[2], and as a fourth parameter the associated SOS matrix from the previous optimization. For efficiency reasons, this should only be used for changes that preserve the structure of the representation (i.e., whether it was PSD/DD/SDD and if its rotation was diagonal, triangular, or dense). If a structure non-preserving change is made, the problem needs to be constructed from scratch. For non-diagonal rotations, consider using RepresentationIAs in the first optimization.

See also IterateRepresentation.

RepresentationMethod{M,Complex}

Union type that defines how the optimizer constraint σ ⪰ 0 is interpreted. Usually, "⪰" means positive semidefinite; however, there are various other possibilities giving rise to weaker results, but scale more favorably. The following methods are supported:

• RepresentationPSD
• RepresentationSDD
• RepresentationDD

See also RepresentationIAs.

RepresentationPSD <: RepresentationMethod

Model the constraint "σ ⪰ 0" as a positive semidefinite cone membership, σ ∈ PSD. This is the strongest possible model, but the most resource-intensive.

RepresentationSDD([u]; complex=true) <: RepresentationMethod

Model the constraint "σ ⪰ 0" as a membership in the scaled diagonally dominant cone, $\sigma = u^\dagger Q u$ for some Q ∈ SDD. The matrix u is by default an identity of any dimension; however, usually, care must be taken to have a matrix of suitable dimension. The membership Q ∈ SDD is achieved using the scaled diagonally dominant (dual) cone directly or (rotated) quadratic cones.

If σ is a Hermitian matrix, a complex-valued scaled diagonally dominant (dual) cone will be used, if supported. If not, fallbacks to the (rotated) quadratic cones are used; however, if complex=false and the ordinary scaled diagonally dominant (dual) cone is supported, rewrite the matrix as a real one and then use the real-valued cone. This is usually never advisable, as the rotated quadratic cone always works on the complex data. Note that if rewritten, u must be real-valued and have twice the side dimension of the complex-valued matrix.

RepresentationDD([u]; complex=true) <: RepresentationMethod

Model the constraint "σ ⪰ 0" as a membership in the diagonally dominant cone, $\sigma = u^\dagger Q u$ for some Q ∈ DD. The matrix u is by default an identity of any dimension; however, usually, care must be taken to have a matrix of suitable dimension. The membership Q ∈ DD is achieved using the diagonally dominant (dual) cone directly, $\ell_1$- or $\ell_\infty$-norm cones or linear inequalities; slack variables will be added as necessary.

If σ is a Hermitian matrix, a complex-valued diagonally dominant (dual) cone will be used, if supported. If not, fallbacks will first try quadratic cones on the complex-valued data, and if this is also not supported, rewrite the matrix as a real one and then apply the real-valued DD constraint. By setting the complex parameter to false, the rewriting to a real matrix will always be used, regardless of complex-valued solver support. Note that if rewritten, u must be real-valued and have twice the side dimension of the complex-valued matrix.

RepresentationIAs(r::Type{RepresentationDD,RepresentationSDD},
    m::Type{<:AbstractMatrix}=UpperTriangular; complex=true)

Default callable that will instantiate a correctly-sized representation of type r with an identity rotation that is, however, not recognized as a diagonal rotation but as type m instead. Use this type in the first call to poly_optimize if you want to re-optimize the problem afterwards with rotations of type m. The default for m, UpperTriangular, is suitable for the automatic Cholesky-based reoptimization.

Result

Result of a polynomial optimization, returned by calling poly_optimize on an AbstractRelaxation. A Result struct r contains information about

• the relaxation employed for the optimization (r.relaxation)
• the optimized problem (available via poly_problem)
• the used method (r.method)
• the time required for the optimization in seconds (r.time)
• the status of the solver (r.status), which also depends on the solver type. Use issuccess to check whether this is a successful status.
• the returned primal value of the solver (r.objective), which, if the status was successful, is a lower bound to the true minimum
• the moment information in vector form (r.moments), which allows to construct a moment matrix, extract solutions (poly_all_solutions or poly_solutions), and an optimality certificate.

This type is not exported.

issuccess(r::Result)

Returns true if the solver successfully solved the relaxation and provided a solution, and false otherwise.

poly_problem(r::Result)

Returns the problem that was associated with the optimization result.

optimality_certificate(result::Result, ϵ=1e-6)

This function applies the flat extension/truncation criterion to determine whether the optimality of the given problem can be certified, in which case it returns :Optimal. If no such certificate is found, the function returns :Unknown. The criterion is meaningless for sparse problems or if a full basis is not available. The parameter ϵ controls the bound below which singular values are considered to be zero, and its negative below which eigenvalues are considered to be negative.

See also poly_optimize.

poly_all_solutions([method, ]result::Result, args...; verbose=false, rel_threshold=100,
    abs_threshold=Inf, kwargs...)

Obtains a vector of all the solutions to a previously optimized problem; then iterates over all of them and grades and sorts them by their badness. Every solution of the returned vector is a tuple that first contains the optimal point and second the badness at this point. Solutions that are rel_threshold times worse than the best solution or worse than abs_threshold will be dropped from the result.

See also poly_optimize, poly_solutions.

poly_solutions([method, ]result::Result, args...; verbose, kwargs...)

Extracts solutions from a polynomial optimization result using the method method. Depending on the chosen method, the result may be an iterator or a vector. Consult the documentation of the methods for further information. If method is omitted, a default method will be chosen according to the relaxation that was used for the optimization.

See also poly_optimize, poly_all_solutions.

poly_solution_badness(result::Result, solution)

Determines the badness of a solution by comparing the value of the objective with the value according to the optimization given in result, and also by checking the violation of the constraints. The closer the return value is to zero, the better. If the return value is too large, solution probably has nothing to do with the actual solution.

See also poly_optimize, poly_solutions, poly_all_solutions.

moment_matrix(problem::Result; max_deg=Inf, prefix=1)

After a problem has been optimized, this function assembles the associated moment matrix (possibly by imposing a degree bound max_deg, and possibly multiplying each monomial by the monomial or variable prefix, which does not add to max_deg). Note that prefix has to be a valid IntMonomial or IntVariable of appropriate type.

See also poly_optimize, poly_optimize.

MomentVector(relaxation::AbstractRelaxation, values::AbstractVector{R} where {R<:Real})

MomentVector is a representation of the result of a polynomial optimization. It contains all the values of the moments that were present in the optimization problem. This vector can be indexed in two ways:

• linearly, which will just transparently yield what linearly indexing values would yield
• with a monomial (or multiple monomials, which means that the product of all the monomials is to be considered), which will yield the value that is associated with this monomial; if the problem was complex-valued, this will be a Complex{R}.

In order to get an association-like iterator, use MomentAssociation.

This type is not exported.

MomentAssociation(m::MomentVector)

Creates a associative iterator over the moment vector m that, upon iteration, returns Pairs assigning values to monomials.

This type is not exported.

SOSCertificate(result::Result)

Construct a SOS certificate from a given optimization result. The returned object will pretty-print to show the decomposition of the optimization problem in terms of a positivstellensatz. To obtain the polynomials for the individual terms, the object can be indexed. The first index is one of :objective, :zero, :nonneg, :psd; the second index is the number of the desired element (omitted for :objective); the last index is the index of the desired grouping due to sparsity. If the last index is omitted, a vector over all groupings is returned.

The returned vectors of polynomials are, for :objective and :nonneg, to be summed over their squares; for :psd, the returned matrix m of polynomials is to be left-multiplied with its adjoint: m' * m. For :zero, a single polynomial is returned. If all these operations are carried out while multiplying with the corresponding prefactors (i.e., the constraints themselves), the resulting polynomial should be equal to the original objective. Note that this need not be the case; only if the relaxation level was sufficient will a SOS certificate in fact be valid.

sos_matrix(relaxation::AbstractRelaxation, state[, constraint])

Extracts the SOS matrices associated with a solved relaxation. A constraint is identified in the same way as the first argument that is passed to a RepresentationMethod (see ^[1]). Short forms are allowed when there is just a single grouping. Usually, a SOSCertificate is more desirable than the construction of individual SOS matrices.

IterateRepresentation(; keep_structure=false)

Default iteration method for DD and SDD representations. This is will perform a Cholesky decomposition of the old SOS matrix and use it as the new rotation, ensuring that results never get worse (at least in theory; since a positive definite SOS matrix is only guaranteed up to a certain tolerance, bad things could still happen).

Note that the resulting rotation matrix will be upper triangular, which may break a previous structure. By setting keep_structure to true, the structure will be preserved (if it was diagonal, this would mean keeping only the diagonal of the Cholesky factor, with no theoretical guarantees, not even about convergence; if it was lower triangular the adjoint will be taken, which will not give any convergence guarantees, as the rotated DD/SDD cone is implemented with respect to the upper triangular factorization).

See also poly_optimize

halfpolytope(method, poly; verbose=false, preprocess_quick=true,
    preprocess_randomized=false, preprocess_fine=false, preprocess=nothing,
    filepath=nothing, parameters...)

Calculates the Newton polytope for the sum of squares optimization of a given objective, which is half the Newton polytope of the objective itself. This requires the availability of a linear solver. For a list of supported solvers, see the solver reference.

There are three preprocessing methods which can be turned on individually or collectively using preprocess; depending on the problem, they may reduce the amount of time that is required to construct the convex hull of the full Newton polytope:

• preprocess_quick is the Akl-Toussaint heuristic. Every monomial will be checked against a linear program that scales as the number of variables in the objective. This is enabled by default.
• preprocess_randomized performs a reduction of the possible number of monomials that comprise the convex hull by picking smaller random subsets of them and eliminating entries in the subset that can be expressed by other entries. This is a good idea if the number of candidate monomials for the vertices of the convex hull is huge (so that preprocess_fine will take too long) but also very redundant. The final polish can be done by enabling both this and the following preprocessing option. Randomized reduction will use multithreading if possible.
• preprocess_fine performs an extensive reduction of the possible number of monomials that comprise the convex hull. Every monomial will be checked against a linear program that scales as the number of monomials in the objective (though it might become more efficient when monomials are ruled out).

After preprocessing is done, the monomials in the half Newton polytope are constructed efficiently subject to a simple min/max-degree constraint using ExponentsMultideg and taken over into the basis if they are contained in the convex polytope whose vertices were determined based on the objective and preprocessing; this is done by performing a linear program for each candidate monomial.

The parameters will be passed on to the linear solver in every case (preprocessing and construction).

See also halfpolytope_from_file.

halfpolytope_from_file(filepath, objective; estimate=false, verbose=false)

Constructs the Newton polytope for the sum of squares optimization of a given objective, which is half the Newton polytope of the objective itself. This function does not do any calculation, but instead loads the data that has been generated using halfpolytope with the given filepath on the given objective.

See also halfpolytope.