User:Saung Tadashi/Polynomial Optimization

Polynomial optimization concerns a optimization problem where the objective is a multivariate polynomial and the constraints are defined by a semialgebraic set, that is, a set of equality and inequalities defined by polynomials. Polynomial optimization can be encountered in several problems from engineering and mathematics, such as control theory.

Although it is possible to find local minimizers using common tools from non-linear optimization, the problem of global optimization is more complex (precisely, NP-hard). Thus, common approaches to tackle a polynomial optimization problem are based on relaxing the problem to a sequence of easier problems whose solution converges to the global optimum of the original polynomial optimization problem.

Moments of measures

To solve a polynomial optimization problem, one can use a hierarchy of easier problems to approximate the original solution of the problem. A common approach is the Lasserre's hierarchy of semidefinite program.

Given a polynomial $p:\mathbb {R} ^{n}\rightarrow \mathbb {R}$, consider that the problem $\min _{x\in \mathbb {R} ^{n}}p(x)$ has a minimizer. It can be shown that this problem is related to finding a measure $\mu$ which minimizes $\int p(x)d\mu$. In fact,

$\inf _{x\in K}f(x)=\inf _{\mu }\left\{\int _{K}fd\mu :\mu {\text{ is a probability measure on }}K\right\}$

 Comment:

Sum of squares

Main article: Sum-of-squares optimization

Nonnegative circuit polynomials and geometric programming

See

Hyperbolic programming

See

Comparison of hierarchies

See Figure 1 of https://arxiv.org/abs/1903.04996.

References

To add:

• A bot will complete this citation soon. Click here to jump the queue arXiv:1811.05439.

See also

• Semidefinite programming
• Sum-of-squares optimization

Software tools

• GloptiPoly
• SparsePOP
• Ncpol2sdpa - A tool to convert a polynomial optimization problem of either commutative or noncommutative variables to a sparse semidefinite programming
• NCTSSOS - a sparse non-commutative polynomial optimization tool based on block moment-SOHS hierarchies.
• Sparse-BSOS - Implementation of bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
• TSSOS - A sparse polynomial optimization tool based on (quasi) block Moment-SOS hierarchies
• repop-toolbox - Tackling Polynomial Optimization Using Relative Entropy Relaxations (AM/GM polynomials)
• POEM – Effective Methods in Polynomial Optimization - Polynomial optimization via sums of nonnegative circuit polynomials (SONC)
• polMin - A Matlab toolbox for constrained and unconstrained polynomial optimization based on a nonuniform random coordinate minimization algorithm