Search

This paper presents a method for calculating the Region of Attraction (ROA) of nonlinear dynamical systems, both with and without control. The ROA is determined by solving a hierarchy of semidefinite programs (SDPs) defined on a splitting of the time and state space. Previous works demonstrated that this splitting could significantly enhance approximation accuracy, although the improvement was highly dependent on the ad‐hoc selection of split locations. In this work, we eliminate the need for this ad‐hoc selection by introducing an optimization‐based method that performs the splits through conic differentiation of the underlying semidefinite programming problem. We provide the differentiability conditions for the split ROA problem, prove the absence of a duality gap, and demonstrate the effectiveness of our method through numerical examples. [ABSTRACT FROM AUTHOR]

We present a nonapproximate computational method for generating G$G$‐optimal designs in response surface methodology (RSM) settings using Gloptipoly, a global polynomial optimizer. Traditional approaches use a grid approximation for computing a candidate design's G$G$‐score. Gloptipoly can find the global optimum of high‐order polynomials thus making it suitable for computing a design's G$G$‐score, that is, its maximum scaled prediction variance, which, for second‐order models, is a quartic polynomial function of the experimental factors. We demonstrate the efficacy and performance of our method through comprehensive application to well‐published examples, and illustrate, for the first time, its application to generating G$G$‐optimal designs supporting models of order greater than 2. This work represents the first non‐approximate computational approach to solving the G$G$‐optimal design problem. This advancement opens new possibilities for finding G$G$‐optimal designs beyond second‐order RSM models. [ABSTRACT FROM AUTHOR]

In recent years, the interest in electric direct current (DC) technologies (such as converters, batteries, and electric vehicles) has increased due to their potential in energy efficiency and sustainability. However, the vast majority of electric systems and networks are based on alternating current (AC) as they also have certain advantages regarding cost-effective transport and robustness. In this paper, an AC/DC optimal power flow method for hybrid microgrids and several key performance indicators (KPIs) for its techno-economic assessment are presented. The combination of both calculations allows users to determine the viability of their hybrid microgrids. AC/DC networks have been modeled considering their most common elements. For the power flow method, polynomial optimization is formulated considering four different objective functions: the minimization of energy losses, voltage deviation, and operational costs and the maximization of the microgrid generation. The power flow method and the techno-economic analysis are implemented in Python and validated in the Centro de Desarrollo de Energias Renovables (CEDER) demonstrator for TIGON. The results show that the calculated power flow variables and those measured at CEDER are practically the same. In addition, the KPIs are obtained and compared for four operating scenarios: baseline, no battery, battery flexibility, and virtual battery (VB) flexibility. The last scenario results in the most profitable option. [ABSTRACT FROM AUTHOR]

We study the representation of nonnegative polynomials in two variables on a certain class of unbounded closed basic semi-algebraic sets (which are called generalized strips). This class includes the strip [ a , b ] × R which was studied by Marshall in (Proc Am Math Soc 138(5):1559–1567, 2010). A denominator-free Nichtnegativstellensätz holds true on a generalized strip when the width of the generalized strip is constant and fails otherwise. As a consequence, we confirm that the standard hierarchy of semidefinite programming relaxations defined for the compact case can indeed be adapted to the generalized strip with constant width. For polynomial optimization problems on the generalized strip with non-constant width, we follow Ha-Pham's work: Solving polynomial optimization problems via the truncated tangency variety and sums of squares. [ABSTRACT FROM AUTHOR]

Generically, a fully measured elasticity tensor has no material symmetry. For single crystals with a cubic lattice, or for the aeronautics turbine blades superalloys such as Nickel-based CMSX-4, cubic symmetry is nevertheless expected. It is in practice necessary to compute the nearest cubic elasticity tensor to a given raw one. Mathematically formulated, the problem consists in finding the distance between a given tensor and the cubic symmetry stratum. It has recently been proved that closed symmetry strata are affine algebraic sets (for any tensorial representation of the rotation group): they are defined by polynomial equations without requirement to polynomial inequalities. Such equations have furthermore been derived explicitly for the closed cubic elasticity stratum. We propose to make use of this mathematical property to formulate the distance to cubic symmetry problem as a polynomial (in fact quadratic) optimization problem, and to derive its quasi-analytical solution using the technique of Gröbner bases. The proposed methodology also applies to cubic Hill elasto-plasticity (where two fourth-order constitutive tensors are involved). [ABSTRACT FROM AUTHOR]

