Search

This paper studies Nash equilibrium problems that are given by polynomial functions. We formulate efficient polynomial optimization problems for computing Nash equilibria. The Moment-sum-of-squares relaxations are used to solve them. Under generic assumptions, the method can find a Nash equilibrium, if there is one. Moreover, it can find all Nash equilibria if there are finitely many ones of them. The method can also detect nonexistence if there is no Nash equilibrium. Funding: J. Nie was supported by the National Science Foundation [Grant DMS-2110780]. [ABSTRACT FROM AUTHOR]

We study separable plus quadratic (SPQ) polynomials, that is, polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sums of squares, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative quadratic polynomial and (ii) a sum of squares. We establish that the answer to question (i) is positive for univariate plus quadratic polynomials and for convex SPQ polynomials but negative already for bivariate quartic SPQ polynomials. We use our decomposition result for convex SPQ polynomials to show that convex SPQ polynomial optimization problems can be solved by "small" semidefinite programs. For question (ii), we provide a complete characterization of the answer based on the degree and the number of variables of the SPQ polynomial. We also prove that testing nonnegativity of SPQ polynomials is NP-hard when the degree is at least four. We end by presenting applications of SPQ polynomials to upper bounding sparsity of solutions to linear programs, polynomial regression problems in statistics, and a generalization of Newton's method that incorporates separable higher order derivative information. Funding: This work was partially supported by an AFOSR MURI award, the Defense Advanced Research Projects Agency Young Faculty Award, the Princeton School of Engineering and Applied Sciences Innovation Award, the National Science Foundation Faculty Early Career Development Program Award, the Google Faculty Award, and the Sloan Fellowship. [ABSTRACT FROM AUTHOR]

De Klerk and Pasechnik introduced in 2002 semidefinite bounds ϑ (r) (G) (r ≥ 0) for the stability number α (G) of a graph G and conjectured their exactness at order r = α (G) − 1. These bounds rely on the conic approximations K n (r) introduced by Parrilo in 2000 for the copositive cone COP n . A difficulty in the convergence analysis of the bounds is the bad behavior of Parrilo's cones under adding a zero row/column: when applied to a matrix not in K n (r) this gives a matrix that does not lie in any of Parrilo's cones, thereby showing that their union is a strict subset of the copositive cone for any n ≥ 6. We investigate the graphs for which the bound of order r≤1 is exact: we algorithmically reduce testing exactness of ϑ (0) to acritical graphs, we characterize the critical graphs with ϑ (0) exact, and we exhibit graphs for which exactness of ϑ (1) is not preserved under adding an isolated node. This disproves a conjecture posed by Gvozdenović and Laurent in 2007, which, if true, would have implied the above conjecture by de Klerk and Pasechnik. Funding: This work is supported by the European Union's Framework Programme for Research and Innovation Horizon 2020 under the Marie Skłodowska-Curie Actions Grant Agreement Polynomial Optimization, Efficiency through Moments and Algebra [Grant 813211]. [ABSTRACT FROM AUTHOR]

In this paper, we establish an equivalence relation between partially symmetric tensors and homogeneous polynomials, prove that every partially symmetric tensor has a partially symmetric canonical polyadic (CP)-decomposition, and present three semidefinite relaxation algorithms. The first algorithm is used to check whether there exists a positive partially symmetric real CP-decomposition for a partially symmetric real tensor and give a decomposition if it has. The second algorithm is used to compute general partial symmetric real CP-decompositions. The third algorithm is used to compute positive partially symmetric complex CP-decomposition of partially symmetric complex tensors. Because for different parameters s , m i , n i , partially symmetric tensors T ∈ S [ m ] F [ n ] represent different kinds of tensors. Hence, the proposed algorithms can be used to compute different types of tensor real/complex CP-decomposition, including general nonsymmetric CP-decomposition, positive symmetric CP-decomposition, positive partially symmetric CP-decomposition, general partially symmetric CP-decomposition, etc. Numerical examples show that the algorithms are effective. [ABSTRACT FROM AUTHOR]

We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre, and a related hierarchy by de Klerk, Hess, and Laurent. For polynomial optimization over the hypercube, we show a refined convergence analysis for the first hierarchy. We also show lower bounds on the convergence rate for both hierarchies on a class of examples. These lower bounds match the upper bounds and thus establish the true rate of convergence on these examples. Interestingly, these convergence rates are determined by the distribution of extremal zeroes of certain families of orthogonal polynomials. [ABSTRACT FROM AUTHOR]

