Search

In this paper, we consider polynomial optimization with correlative sparsity. We construct correlatively sparse Lagrange multiplier expressions (CS-LMEs) and propose CS-LME reformulations for polynomial optimization problems using the Karush-Kuhn-Tucker optimality conditions. Correlatively sparse sum-of-squares (CS-SOS) relaxations are applied to solve the CS-LME reformulation. We show that the CS-LME reformulation inherits the original correlative sparsity pattern, and the CS-SOS relaxation provides sharper lower bounds when applied to the CS-LME reformulation, compared with when it is applied to the original problem. Moreover, the convergence of our approach is guaranteed under mild conditions. In numerical experiments, our new approach usually finds the global optimal value (up to a negligible error) with a low relaxation order for cases where directly solving the problem fails to get an accurate approximation. Also, by properly exploiting the correlative sparsity, our CS-LME approach requires less computational time than the original LME approach to reach the same accuracy level. [ABSTRACT FROM AUTHOR]

We consider the problem of decomposing a regular non-negative function as a sum of squares of functions which preserve some form of regularity. In the same way as decomposing non-negative polynomials as sum of squares of polynomials allows to derive methods in order to solve global optimization problems on polynomials, decomposing a regular function as a sum of squares allows to derive methods to solve global optimization problems on more general functions. As the regularity of the functions in the sum of squares decomposition is a key indicator in analyzing the convergence and speed of convergence of optimization methods, it is important to have theoretical results guaranteeing such a regularity. In this work, we show second order sufficient conditions in order for a p times continuously differentiable non-negative function to be a sum of squares of p-2 differentiable functions. The main hypothesis is that, locally, the function grows quadratically in directions which are orthogonal to its set of zeros. The novelty of this result, compared to previous works is that it allows sets of zeros which are continuous as opposed to discrete, and also applies to manifolds as opposed to open sets of Rd. This has applications in problems where manifolds of minimizers or zeros typically appear, such as in optimal transport, and for minimizing functions defined on manifolds. [ABSTRACT FROM AUTHOR]

A striking pathology of semidefinite programs (SDPs) is illustrated by a classical example of Khachiyan: feasible solutions in SDPs may need exponential space even to write down. Such exponential size solutions are the main obstacle to solving a long standing, fundamental open problem: can we decide feasibility of SDPs in polynomial time? The consensus seems that SDPs with large size solutions are rare. However, here we prove that they are actually quite common: a linear change of variables transforms every strictly feasible SDP into a Khachiyan type SDP, in which the leading variables are large. As to "how large," that depends on the singularity degree of a dual problem. Further, we present some SDPs coming from sum-of-squares proofs, in which large solutions appear naturally, without any change of variables. We also partially answer the question how do we represent such large solutions in polynomial space? [ABSTRACT FROM AUTHOR]

We study the problem of decomposing a polynomial p into a sum of r squares by minimizing a quadratically penalized objective fp(u)= ...2. This objective is nonconvex and is equivalent to the rank-r Burer--Monteiro factorization of a semidefinite program (SDP) encoding the sum of squares decomposition. We show that for all univariate polynomials p, if r\geq 2, then fp(u) has no spurious second-order critical points, showing that all local optima are also global optima. This is in contrast to previous work showing that for general SDPs, in addition to genericity conditions, r has to be roughly the square root of the number of constraints (the degree of p) for there to be no spurious second-order critical points. Our proof uses tools from computational algebraic geometry and can be interpreted as constructing a certificate using the first- and second-order necessary conditions. We also show that by choosing a norm based on sampling equally spaced points on the circle, the gradient ᐁ fp can be computed in nearly linear time using fast Fourier transforms. Experimentally we demonstrate that this method has very fast convergence using first-order optimization algorithms such as L-BFGS, with near-linear scaling to million-degree polynomials. [ABSTRACT FROM AUTHOR]