Abstract: The generalized Nash equilibrium problem (GNEP) is a kind of game to find strategies for a group of players such that each player’s objective function is optimized. Solutions for GNEPs are called generalized Nash equilibria (GNEs). In this paper, we propose a numerical method for finding GNEs of GNEPs of polynomials based on the polyhedral homotopy continuation and the Moment-SOS hierarchy of semidefinite relaxations. We show that our method can find all GNEs if they exist, or detect the nonexistence of GNEs, under some genericity assumptions. Some numerical experiments are made to demonstrate the efficiency of our method.

This paper proposes a novel Difference-of-Convex (DC) decomposition for polynomials using a power-sum representation, achieved by solving a sparse linear system. We introduce the Boosted DCA with Exact Line Search ( BDCA e ) for addressing linearly constrained polynomial programs within the DC framework. Notably, we demonstrate that the exact line search equates to determining the roots of a univariate polynomial in an interval, with coefficients being computed explicitly based on the power-sum DC decompositions. The subsequential convergence of BDCA e to critical points is proven, and its convergence rate under the Kurdyka–Łojasiewicz property is established. To efficiently tackle the convex subproblems, we integrate the Fast Dual Proximal Gradient method by exploiting the separable block structure of the power-sum DC decompositions. We validate our approach through numerical experiments on the Mean–Variance–Skewness–Kurtosis portfolio optimization model and box-constrained polynomial optimization problems. Comparative analysis of BDCA e against DCA, BDCA with Armijo line search, UDCA, and UBDCA with projective DC decomposition, alongside standard nonlinear optimization solvers FMINCON and FILTERSD, substantiates the efficiency of our proposed approach. [ABSTRACT FROM AUTHOR]

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]

In recent years, the interest in electric direct current (DC) technologies (such as converters, batteries, and electric vehicles) has increased due to their potential in energy efficiency and sustainability. However, the vast majority of electric systems and networks are based on alternating current (AC) as they also have certain advantages regarding cost-effective transport and robustness. In this paper, an AC/DC optimal power flow method for hybrid microgrids and several key performance indicators (KPIs) for its techno-economic assessment are presented. The combination of both calculations allows users to determine the viability of their hybrid microgrids. AC/DC networks have been modeled considering their most common elements. For the power flow method, polynomial optimization is formulated considering four different objective functions: the minimization of energy losses, voltage deviation, and operational costs and the maximization of the microgrid generation. The power flow method and the techno–economic analysis are implemented in Python and validated in the Centro de Desarrollo de Energías Renovables (CEDER) demonstrator for TIGON. The results show that the calculated power flow variables and those measured at CEDER are practically the same. In addition, the KPIs are obtained and compared for four operating scenarios: baseline, no battery, battery flexibility, and virtual battery (VB) flexibility. The last scenario results in the most profitable option.

Optimal control problems are prevalent in model-based control, state and parameter estimation, and experimental design for complex dynamical systems. An approach for obtaining solutions to these problems is based on the notion of parsimonious input parameterization and comprises two tasks: the enumeration of arc sequences followed by the computation of optimal values of a small number of decision variables for each sequence. This paper proposes an efficient global solution method for single-input optimal control problems for nonlinear dynamical systems with a potentially large number of states or complex dynamics via sum-of-squares polynomials and parallel computing. The method approximates the problem for a given arc sequence as a polynomial optimization problem that can be efficiently solved to global optimality via semidefinite programming. It is established that the difference between the cost obtained by the proposed method and the globally optimal cost of the original problem is bounded and depends on the polynomial approximation error. The method is illustrated by simulation examples of a reaction system and a rocket.

