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 May 7, 2026
Positivstellensätze and Moment Problems with Universal Quantifiers
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
- Award ID(s):
- 2110780
- PAR ID:
- 10645611
- Publisher / Repository:
- informs
- Date Published:
- Journal Name:
- Mathematics of Operations Research
- ISSN:
- 0364-765X
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Local convergence analysis of the augmented Lagrangian method (ALM) is established for a large class of composite optimization problems with nonunique Lagrange multipliers under a second-order sufficient condition. We present a new second-order variational property called the semistability of second subderivatives and demonstrate that it is widely satisfied for numerous classes of functions, which is important for applications in constrained and composite optimization problems. Using the latter condition and a certain second-order sufficient condition, we are able to establish Q-linear convergence of the primal-dual sequence for an inexact version of the ALM for composite programs. Funding: Research of the first author is partially supported by Singapore National Academy of Science via SASEAF Programme under the grant RIE2025 NRF International Partnership Funding Initiative. Research of the second author is partially supported by the National Science Foundation under the grant DMS 2108546.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
-
A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the (k−1)-dimensional projective space over F_q that have size at most cqk for some universal constant c. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of F_q-linear minimal codes of length n and dimension k, for every prime power q, for which n ≤ cqk. This solves one of the main open problems on minimal codes.more » « less
-
Abstract Let $$K$$ be a real closed field with a nontrivial non-archimedean absolute value. We study a refined version of the tropicalization map, which we call real tropicalization map, that takes into account the signs on $$K$$. We study images of semialgebraic subsets of $K^n$ under this map from a general point of view. For a semialgebraic set $$S \subseteq K^n$$ we define a space $$S_r^{{\operatorname{an}}}$$ called the real analytification, which we show to be homeomorphic to the inverse limit of all real tropicalizations of $$S$$. We prove a real analogue of the tropical fundamental theorem and show that the tropicalization of any semialgebraic set is described by tropicalization of finitely many inequalities, which are valid on the semialgebraic set. We also study the topological properties of real analytification and tropicalization. If $$X$$ is an algebraic variety, we show that $$X_r^{{\operatorname{an}}}$$ can be canonically embedded into the real spectrum $$X_r$$ of $$X$$, and we study its relation with the Berkovich analytification of $$X$$.more » « less