We consider the unconstrained optimization of multivariate trigonometric polynomials by the sum-of-squares hierarchy of lower bounds. We first show a convergence rate of O(1/s²) for the relaxation with degree s without any assumption on the trigonometric polynomial to minimize. Second, when the polynomial has a finite number of global minimizers with invertible Hessians at these minimizers, we show an exponential convergence rate with explicit constants. Our results also apply to minimizing regular multivariate polynomials on the hypercube. [ABSTRACT FROM AUTHOR]

We present a method for finding lower bounds on the global infima of integral variational problems, wherein ∫Ωf(x,u(x),∇u(x))dx is minimized over functions u:Ω⊂Rn → Rm satisfying given equality or inequality constraints. Each constraint may be imposed over Ω or its boundary, either pointwise or in an integral sense. These global minimizations are generally nonconvex and intractable. We formulate a particular convex maximization, here called the pointwise dual relaxation (PDR), whose supremum is a lower bound on the infimum of the original problem. The PDR can be derived by dualizing and relaxing the original problem; its constraints are pointwise equalities or inequalities over finite-dimensional sets rather than over infinite-dimensional function spaces. When the original minimization can be specified by polynomial functions of (x,u,∇u), the PDR can be further relaxed by replacing pointwise inequalities with polynomial sum-of-squares (SOS) conditions. The resulting SOS program is computationally tractable when the dimensions m,n and the number of constraints are not too large. The framework presented here generalizes an approach of Valmorbida, Ahmadi, and Papachristodoulou [IEEE Trans. Automat. Control, 61 (2016), pp. 1649-1654]. We prove that the optimal lower bound given by the PDR is sharp for several classes of problems, whose special cases include leading eigenvalues of Sturm-Liouville problems and optimal constants of Poincaré inequalities. For these same classes, we prove that SOS relaxations of the PDR converge to the sharp lower bound as polynomial degrees are increased. Convergence of SOS computations in practice is illustrated for several examples. [ABSTRACT FROM AUTHOR]

Assessing nonnegativity of multivariate polynomials over the reals, through the computation of certificates of nonnegativity, is a topical issue in polynomial optimization. This is usually tackled through the computation of sum of squares decompositions which rely on efficient numerical solvers for semidefinite programming. This method faces two difficulties. The first one is that the certificates obtained this way are approximate and then nonexact. The second one is due to the fact that not all nonnegative polynomials are sums of squares. In this paper, we build on previous works by Parrilo and Nie, Demmel, and Sturmfels who introduced certificates of nonnegativity modulo gradient ideals. We prove that, actually, such certificates can be obtained exactly over the rationals if the polynomial under consideration has rational coefficients, and we provide exact algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bitsize bounds of such certificates. [ABSTRACT FROM AUTHOR]

This work is a follow-up and a complement to [J. Wang, V. Magron and J. B. Lasserre, preprint, arXiv: 1912.08899, 2019] where the TSSOS hierarchy was proposed for solving polynomial optimization problems (POPs). The chordal-TSSOS hierarchy that we propose is a new sparse moment-SOS framework based on term sparsity and chordal extension. By exploiting term sparsity of the input polynomials we obtain a two-level hierarchy of semidefinite programming relaxations. The novelty and distinguishing feature of such relaxations is to involve block matrices obtained in an iterative procedure that performs chordal extension of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Various numerical examples demonstrate the efficiency and the scalability of this new hierarchy for both unconstrained and constrained POPs. The two hierarchies are complementary. While the former TSSOS [J. Wang, V. Magron and J. B. Lasserre, preprint, arXiv:1912.08899, 2019] has a theoretical convergence guarantee (to the dense moment-SOS relaxation), the chordal-TSSOS has superior performance but lacks this theoretical guarantee. [ABSTRACT FROM AUTHOR]

This paper is concerned with polynomial optimization problems. We show how to exploit term (or monomial) sparsity of the input polynomials to obtain a new converging hierarchy of semidefinite programming relaxations. The novelty (and distinguishing feature) of such relaxations is to involve block-diagonal matrices obtained in an iterative procedure performing completion of the connected components of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Our theoretical framework is then applied to compute lower bounds for polynomial optimization problems either randomly generated or coming from the networked system literature. [ABSTRACT FROM AUTHOR]