In this article, we are interested in developing polynomial decomposition techniques based on sums-of-squares (SOS), namely the difference-of-sums-of-squares (D-SOS) and the difference-of-convex-sums-of-squares (DC-SOS). In particular, the DC-SOS decomposition is very useful for dilference-of-convex (DC) programming formulation of polynomial optimization problems. First, we introduce the cone of convex-sums-of-squares (CSOS) polynomials and discuss its relationship to the sums-of-squares (SOS) polynomials, the non-negative polynomials, and the SOS-convex polynomials. Then we propose the set of D-SOS and DC-SOS polynomials and prove that any polynomial can be formulated as D-SOS and DC-SOS. The problem of finding D-SOS and DC-SOS decompositions can be formulated as a semi-definite program and solved for any desired precision in polynomial time using interior point methods. Some algebraic properties of CSOS, D-SOS, and DC- SOS are established. Second, we focus on establishing several practical algorithms for exact D-SOS and DC-SOS polynomial decompositions without solving any SDP. The numerical performance of the proposed D-SOS and DC-SOS decomposition algorithms and their parallel versions, tested on a dataset of 1750 randomly generated polynomials, is reported. [ABSTRACT FROM AUTHOR]

A nonnegativity certificate (NNC) is a way to write a polynomial so that its nonnegativity on a Semialgebraic set becomes evident. Positivstellensatze (Psatze) guarantee the existence of NNCs. Both NNCs and Psatze underlie powerful algorithmic techniques for optimization. This paper proposes a universal approach to derive new Psatze for general Semialgebraic sets from ones developed for simpler sets, such as a box, a simplex, or the nonnegative orthant. We provide several results illustrating the approach. First, by considering Handelman's Positivstellensatz (Psatz) over a box, we construct non-SOS Schmüdgen-type Psatze over any compact Semialgebraic set, that is, a family of Psatze that follow the structure of the fundamental Schmiidgen's Psatz but where instead of SOS polynomials, any class of polynomials containing the nonnegative constants can be used, such as SONC, DSOS/SDSOS, hyperbolic, or sums of AM/GM polynomials. Second, by considering the simplex as the simple set, we derive a sparse Psatz over general compact sets which does not rely on any structural assumptions of the set. Finally, by considering Polya's Psatz over the nonnegative orthant, we derive a new non-SOS Psatz over unbounded sets which satisfy some generic conditions. All these results contribute to the literature regarding the use of non-SOS polynomials and sparse NNCs to derive Psatze over compact and unbounded sets. Throughout the article, we illustrate our results with relevant examples and numerical experiments. [ABSTRACT FROM AUTHOR]

This work addresses the occupation measure relaxation of calculus of variations problems, which is an infinite-dimensional linear programming reformulation amenable to numerical approximation by a hierarchy of semidefinite optimization problems. We address the problem of equivalence of this relaxation to the original problem. Our main result provides sufficient conditions for this equivalence. These conditions, revolving around the convexity of the data, are simple and apply in very general settings that may be of arbitrary dimensions and may include pointwise and integral constraints, thereby considerably strengthening the existing results. Our conditions are also extended to optimal control problems. In addition, we demonstrate how these results can be applied in nonconvex settings, showing that the occupation measure relaxation is at least as strong as the convexification using the convex envelope; in doing so, we prove that a certain weakening of the occupation measure relaxation is equivalent to the convex envelope. This opens the way to application of the occupation measure relaxation in situations where the convex envelope relaxation is known to be equivalent to the original problem, which includes problems in magnetism and elasticity. [ABSTRACT FROM AUTHOR]

We study optimal simple second-order cone representations (a particular subclass of second-order cone representations) for weighted geometric means, which turns out to be closely related to minimum mediated sets. Several lower bounds and upper bounds on the size of optimal simple second-order cone representations are proved. In the case of bivariate weighted geometric means (equivalently, one-dimensional mediated sets), we are able to prove the exact size of an optimal simple second-order cone representation and give an algorithm to compute one. In the genenal case, fast heuristic algorithms and traversal algorithms are proposed to compute an approximately optimal simple second-order cone representation. Finally, applications to polynomial optimization, matrix optimization, and quantum information are provided. [ABSTRACT FROM AUTHOR]

