An official website of the United States government
Abstract This paper studies the polynomial optimization problem whose feasible set is a union of several basic closed semialgebraic sets. We propose a unified hierarchy of Moment-SOS relaxations to solve it globally. Under some assumptions, we prove the asymptotic or finite convergence of the unified hierarchy. Special properties for the univariate case are discussed. The application for computing (p, q)-norms of matrices is also presented.
more »
« less
This content will become publicly available on September 1, 2026
Polynomial optimization relaxations for generalized semi-infinite programs
Abstract This paper studies generalized semi-infinite programs (GSIPs) given by polynomials. We propose a hierarchy of polynomial optimization relaxations to solve them. They are based on Lagrange multiplier expressions and polynomial extensions. Moment-SOS relaxations are applied to solve the polynomial optimization. The convergence of this hierarchy is shown under certain conditions. In particular, the classical semi-infinite programs can be solved as a special case of GSIPs. We also study GSIPs that have convex infinity constraints and show that they can be solved exactly by a single polynomial optimization relaxation. The computational efficiency is demonstrated by extensive numerical results.
more »
« less
- Award ID(s):
- 2110780
- PAR ID:
- 10645610
- Publisher / Repository:
- Springer Nature
- Date Published:
- Journal Name:
- Mathematical Programming Computation
- Volume:
- 17
- Issue:
- 3
- ISSN:
- 1867-2949
- Page Range / eLocation ID:
- 547 to 583
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract This paper studies the sparse Moment-SOS hierarchy of relaxations for solving sparse polynomial optimization problems. We show that this sparse hierarchy is tight if and only if the objective can be written as a sum of sparse nonnegative polynomials, each of which belongs to the sum of the ideal and quadratic module generated by the corresponding sparse constraints. Based on this characterization, we give several sufficient conditions for the sparse Moment-SOS hierarchy to be tight. In particular, we show that this sparse hierarchy is tight under some assumptions such as convexity, optimality conditions or finiteness of constraining sets.more » « less
-
This paper studies Positivstellensätze and moment problems for sets K that are given by universal quantifiers. Let Q be the closed set of universal quantifiers. Fix a finite nonnegative Borel measure whose support is Q and assume it satisfies the multivariate Carleman condition. First, we prove a Positivstellensatz with universal quantifiers: if a polynomial f is positive on K, then f belongs to the associated quadratic module, under the archimedeanness assumption. Second, we prove some necessary and sufficient conditions for a full (or truncated) multisequence to admit a representing measure supported in K. In particular, the classical flat extension theorem of Curto and Fialkow is generalized to truncated moment problems on such a set K. Third, we present applications of the above Positivstellensatz and moment problems in semi-infinite optimization, where feasible sets are given by infinitely many constraints with universal quantifiers. This results in a new hierarchy of Moment-SOS relaxations. Its convergence is shown under some usual assumptions. The quantifier set Q is allowed to be non-semialgebraic, which makes it possible to solve some optimization problems with non-semialgebraic constraints. Funding: X. Hu and J. Nie are partially supported by the NSF [Grant DMS-2110780]. I. Klep is supported by the Slovenian Research Agency program P1-0222 [also Grants J1-50002, J1-60011, J1-50001, J1-2453, N1-0217, and J1-3004] and was partially supported by the Marsden Fund Council of the Royal Society of New Zealand. I. Klep’s work was partly performed within the project COMPUTE, funded within the QuantERA II program that has received funding from the EU’s H2020 research and innovation program under the GA No 101017733.more » « less
-
The multi-objective optimization is to optimize several objective functions over a common feasible set. Because the objectives usually do not share a common optimizer, people often consider (weakly) Pareto points. This paper studies multi-objective optimization problems that are given by polynomial functions. First, we study the geometry for (weakly) Pareto values and represent Pareto front as the boundary of a convex set. Linear scalarization problems (LSPs) and Chebyshev scalarization problems (CSPs) are typical approaches for getting (weakly) Pareto points. For LSPs, we show how to use tight relaxations to solve them and how to detect existence or nonexistence of proper weights. For CSPs, we show how to solve them by moment relaxations. Moreover, we show how to check whether a given point is a (weakly) Pareto point or not and how to detect existence or nonexistence of (weakly) Pareto points. We also study how to detect unboundedness of polynomial optimization, which is used to detect nonexistence of proper weights or (weakly) Pareto points. Funding: J. Nie is partially supported by the National Science Foundation [Grant DMS-2110780].more » « less
-
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].more » « less