Chvátal–Gomory cuts (CG-cuts) and the Bienstock–Zuckerberg hierarchy capture useful linear programs that the standard bounded degree sum-of-squares (SoS) hierarchy fails to capture. In this paper we present a novel polynomial time SoS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low degree polynomials). We show that the new SoS hierarchy recovers the Bienstock–Zuckerberg hierarchy. Our result implies a linear program that reproduces the Bienstock–Zuckerberg hierarchy as a polynomial-sized, efficiently constructible extended formulation that satisfies all constant pitch inequalities. The construction is also very simple, and it is fully defined by giving the supporting polynomials. Moreover, for a class of polytopes (e.g., set cover and packing problems), the resulting SoS hierarchy optimizes in polynomial time over the polytope resulting from any constant rounds of CG-cuts, up to an arbitrarily small error in the solution value. Arguably, this is the first example where different basis functions can be useful in asymmetric situations to obtain a hierarchy of relaxations. [ABSTRACT FROM AUTHOR]

In this paper, we study polynomial norms, i.e., norms that are the dth root of a degree-d homogeneous polynomial f. We first show that a necessary and sufficient condition for f1/d to be a norm is for f to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from dth roots of polynomials, we prove that any norm can be approximated arbitrarily well by a polynomial norm. We then investigate the computational problem of testing whether a form gives a polynomial norm. We show that this problem is strongly NP-hard already when the degree of the form is 4, but can always be answered by solving a hierarchy of semidefinite programs. We further study the problem of optimizing over the set of polynomial norms using semidefinite programming. To do this, we introduce the notion of r-sum of squares-convexity and extend a result of Reznick on sum of squares representations of positive definite forms to positive definite biforms. We conclude with some applications of polynomial norms to statistics and dynamical systems. [ABSTRACT FROM AUTHOR]

In this article we present a robustness analysis of the extraction of optimizers in polynomial optimization. Optimizers can be extracted by solving moment problems using atness and the Gelfand-Naimark-Segal (GNS) construction. Here a modification of the GNS construction is presented that applies even to nonat data, and then its sensitivity under perturbations is studied. The focus is on eigenvalue optimization for noncommutative polynomials, but we also explain how the main results pertain to commutative and tracial optimization. [ABSTRACT FROM AUTHOR]

In this paper we study feasibility and infeasibility of nonlinear two-stage fully adjustable robust feasibility problems with an empty first stage. This is equivalent to deciding whether the uncertainty set is contained within the projection of the feasible region onto the uncertainty-space. Moreover, the considered sets are assumed to be described by polynomials. For answering this question, two very general approaches using methods from polynomial optimization are presented--one for showing feasibility and one for showing infeasibility. The developed methods are approximated through sum of squares (SOS) polynomials and solved using semidefinite programs. Deciding robust feasibility and infeasibility is important for gas network operations, which is a nonconvex feasibility problem where the feasible set is described by a composition of polynomials with the absolute value function. Concerning the gas network problem, different topologies are considered. It is shown that a tree structured network can be decided exactly using linear programming. Furthermore, a method is presented to reduce a tree network with one additional arc to a single cycle network. In this case, the problem can be decided by eliminating the absolute value functions and solving the resulting linearly many polynomial optimization problems. Lastly, the effectivity of the methods is tested on a variety of small cyclic networks. It turns out that for instances where robust feasibility or infeasibility can be decided successfully, level 2 or level 3 of the Lasserre relaxation hierarchy typically is sufficient. [ABSTRACT FROM AUTHOR]