In this paper, we focus on a class of robust vector polynomial optimization problems (RVPOP in short) without any convex assumptions. By combining/improving the utopia point method (a nonlinear scalarization) for vector optimization and "joint+marginal" relaxation method for polynomial optimization, we solve the RVPOP successfully. Both theoratical and computational aspects are considered. [ABSTRACT FROM AUTHOR]

In this paper, we proposed an approach for computing the Hausdorff distance between convex semialgebraic sets. We exploit the KKT conditions to rewrite the Hausdorff distance as polynomial maximization problems under some assumptions, in which polynomial and rational expressions of Lagrange multipliers are used. Then, polynomial maximization problems are solved by Lasserre's hierarchy of semi-definite relaxations. Finally, some numerical examples are reported. [ABSTRACT FROM AUTHOR]

Vision-based algorithms are widely applied to micro-air vehicles (MAVs) because of their limited takeoff weight. Conventional stereo camera requires a large baseline for long-distance detection, which is difficult for MAVs. The rapidly developing, learning-based, monocular depth estimation method can handle these problems and succeed remarkably well in providing acceptable depth in indoor (maximum distance: 10 m) and outdoor (maximum distance: 80 m) environments. For the safety of an MAV in outdoor environments, we, therefore, propose a monocular-camera-based dynamic avoidance system, along with obstacle motion estimation by depth estimation methods using the Kalman filter. To handle the position uncertainty of a dynamic obstacle and predict its future movement, a polynomial-fitting-based trajectory prediction method with a defined uncertainty range has been used. Subsequently, using quadratic programming (QP), a safe, corridor-based, spatiotemporal trajectory generation method is proposed to ensure the safety of the MAV. We validate the performance of our algorithm through simulation and real-world experiments using an MAV.

The use of approximate solution techniques for the Chemical Master Equation is a common practice for the analysis of stochastic chemical systems. Despite their widespread use, however, many such techniques rely on unverifiable assumptions and only a few provide mechanisms to control the approximation error quantitatively. Addressing this gap, Dowdy and Barton (J Chem Phys 149(7):074103, 2018) proposed an optimization-based technique for the computation of guaranteed bounds on the moment trajectories associated with stochastic chemical systems, thereby providing a general framework for rigorous uncertainty quantification. Here, we present an extension of this method. The key contribution is a new hierarchy of convex necessary moment conditions that build upon partitioning of the time domain. These conditions reflect the temporal causality that is inherent to the moment trajectories associated with stochastic processes described by the Chemical Master Equation and can be strengthened by simple refinement of the time domain partition. Analogous to the original method, these conditions generate a hierarchy of semidefinite programs that furnishes monotonically improving bounds on the trajectories of the moments and related statistics of stochastic chemical systems. Compared to its predecessor, the presented hierarchy produces bounds that are at least as tight and features new bound tightening mechanisms such as refinement of the time domain partition which often enable the computation of dramatically tighter bounds with lower computational cost. We analyze the properties of the presented hierarchy, discuss some aspects of its practical implementation and demonstrate its merits with several examples. [ABSTRACT FROM AUTHOR]

We study properties of the convex hull of a set S described by quadratic inequalities. A simple way of generating inequalities valid on S is to take a nonnegative linear combinations of the defining inequalities of S. We call such inequalities aggregations. Special aggregations naturally contain the convex hull of S, and we give sufficient conditions for such aggregations to define the convex hull. We introduce the notion of hidden hyperplane convexity (HHC), which is related to the classical notion of hidden convexity of quadratic maps. We show that if the quadratic map associated with S satisfies HHC, then the convex hull of S is defined by special aggregations. To the best of our knowledge, this result generalizes all known results regarding aggregations defining convex hulls. Using this sufficient condition, we are able to recognize previously unknown classes of sets where aggregations lead to convex hull. We show that the condition known as positive definite linear combination together with hidden hyerplane convexity is a sufficient condition for finitely many aggregations to define the convex hull. All the above results are for sets defined using open quadratic inequalities. For closed quadratic inequalities, we prove a new result regarding aggregations giving the convex hull, without topological assumptions on S. [ABSTRACT FROM AUTHOR]

