More Like this

1. Polynomial Optimization Over Unions of Sets

   https://doi.org/10.1007/s10013-024-00700-3  

   Nie, Jiawang; Zhang, Linghao (July 2024, Vietnam Journal of Mathematics)

   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
2. Ehrhart theory of paving and panhandle matroids

   https://doi.org/10.1515/advgeom-2023-0020  

   Hanely, Derek; Martin, Jeremy L.; McGinnis, Daniel; Miyata, Dane; Nasr, George D.; Vindas-Meléndez, Andrés R.; Yin, Mei (October 2023, Advances in Geometry)

   Abstract We show that the base polytopeP_Mof any paving matroidMcan be systematically obtained from a hypersimplex by slicing off certain subpolytopes, namely base polytopes of lattice path matroids corresponding to panhandle-shaped Ferrers diagrams. We calculate the Ehrhart polynomials of these matroids and consequently write down the Ehrhart polynomial ofP_M, starting with Katzman’s formula for the Ehrhart polynomial of a hypersimplex. The method builds on and generalizes Ferroni’s work on sparse paving matroids. Combinatorially, our construction corresponds to constructing a uniform matroid from a paving matroid by iterating the operation ofstressed-hyperplane relaxationintroduced by Ferroni, Nasr and Vecchi, which generalizes the standard matroid-theoretic notion of circuit-hyperplane relaxation. We present evidence that panhandle matroids are Ehrhart positive and describe a conjectured combinatorial formula involving chain forests and Eulerian numbers from which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that they depend only on their design-theoretic parameters: for example, while projective planes of the same order need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent. 

   more » « less
3. Verifying Global Optimality of Candidate Solutions to Polynomial Optimization Problems using a Determinant Relaxation Hierarchy

   https://doi.org/10.1109/CDC45484.2021.9683608  

   Xu, Sikun; Ma, Ruoyi; Molzahn, Daniel K.; Hijazi, Hassan L.; Josz, Cedric (December 2021, 60th IEEE Conference on Decision and Control (CDC))

   We propose an approach for verifying that a given feasible point for a polynomial optimization problem is globally optimal. The approach relies on the Lasserre hierarchy and the result of Lasserre regarding the importance of the convexity of the feasible set as opposed to that of the individual constraints. By focusing solely on certifying global optimality and relaxing the Lasserre hierarchy using necessary conditions for positive semidefiniteness based on matrix determinants, the proposed method is implementable as a computationally tractable linear program. We demonstrate this method via application to the optimal power flow problem used to operate electric power systems. 

   more » « less
4. A characterization for tightness of the sparse Moment-SOS hierarchy

   https://doi.org/10.1007/s10107-025-02223-2  

   Nie, Jiawang; Qu, Zheng; Tang, Xindong; Zhang, Linghao (May 2025, Mathematical Programming)

   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
5. Breaking the Mold: Nonlinear Ranking Function Synthesis Without Templates

   https://doi.org/10.1007/978-3-031-65627-9_21  

   Zhu, Shaowei; Kincaid, Zachary (January 2024, Springer Nature Switzerland)

   Abstract This paper studies the problem of synthesizing (lexicographic) polynomial ranking functions for loops that can be described in polynomial arithmetic over integers and reals. While the analogous ranking function synthesis problem forlineararithmetic is decidable, even checking whether agivenfunction ranks an integer loop is undecidable in the nonlinear setting. We side-step the decidability barrier by working within the theory of linear integer/real rings (LIRR) rather than the standard model of arithmetic. We develop a termination analysis that is guaranteed to succeed if a loop (expressed as a formula) admits a (lexicographic) polynomial ranking function. In contrast to template-based ranking function synthesis inrealarithmetic, our completeness result holds for lexicographic ranking functions of unbounded dimension and degree, and effectively subsumes linear lexicographic ranking function synthesis for linearintegerloops. 

   more » « less