Consider a finite system of nonstrict real polynomial inequalities and suppose its solution set S ⊑ Rn is convex, has nonempty interior, and is compact. Suppose that the system satisfies the Archimedean condition, which is slightly stronger than the compactness of S. Suppose that each defining polynomial satisfies a second order strict quasiconcavity condition where it vanishes on S (which is very natural because of the convexity of S) or its Hessian has a certain matrix sums of squares certificate for negative-semidefiniteness on S (fulfilled trivially by linear polynomials). Then we show that the system possesses an exact Lasserre relaxation. In their seminal work of 2009, Helton and Nie showed under the same conditions that S is the projection of a spectrahedron, i.e., it has a semidefinite representation. The semidefinite representation used by Helton and Nie arises from glueing together Lasserre relaxations of many small pieces obtained in a nonconstructive way. By refining and varying their approach, we show that we can simply take a Lasserre relaxation of the original system itself. Such a result was provided by Helton and Nie with much more machinery only under very technical conditions and after changing the description of S. [ABSTRACT FROM AUTHOR]

We study sum of squares (SOS) relaxations to optimize polynomial functions over a set ⋒ Rn, where V is a complex algebraic variety. We propose a new methodology that, rather than relying on some algebraic description, represents V with a generic set of complex samples. This approach depends only on the geometry of V, avoiding representation issues such as multiplicity and choice of generators. It also takes advantage of the coordinate ring structure to reduce the size of the corresponding semidefinite program (SDP). In addition, the input can be given as a straight-line program. Our methods are particularly appealing for varieties that are easy to sample from but for which the defining equations are complicated, such as SO(n), Grassmannians, or rank k tensors. For arbitrary varieties, we can obtain the required samples by using the tools of numerical algebraic geometry. In this way we connect the areas of SOS optimization and numerical algebraic geometry. [ABSTRACT FROM AUTHOR]

In this article, we propose a geometric programming method in order to compute lower bounds for real polynomials. We provide new sufficient conditions for polynomials to be nonnegative as well as to have a sum of binomial squares representation. These criteria rely on the coefficients and the support of a polynomial and generalize all previous ones by Lasserre, Ghasemi, Marshall, Fidalgo, and Kovacec to polynomials with arbitrary simplex Newton polytopes. This generalization yields a geometric programming approach for computing lower bounds for polynomials that significantly extends the geometric programming method proposed by Ghasemi and Marshall. Furthermore, it shows that geometric programming is strongly related to nonnegativity certificates based on sums of nonnegative circuit polynomials, which were recently introduced by the authors. [ABSTRACT FROM AUTHOR]

A central question in optimization is to maximize (or minimize) a linear function over a given polytope P. To solve such a problem in practice one needs a concise description of the polytope P. In this paper we are interested in representations of P using the positive semidefinite cone: a positive semidefinite lift (PSD lift) of a polytope P is a representation of P as the projection of an affine slice of the positive semidefinite cone Sd+. Such a representation allows linear optimization problems over P to be written as semidefinite programs of size d. Such representations can be beneficial in practice when d is much smaller than the number of facets of the polytope P. In this paper we are concerned with so-called equivariant PSD lifts (also known as symmetric PSD lifts) which respect the symmetries of the polytope P. We present a representation-theoretic framework to study equivariant PSD lifts of a certain class of symmetric polytopes known as orbitopes. Ourmain result is a structure theorem where we show that any equivariant PSD lift of size d of an orbitope is of sum-of-squares type where the functions in the sum-of-squares decomposition come from an invariant subspace of dimension smaller than d3. We use this framework to study two well-known families of polytopes, namely the parity polytope and the cut polytope, and we prove exponential lower bounds for equivariant PSD lifts of these polytopes. [ABSTRACT FROM AUTHOR]

We show that if a polynomial f ∊ R[x1,...,xn] is nonnegative on a closed basic semialgebraic set X={x ∊ Rn:g1(x)≥0,...,gr(x)≥0}, where g1,...,gr ∊ R[x1,...,xn], then f can be approximated uniformly on compact sets by polynomials of the form σ0+φ(g1)g1+...+φ(gr)gr, where σ0 ∊ R[x1,...,xn] and φ ∊ R[t] are sums of squares of polynomials. In particular, if X is compact, and h(x):=R2-∣x∣2 is positive on X, then f=σ0+σ1h+φ(g1)g1+...+φ(gr)gr for some sums of squares σ0,σ1 ∊ R[x1,...,xn] and φ ∊ R[t], where ∣x∣2=x21+...+x2n. We apply a quantitative version of those results to semidefinite optimization methods. Let X be a convex closed semialgebraic subset of Rn and let f be a polynomial which is positive on X. We give necessary and sufficient conditions for the existence of an exponent N ∊ N such that (1+∣x∣2)N f(x) is a convex function on X. We apply this result to searching for lower critical points of polynomials on convex compact semialgebraic sets. [ABSTRACT FROM AUTHOR]