In this paper, we consider polynomial optimization with correlative sparsity. We construct correlatively sparse Lagrange multiplier expressions (CS-LMEs) and propose CS-LME reformulations for polynomial optimization problems using the Karush-Kuhn-Tucker optimality conditions. Correlatively sparse sum-of-squares (CS-SOS) relaxations are applied to solve the CS-LME reformulation. We show that the CS-LME reformulation inherits the original correlative sparsity pattern, and the CS-SOS relaxation provides sharper lower bounds when applied to the CS-LME reformulation, compared with when it is applied to the original problem. Moreover, the convergence of our approach is guaranteed under mild conditions. In numerical experiments, our new approach usually finds the global optimal value (up to a negligible error) with a low relaxation order for cases where directly solving the problem fails to get an accurate approximation. Also, by properly exploiting the correlative sparsity, our CS-LME approach requires less computational time than the original LME approach to reach the same accuracy level. [ABSTRACT FROM AUTHOR]

We introduce novel polyhedral approximation hierarchies for the cone of nonnegative forms on the unit sphere in Rn and for its (dual) cone of moments. We prove computable quantitative bounds on the speed of convergence of such hierarchies. We also introduce a novel optimization-free algorithm for building converging sequences of lower bounds for polynomial minimization problems on spheres. Finally, some computational results are discussed, showcasing our implementation of these hierarchies in the programming language Julia. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of fractional semi-infinite polynomial programming problems involving sos-convex polynomial functions. For such a problem, by a conic reformulation proposed in our previous work and the quadratic modules associated with the index set, a hierarchy of semidefinite programming (SDP) relaxations can be constructed and convergent upper bounds of the optimum can be obtained. In this paper, by introducing Lasserre's measure-based representation of nonnegative polynomials on the index set to the conic reformulation, we present a new SDP relaxation method for the considered problem. This method enables us to compute convergent lower bounds of the optimum and extract approximate minimizers. Moreover, for a set defined by infinitely many sos-convex polynomial inequalities, we obtain a procedure to construct a convergent sequence of outer approximations which have semidefinite representations (SDr). The convergence rate of the lower bounds and outer SDr approximations are also discussed. [ABSTRACT FROM AUTHOR]

Weight optimization of frame structures with continuous cross-section parametrization is a challenging non-convex problem that has traditionally been solved by local optimization techniques. Here, we exploit its inherent semi-algebraic structure and adopt the Lasserre hierarchy of relaxations to compute the global minimizers. While this hierarchy generates a natural sequence of lower bounds, we show, under mild assumptions, how to project the relaxed solutions onto the feasible set of the original problem and thus construct feasible upper bounds. Based on these bounds, we develop a simple sufficient condition of global ε -optimality. Finally, we prove that the optimality gap converges to zero in the limit if the set of global minimizers is convex. We demonstrate these results by means of two academic illustrations. [ABSTRACT FROM AUTHOR]

We show that (1) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (2) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods for minimizing the largest eigenvalue of a matrix pencil. Convergence to the optimal value of the semidefinite relaxation is guaranteed. As a result we obtain a hierarchy of nonsmooth "spectral relaxations" of the initial POP. Efficiency and robustness of this spectral hierarchy is tested against several equality constrained POPs on a sphere as well as on a sample of randomly generated quadratically constrained quadratic problems. [ABSTRACT FROM AUTHOR]

We consider cones of real forms which are sums of squares and invariant under a (finite) reflection group. Using the representation theory of these groups we are able to use the symmetry inherent in these cones to give more efficient descriptions. We focus especially on the A n , B n , and D n case where we use so-called higher Specht polynomials to give a uniform description of these cones. These descriptions allow us, to deduce that the description of the cones of sums of squares of fixed degree 2 d stabilizes with n > 2 d. Furthermore, in cases of small degree, we are able to analyze these cones more explicitly and compare them to the cones of non-negative forms. [ABSTRACT FROM AUTHOR]