In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellensätze from the late 20th century (e.g., due to Stengle, Putinar, or Schmüdgen) that certify positivity of a polynomial on an arbitrary closed basic semialgebraic set. In this paper, we show that such hierarchies could in fact be designed from much more limited Positivstellensätze dating back to the early 20th century that only certify positivity of a polynomial globally. More precisely, we show that any inner approximation to the cone of positive homogeneous polynomials that is arbitrarily tight can be turned into a converging hierarchy of lower bounds for general polynomial minimization problems with compact feasible sets. This in particular leads to a semidefinite programming–based hierarchy that relies solely on Artin's solution to Hilbert's 17th problem. We also use a classical result from Pólya on global positivity of even forms to construct an "optimization-free" converging hierarchy for general polynomial minimization problems with compact feasible sets. This hierarchy requires only polynomial multiplication and checking nonnegativity of coefficients of certain fixed polynomials. As a corollary, we obtain new linear programming–based and second-order cone programming–based hierarchies for polynomial minimization problems that rely on the recently introduced concepts of diagonally dominant sum of squares and scaled diagonally dominant sum of squares polynomials. We remark that the scope of this paper is theoretical at this stage, as our hierarchies—though they involve at most two sum of squares constraints or only elementary arithmetic at each level—require the use of bisection and increase the number of variables (respectively, the degree) of the problem by the number of inequality constraints plus three (respectively, by a factor of two). [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre [Lasserre JB (2011) A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3):864–885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, this comparison yields a faster rate of convergence of the Lasserre hierarchy than what was previously known in the literature. [ABSTRACT FROM AUTHOR]

We provide a monotone nonincreasing sequence of upper bounds converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝ n. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864-885] is that only elementary computations are required. For optimization over the hypercube [0, 1] n, we show that the new bounds have a rate of convergence in . Moreover, we show a stronger convergence rate in O(1/ k) for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator k produces bounds with a rate of convergence in O(1/ k2), but at the cost of O( kn) function evaluations, while the new bound needs only O( nk) elementary calculations. [ABSTRACT FROM AUTHOR]

We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in a real vector space of dimension two. Previous work shows that optimizing a quadratic polynomial over the integer points in a polyhedral region in a real vector space of dimension two can be done in polynomial time, whereas optimizing a quartic polynomial in the same type of region is NP-hard. We close the gap by showing that this problem can be solved in polynomial time for cubic polynomials. Furthermore, we show that the problem of minimizing a homogeneous polynomial of any fixed degree over the integer points in a bounded polyhedron in a real vector space of dimension two is solvable in polynomial time. We show that this holds for polynomials that can be translated into homogeneous polynomials, even when the translation vector is unknown. We demonstrate that such problems in the unbounded case can have smallest optimal solutions of exponential size in the size of the input, thus requiring a compact representation of solutions for a general polynomial time algorithm for the unbounded case. [ABSTRACT FROM AUTHOR]

In this paper, we establish hardness and approximation results for various Lp-ball constrained homogeneous polynomial optimization problems, where p ∈ [2, ∞]. Specifically, we prove that for any given d ≥ 3 and p ∈ [2, ∞], both the problem of optimizing a degree-d homogeneous polynomial over the Lp-ball and the problem of optimizing a degree-d multilinear form (regardless of its super-symmetry) over Lp-balls are NP-hard. On the other hand, we show that these problems can be approximated to within a factor of Ω((log n)(d-2)/p/nd/2-1) in deterministic polynomial time, where n is the number of variables. We further show that with the help of randomization, the approximation guarantee can be improved to Ω((log n/n)d/2-1), which is independent of p and is currently the best for the aforementioned problems. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where p ∈ {2, ∞}. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems. [ABSTRACT FROM AUTHOR]

Random sampling is a simple but powerful method in statistics and in the design of randomized algorithms. In a typical application, random sampling can be applied to estimate an extreme value, say maximum, of a function f over a set S⊆R. To do so, one may select a simpler (even finite) subset S0 S, randomly take some samples over S0 for a number of times, and pick the best sample. The hope is to find a good approximate solution with reasonable chance. This paper sets out to present a number of scenarios for f , S and S0 where certain probability bounds can be established, leading to a quality assurance of the procedure. In our setting, f is a multivariate polynomial function. We prove that if f is a d-th order homogeneous polynomial in n variables and F is its corresponding super-symmetric tensor, and .i (i D 11 21 : : : 1 n) are i.i.d. Bernoulli random variables taking 1 or .1 with equal probability, then Prob8f 4.11 .21 : : : 1 .n5 .n.d=2.F .19 ., where .1 . > 0 are two universal constants and . .1 denotes the summation of the absolute values of all its entries. Several new inequalities concerning probabilities of the above nature are presented in this paper. Moreover, we show that the bounds are tight in most cases. Applications of our results in optimization are discussed as well. [ABSTRACT FROM AUTHOR]

In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semidefinite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization problems, show how the degree principle for the symmetric group can be computationally exploited, and also propose some methods to efficiently compute the geometric quotient. [ABSTRACT FROM AUTHOR]