We study the optimization problem of minimizing f(x) subject to h(x) = 0, g(x) > 0 with f a polynomial and h, g two tuples of polynomials in x ∈ ℝn. Lasserre's hierarchy is a sequence of sum of squares relaxations for finding the global minimum fmin. Let K be the feasible set. We prove the following results: (i) If the real variety Vℝ (h) is finite, then Lasserre's hierarchy has finite convergence, no matter if the complex variety VC(h) is finite or not. This solves an open question in the survey by M. Laurent [IMA Vol. Math. Appl. 149, Springer, New York, 2009, pp. 157-270]. (ii) If K and Vℝ (H) have the same vanishing ideal, then the finite convergence of Lasserre's hierarchy is independent of the choice of defining polynomials for the real variety VR(h). (iii) If only K is finite, a refined version of Lasserre's hierarchy (using the preordering of g) has finite convergence. [ABSTRACT FROM AUTHOR]

We extend Nesterov's semidefinite programming characterization of squared functional systems, and Faybusovich's abstraction to bilinear symmetric maps, to cones of sum-of-squares elements in general abstract algebras. Using algebraic techniques such as isomorphism, linear isomorphism, tensor products, sums, and direct sums, we show that many concrete cones are in fact sum-of-squares cones with respect to some algebra and thus are representable by the cone of positive semidefinite matrices. We also consider nonnegativity with respect to a proper cone K and show that in some cases cones of K-nonnegative functions are either sum of squares or at least semidefinite representable. For example, we show that some well-known Chebyshev systems, when extended to Euclidean Jordan algebras, induce cones that are semidefinite representable. Finally we will discuss some concrete examples and applications, including minimum ellipsoid enclosing given space curves, minimization of eigenvalues of polynomial matrix pencils, approximation of functions by shape-constrained functions, and approximation of combinatorial optimization problems by polynomial programming. [ABSTRACT FROM AUTHOR]

Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials, via the definition of convexity, its first order characterization, and its second order characterization, are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming, whereas deciding convexity is NP-hard. If we denote the set of convex and sos-convex polynomials in n variables of degree d with ᴄ̃n,d and ... respectively, then our main contribution is to prove that ᴄ̃n,d = ... if and only if n = 1 or d = 2 or (n,d) = (2,4). We also present a complete characterization for forms (homogeneous polynomials) except for the case (n, d) = (3, 4), which is joint work with Blekherman and is to be published elsewhere. Our result states that the set Cn,d of convex forms in n variables of degree d equals the set ΣCn,d of sos-convex forms if and only if n = 2 or d = 2 or (n, d) = (3, 4). To prove these results, we present in particular explicit examples of polynomials in ᴄ̃2,6\... and ᴄ̃3,4\... and forms in C3,6\ΣC3,6 and C4,4\ΣC4,4, and a general procedure for constructing forms in Cn,d+2\ΣCn,d+2 from nonnegative but not sos forms in n variables and degree d. Although for disparate reasons, the remarkable outcome is that convex polynomials (resp., forms) are sos-convex exactly in cases where nonnegative polynomials (resp., forms) are sums of squares, as characterized by Hilbert. [ABSTRACT FROM AUTHOR]

We study how to solve semidefinite programming (SDP) relaxations for large-scale polynomial optimization. When interior-point methods are used. typically only small or moderately large problems could be solved. This paper studies regularization methods for solving polynomial optimization problems. We describe these methods for semidefinite optimization with block structures and then apply them to solve large-scale polynomial optimization problems. The performance is tested on various numerical examples. With regularization methods, significantly bigger problems could be solved on a regular computer, which is almost impossible with interior point methods. [ABSTRACT FROM AUTHOR]