C-eigenvalues of piezoelectric-type tensors play an important role in piezoelectric effect and converse piezoelectric effect. While the largest C-eigenvalue of a given piezoelectric-type tensor has concrete physical meaning which determines the highest piezoelectric coupling constant. In this paper, we focus on computing the maximum C-eigenvalue of piezoelectric-type tensors which is a third degree polynomial problem. To do that, we first establish the equivalence between the proposed polynomial optimization problem (POP) and a multi-linear optimization problem (MOP) under conditions that the original objective function is concave. Then, an augmented POP (which can also be regarded as a regularized POP) is introduced for the purpose to guarantee the concavity of the underlying objective function. Theoretically, both the augmented POP and the original problem share the same optimal solutions when the compact sets are specified as unit spheres. By exploiting the multi-block structure of the resulting MOP, we accordingly propose a proximal alternating minimization algorithm to get an approximate optimal value of the maximum C-eigenvalue. Furthermore, convergence of the proposed algorithm is established under mild conditions. Finally, some preliminary computational results on synthetic data sets are reported to show the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider the tensor absolute value equations (TAVEs). When one tensor is row diagonal with odd order, we show that the TAVEs can be reduced to an algebraic equation; when it is row diagonal and nonsingular with even order, we prove that the TAVEs is equivalent to a polynomial complementary problem. When no tensor is row diagonal, we formulate the TAVEs equivalently as polynomial optimization problems in two different ways. Each of them can be solved by Lasserre's hierarchy of semideflnite relaxations. The finite convergence properties are also discussed. Numerical experiments show the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

The use of machine learning techniques to improve the performance of branch-and-bound optimization algorithms is a very active area in the context of mixed integer linear problems, but little has been done for nonlinear optimization. To bridge this gap, we develop a learning framework for spatial branching and show its efficacy in the context of the Reformulation-Linearization Technique for polynomial optimization problems. The proposed learning is performed offline, based on instance-specific features and with no computational overhead when solving new instances. Novel graph-based features are introduced, which turn out to play an important role for the learning. Experiments on different benchmark instances from the literature show that the learning-based branching rule significantly outperforms the standard rules. History: Accepted by Andrea Lodi, Area Editor/Design & Analysis of Algorithms – Discrete. Funding: This work was supported by Ivey Business School (David G. Burgoyne Faculty Fellowship); FEDER [MTM2014-60191-JIN]; Spanish Ministry of Education [FPU Grant 17/02643, FPU Grant 20/01555]; Conselleria de Cultura, Educacion e Universidade [ED431C 2021/24]; Natural Sciences and Engineering Research Council of Canada [Discovery Grant 2017-04185]; Spanish Ministry of Science and Technology [MTM2017-87197-C3] and Spanish Ministry of Science and Innovation [PID2021-124030NB-C32]. [ABSTRACT FROM AUTHOR]

We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone of our framework. We then accelerate iPGM by taking long, but safeguarded, rank-one steps generated by fast nonlinear programming algorithms. We prove that the new framework is still globally convergent for solving the SDP. To solve the iPGM subproblem of projecting a given point onto the feasible set of the SDP, we design a two-phase algorithm with phase one using a symmetric Gauss–Seidel based accelerated proximal gradient method (sGS-APG) to generate a good initial point, and phase two using a modified limited-memory BFGS (L-BFGS) method to obtain an accurate solution. We analyze the convergence for both phases and establish a novel global convergence result for the modified L-BFGS that does not require the objective function to be twice continuously differentiable. We conduct numerical experiments for solving second-order SDP relaxations arising from a diverse set of POPs. Our framework demonstrates state-of-the-art efficiency, scalability, and robustness in solving degenerate SDPs to high accuracy, even in the presence of millions of equality constraints. [ABSTRACT FROM AUTHOR]

A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints from the second order Lasserre hierarchy. We explore a variety of approaches for adding a subset of the positive semidefinite constraints of the second order sparse relaxation obtained by using the maximum cliques of the graph's chordal extension. We apply this idea to sparse graphs of different sizes and densities, and provide evidence of its strengths and limitations when compared to the state-of-the-art Max-Cut solver BiqCrunch and the alternative sparse relaxation CS-TSSOS. [ABSTRACT FROM AUTHOR]

