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. A qualitative, network-centric method for modeling socio-technical systems, with applications to evaluating interventions on social media platforms to increase social equality

   https://doi.org/10.1007/s41109-022-00486-8  

   Joseph, Kenneth; Chen, Huei-Yen Winnie; Ionescu, Stefania; Du, Yuhao; Sankhe, Pranav; Hannak, Aniko; Rudra, Atri (July 2022, Applied Network Science)

   Abstract We propose and extend a qualitative, complex systems methodology from cognitive engineering, known as theabstraction hierarchy, to model how potential interventions that could be carried out by social media platforms might impact social equality. Social media platforms have come under considerable ire for their role in perpetuating social inequality. However, there is also significant evidence that platforms can play a role inreducingsocial inequality, e.g. through the promotion of social movements. Platforms’ role in producing or reducing social inequality is, moreover, not static; platforms can and often do take actions targeted at positive change. How can we develop tools to help us determine whether or not a potential platform change might actually work to increase social equality? Here, we present the abstraction hierarchy as a tool to help answer this question. Our primary contributions are two-fold. First, methodologically, we extend existing research on the abstraction hierarchy in cognitive engineering with principles from Network Science. Second, substantively, we illustrate the utility of this approach by using it to assess the potential effectiveness of a set of interventions, proposed in prior work, for how online dating websites can help mitigate social inequality. 

   more » « less