In this paper we study constrained eigenvalue optimization of noncommutative (nc) polynomials, focusing on the polydisc and the ball. Our three main results are as follows: (1) an nc polynomial is nonnegative if and only if it admits a weighted sum of hermitian squares decomposition; (2) (eigenvalue) optima for nc polynomials can be computed using a single semidefinite program (SDP)--this sharply contrasts with the commutative case where sequences of SDPs are needed; (3) the dual solution to this "single" SDP can be exploited to extract eigenvalue optimizers with an algorithm based on two ingredients: solution to a truncated nc moment problem via flat extensions, and Gelfand-Naimark-Segal construction. The implementation of these procedures in our computer algebra system NCSOStools is presented, and several examples pertaining to matrix inequalities are given to illustrate our results. [ABSTRACT FROM AUTHOR]

This paper studies the so-called biquadratic optimization over unit spheres Minx∈ℝn,y∈ℝm ∑1≤i,k≤n, 1≤j,l≤m bijklxiyjxkyl, subject to ||x|| = 1, ||y|| = 1. We show that this problem is NP-hard, and there is no polynomial time algorithm returning a positive relative approximation bound. Then, we present various approximation methods based on semidefinite programming (SDP) relaxations. Our theoretical results are as follows: For general biquadratic forms, we develop a 1/2max{m,n}² -approximation algorithm under a slightly weaker approximation notion; for biquadratic forms that are square-free, we give a relative approximation bound 1/nm; when min/{n,m} is a constant, we present two polynomial time approximation schemes (PTASs) which are based on sum of squares (SOS) relaxation hierarchy and grid sampling of the standard simplex. For practical computational purposes, we propose the first order SOS relaxation, a convex quadratic SDP relaxation, and a simple minimum eigenvalue method and show their error bounds. Some illustrative numerical examples are also included. [ABSTRACT FROM AUTHOR]

A set S ⊆ ℝn is called semidefinite programming (SDP) representable or semidefinite representable if S equals the projection of a set in higher dimensional space which is describable by some linear matrix inequality (LMI). Clearly, if S is SDP representable, then S must be convex and semialgebraic (it is describable by conjunctions and disjunctions of polynomial equalities or inequalities). This paper proves sufficient conditions and necessary conditions for SDP representability of convex sets and convex hulls by proposing a new approach to constructing SDP representations. The contributions of this paper are: (i) For bounded SDP representable sets W1, . . .,Wm, we give an explicit construction of an SDP representation for conv(∪k=1mWk). This provides a technique for building global SDP representations from the local ones. (ii) For the SDP representability of a compact convex semialgebraic set S, we prove sufficient: the boundary ∂S is nonsingular and positively curved, while necessary is: ∂S has nonnegative curvature at each nonsingular point. In terms of defining polynomials for S, nonsingular boundary amounts to them having nonvanishing gradient at each point on ∂S and the curvature condition can be expressed as their strict versus nonstrict quasiconcavity at those points on ∂S where they vanish. The gaps between them are ∂S having or not having singular points either of the gradient or of the curvature's positivity. A sufficient condition bypassing the gaps is when some defining polynomials of S satisfy an algebraic condition called sosconcavity. (iii) For the SDP representability of the convex hull of a compact nonconvex semialgebraic set T, we find that the critical object is ∂cT, the maximum subset of ∂T contained in ∂conv(T). We prove sufficient for SDP representability: ∂cT is nonsingular and positively curved, and necessary is: ∂cT has nonnegative curvature at nonsingular points. The gaps between our sufficient and necessary conditions are similar to case (ii). The positive definite Lagrange Hessian (PDLH) condition, which meshes well with constructions, is also discussed. [ABSTRACT FROM AUTHOR]