Screened Poisson Surface Reconstruction creates 2D surfaces from sets of oriented points in 3D (and can be extended to co‐dimension one surfaces in arbitrary dimensions). In this work we generalize the technique to manifolds of co‐dimension larger than one. The reconstruction problem consists of finding a vector‐valued function whose zero set approximates the input points. We argue that the right extension of screened Poisson Surface Reconstruction is based on exterior products: the orientation of the point samples is encoded as the exterior product of the local normal frame. The goal is to find a set of scalar functions such that the exterior product of their gradients matches the exterior products prescribed by the input points. We show that this setup reduces to the standard formulation for co‐dimension 1, and leads to more challenging multi‐quadratic optimization problems in higher co‐dimension. We explicitly treat the case of co‐dimension 2, i.e., curves in 3D and 2D surfaces in 4D. We show that the resulting bi‐quadratic problem can be relaxed to a set of quadratic problems in two variables and that the solution can be made effective and efficient by leveraging a hierarchical approach. [ABSTRACT FROM AUTHOR]

In this paper, we provide a new scheme for approximating the weakly efficient solution set for a class of vector optimization problems with rational objectives over a feasible set defined by finitely many polynomial inequalities. More precisely, we present a procedure to obtain a sequence of explicit approximations of the weakly efficient solution set of the problem in question. Each approximation is the intersection of the sublevel set of a single polynomial and the feasible set. To this end, we make use of the achievement function associated with the considered problem and construct polynomial approximations of it over the feasible set from above. Remarkably, the construction can be converted to semidefinite programming problems. Several nontrivial examples are designed to illustrate the proposed new scheme. [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]

The matrix spectral norm and nuclear norm appear in enormous applications. The generalization of these norms to higher-order tensors is becoming increasingly important, but unfortunately they are NP-hard to compute or even approximate. Although the two norms are dual to each other, the best-known approximation bound achieved by polynomial-time algorithms for the tensor nuclear norm is worse than that for the tensor spectral norm. In this paper, we bridge this gap by proposing deterministic algorithms with the best bound for both tensor norms. Our methods not only improve the approximation bound for the nuclear norm but also are data independent and easily implementable compared to existing approximation methods for the tensor spectral norm. The main idea is to construct a selection of unit vectors that can approximately represent the unit sphere, in other words, a collection of spherical caps to cover the sphere. For this purpose, we explicitly construct several collections of spherical caps for sphere covering with adjustable parameters for different levels of approximations and cardinalities. These readily available constructions are of independent interest, as they provide a powerful tool for various decision-making problems on spheres and related problems. We believe the ideas of constructions and the applications to approximate tensor norms can be useful to tackle optimization problems over other sets, such as the binary hypercube. [ABSTRACT FROM AUTHOR]

We consider the unconstrained optimization of multivariate trigonometric polynomials by the sum-of-squares hierarchy of lower bounds. We first show a convergence rate of O(1/s²) for the relaxation with degree s without any assumption on the trigonometric polynomial to minimize. Second, when the polynomial has a finite number of global minimizers with invertible Hessians at these minimizers, we show an exponential convergence rate with explicit constants. Our results also apply to minimizing regular multivariate polynomials on the hypercube. [ABSTRACT FROM AUTHOR]

One of the most-extensively studied problems in three-dimensional Computer Vision is "Perspective-n-Point" (PnP), which concerns estimating the pose of a calibrated camera, given a set of 3D points in the world and their corresponding 2D projections in an image captured by the camera. One solution method that ranks as very accurate and robust proceeds by reducing PnP to the minimization of a fourth-degree polynomial over the three-dimensional sphere S 3 . Despite a great deal of effort, there is no known fast method to obtain this goal. A very common approach is solving a convex relaxation of the problem, using "Sum Of Squares" (SOS) techniques. We offer two contributions in this paper: a faster (by a factor of roughly 10) solution with respect to the state-of-the-art, which relies on the polynomial's homogeneity; and a fast, guaranteed, easily parallelizable approximation, which makes use of a famous result of Hilbert. [ABSTRACT FROM AUTHOR]

