Search

We prove that every semidefinite moment relaxation of a polynomial optimization problem (POP) with a ball constraint can be reformulated as a semidefinite program involving a matrix with constant trace property (CTP). As a result, such moment relaxations can be solved efficiently by first-order methods that exploit CTP, e.g., the conditional gradient-based augmented Lagrangian method. We also extend this CTP-exploiting framework to large-scale POPs with different sparsity structures. The efficiency and scalability of our framework are illustrated on some moment relaxations for various randomly generated POPs, especially second-order moment relaxations for quadratically constrained quadratic programs. [ABSTRACT FROM AUTHOR]

In a first contribution, we revisit two certificates of positivity on (possibly non-compact) basic semialgebraic sets due to Putinar and Vasilescu (C R Acad Sci Ser I Math 328(6):495–499, 1999). We use Jacobi's technique from (Math Z 237(2):259–273, 2001) to provide an alternative proof with an effective degree bound on the sums of squares weights in such certificates. As a consequence, it allows one to define a hierarchy of semidefinite relaxations for a general polynomial optimization problem. Convergence of this hierarchy to a neighborhood of the optimal value as well as strong duality and analysis are guaranteed. In a second contribution, we introduce a new numerical method for solving systems of polynomial inequalities and equalities with possibly uncountably many solutions. As a bonus, one can apply this method to obtain approximate global optimizers in polynomial optimization. [ABSTRACT FROM AUTHOR]

We provide a new degree bound on the weighted sum-of-squares (SOS) polynomials for Putinar–Vasilescu's Positivstellensatz. This leads to another Positivstellensatz saying that if f is a polynomial of degree at most 2 d f nonnegative on a semialgebraic set having nonempty interior defined by finitely many polynomial inequalities g j (x) ≥ 0 , j = 1 , ... , m with g 1 : = L − ‖ x ‖ 2 2 for some L > 0 , then there exist positive constants c ¯ and c depending on f , g j such that for any ε > 0 , for all k ≥ c ¯ ε − c , f has the decomposition (1) (1 + ‖ x ‖ 2 2) k (f + ε) = σ 0 + ∑ j = 1 m σ j g j , for some SOS polynomials σ j being such that the degrees of σ 0 , σ j g j are at most 2 (d f + k). Here ‖ ⋅ ‖ 2 denotes the ℓ 2 vector norm. As a consequence, we obtain a converging hierarchy of semidefinite relaxations for lower bounds in polynomial optimization on basic compact semialgebraic sets. The complexity of this hierarchy is O (ε − c) for prescribed accuracy ε > 0. In particular, if m = L = 1 then c = 65 , yielding the complexity O (ε − 65) for the minimization of a polynomial on the unit ball. [ABSTRACT FROM AUTHOR]

This work proposes a new moment-SOS hierarchy, called CS-TSSOS, for solving large-scale sparse polynomial optimization problems. Its novelty is to exploit simultaneously correlative sparsity and term sparsity by combining advantages of two existing frameworks for sparse polynomial optimization. The former is due to Waki et al. [40] while the latter was initially proposed by Wang et al. [42] and later exploited in the TSSOS hierarchy [46, 47]. In doing so we obtain CS-TSSOS—a two-level hierarchy of semidefinite programming relaxations with (i) the crucial property to involve blocks of SDP matrices and (ii) the guarantee of convergence to the global optimum under certain conditions. We demonstrate its efficiency and scalability on several large-scale instances of the celebrated Max-Cut problem and the important industrial optimal power flow problem, involving up to six thousand variables and tens of thousands of constraints. [ABSTRACT FROM AUTHOR]