We consider a polynomial programming problem P on a compact basic semialgebraic set K ⊂ ℝn, described by m polynomial inequalities gj (X) ≥ 0, and with criterion f ∈ ℝ [X]. We propose a hierarchy of semidefinite relaxations in the spirit of those of Waki et al. [SIAM J. Optim., 17 (2006), pp. 218-242]. In particular, the SDP-relaxation of order r has the following two features: (a) The number of variables is O(κ2r), where κ = max[κ1, κ2] with κ1 (resp., κ2) being the maximum number of variables appearing in the monomials of f (resp., appearing in a single constraint gj (X) ≥ 0). (b) The largest size of the linear matrix inequalities (LMIs) is O(κr). This is to compare with the respective number of variables O(n2r) and LMI size O(nr) in the original SDP-relaxations defined in [J. B. Lasserre, SIAM J. Optim., 11 (2001), pp. 796-817]. Therefore, great computational savings are expected in case of sparsity in the data {gj, f}, i.e., when κ is small, a frequent case in practical applications of interest. The novelty with respect to [H. Waki, S. Kim, M. Kojima, and M. Maramatsu, SIAM J. Optim., 17 (2006), pp. 218-242] is that we prove convergence to the global optimum of P when the sparsity pattern satisfies a condition often encountered in large size problems of practical applications, and known as the running intersection property in graph theory. In such cases, and as a by-product, we also obtain a new representation result for polynomials positive on a compact basic semialgebraic set, a sparse version of Putinar's Positivstellensatz [M. Putinar, Indiana Univ. Math. J., 42 (1993), pp. 969-984]. [ABSTRACT FROM AUTHOR]

We show that every real nonnegative polynomial $f$ can be approximated as closely as desired (in the $l_1$-norm of its coefficient vector) by a sequence of polynomials $\{f_\epsilon\}$ that are sums of squares. The novelty is that each $f_\epsilon$ has a simple and explicit form in terms of $f$ and $\epsilon$. [ABSTRACT FROM AUTHOR]

Wih every real polynomial $f$, we associate a family $\{f_{\epsilon r}\}_{\epsilon, r}$ of real polynomials, in explicit form in terms of $f$ and the parameters $\epsilon>0,r\in\N$, and such that $\Vert f-f_{\epsilon r}\Vert_1\to 0$ as $\epsilon\to 0$. Let $V\subset \R^n$ be a real algebraic set described by finitely many polynomials equations $g_j(x)=0,j\in J$, and let $f$ be a real polynomial, nonnegative on $V$. We show that for every $\epsilon>0$, there exist nonnegative scalars $\{\lambda_j(\epsilon)\}_{j\in J}$ such that, for all $r$ sufficiently large, \[f_{\epsilon r}+\sum_{j\in J} \lambda_j(\epsilon)\,g_j^2\quad\mbox{is a sum of squares.}\] This representation is an obvious certificate of nonnegativity of $f_{\epsilon r}$ on $V$, and very specific in terms of the $g_j$ that define the set $V$. In particular, it is valid with no assumption on $V$. In addition, this representation is also useful from a computation point of view, as we can define semidefinite programming relaxations to approximate the global minimum of $f$ on a real algebraic set $V$, or a semialgebraic set $\K$, and again, with no assumption on $V$ or $\K$. [ABSTRACT FROM AUTHOR]

A basic closed semialgebraic subset S of $\R^n$ is defined by simultaneous polynomial inequalities $g_1\ge 0,\dotsc,g_m\ge 0$. We give a short introduction to Lasserre's method for minimizing a polynomial f on a compact set S of this kind. It consists of successively solving tighter and tighter convex relaxations of this problem which can be formulated as semidefinite programs. We give a new short proof for the convergence of the optimal values of these relaxations to the infimum $f^\ast$ of f on S which is constructive and elementary. In the case where f possesses a unique minimizer $x^\ast$, we prove that every sequence of "nearly" optimal solutions of the successive relaxations gives rise to a sequence of points in $\R^n$ converging to $x^\ast$. [ABSTRACT FROM AUTHOR]