This paper considers polynomial optimization with unbounded sets. We give a homogenization formulation and propose a hierarchy of Moment-SOS relaxations to solve it. Under the assumptions that the feasible set is closed at infinity and the ideal of homogenized equality constraining polynomials is real radical, we show that this hierarchy of Moment-SOS relaxations has finite convergence, if some optimality conditions (i.e., the linear independence constraint qualification, strict complementarity and second order sufficient conditions) hold at every minimizer, including the one at infinity. Moreover, we prove extended versions of Putinar-Vasilescu type Positivstellensatz for polynomials that are nonnegative on unbounded sets. The classical Moment-SOS hierarchy with denominators is also studied. In particular, we give a positive answer to a conjecture of Mai, Lasserre and Magron in their recent work. [ABSTRACT FROM AUTHOR]

Polynomial nonnegativity constraints can often be handled using the sum of squares condition. This can be efficiently enforced using semidefinite programming formulations, or as more recently proposed by Papp and Yildiz (Papp D in SIAM J O 29: 822–851, 2019), using the sum of squares cone directly in an interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and ℓ 1 -norm cones) can also be modeled through structured sum of squares programs. We take a different approach and propose using more specialized cones instead. This can result in lower dimensional formulations, more efficient oracles for interior point methods, or self-concordant barriers with smaller parameters. [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]

We present a method for finding lower bounds on the global infima of integral variational problems, wherein ∫Ωf(x,u(x),∇u(x))dx is minimized over functions u:Ω⊂Rn → Rm satisfying given equality or inequality constraints. Each constraint may be imposed over Ω or its boundary, either pointwise or in an integral sense. These global minimizations are generally nonconvex and intractable. We formulate a particular convex maximization, here called the pointwise dual relaxation (PDR), whose supremum is a lower bound on the infimum of the original problem. The PDR can be derived by dualizing and relaxing the original problem; its constraints are pointwise equalities or inequalities over finite-dimensional sets rather than over infinite-dimensional function spaces. When the original minimization can be specified by polynomial functions of (x,u,∇u), the PDR can be further relaxed by replacing pointwise inequalities with polynomial sum-of-squares (SOS) conditions. The resulting SOS program is computationally tractable when the dimensions m,n and the number of constraints are not too large. The framework presented here generalizes an approach of Valmorbida, Ahmadi, and Papachristodoulou [IEEE Trans. Automat. Control, 61 (2016), pp. 1649-1654]. We prove that the optimal lower bound given by the PDR is sharp for several classes of problems, whose special cases include leading eigenvalues of Sturm-Liouville problems and optimal constants of Poincaré inequalities. For these same classes, we prove that SOS relaxations of the PDR converge to the sharp lower bound as polynomial degrees are increased. Convergence of SOS computations in practice is illustrated for several examples. [ABSTRACT FROM AUTHOR]

This paper studies convex generalized Nash equilibrium problems that are given by polynomials. We use rational and parametric expressions for Lagrange multipliers to formulate efficient polynomial optimization for computing generalized Nash equilibria (GNEs). The Moment-SOS hierarchy of semidefinite relaxations are used to solve the polynomial optimization. Under some general assumptions, we prove the method can find a GNE if there exists one, or detect nonexistence of GNEs. Numerical experiments are presented to show the efficiency of the method. [ABSTRACT FROM AUTHOR]

The second-order cone (SOC) is a class of simple convex cones and optimizing over them can be done more efficiently than with semidefinite programming. It is interesting both in theory and in practice to investigate which convex cones admit a representation using SOCs, given that they have a strong expressive ability. In this paper, we prove constructively that the cone of sums of nonnegative circuits (SONC) admits a SOC representation. Based on this, we give a new algorithm for unconstrained polynomial optimization via SOC programming. We also provide a hybrid numeric-symbolic scheme which combines the numerical procedure with a rounding-projection algorithm to obtain exact nonnegativity certificates. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with fairly large degree and number of variables. [ABSTRACT FROM AUTHOR]