Algebraic degree of polynomial optimization
From MaRDI portal
Abstract: Consider the polynomial optimization problem whose objective and constraints are all described by multivariate polynomials. Under some genericity assumptions, %% on these polynomials, we prove that the optimality conditions always hold on optimizers, and the coordinates of optimizers are algebraic functions of the coefficients of the input polynomials. We also give a general formula for the algebraic degree of the optimal coordinates. The derivation of the algebraic degree is equivalent to counting the number of all complex critical points. As special cases, we obtain the algebraic degrees of quadratically constrained quadratic programming (QCQP), second order cone programming (SOCP) and -th order cone programming (pOCP), in analogy to the algebraic degree of semidefinite programming.
Recommendations
Cited in
(43)- Tensor eigenvalue complementarity problems
- Multi-objective convex polynomial optimization and semidefinite programming relaxations
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- Computing critical points for invariant algebraic systems
- Gröbner bases and critical values: the asymptotic combinatorics of determinantal systems
- Certifying the global optimality of quartic minimization over the sphere
- The saddle point problem of polynomials
- The geometry of SDP-exactness in quadratic optimization
- Solving determinantal systems using homotopy techniques
- On types of degenerate critical points of real polynomial functions
- On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems
- Saddle points of rational functions
- Certifying convergence of Lasserre's hierarchy via flat truncation
- The CP-matrix approximation problem
- Algebraic degree in semidefinite and polynomial optimization
- Genericity in polynomial optimization
- Computing the distance between the linear matrix pencil and the completely positive cone
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Critical points via monodromy and local methods
- Algebraic optimization degree
- An improved semidefinite programming hierarchy for testing entanglement
- The Maximum Likelihood Degree of Sparse Polynomial Systems
- Algebraic optimization of sequential decision problems
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- Optimality conditions for homogeneous polynomial optimization on the unit sphere
- Gaussian Likelihood Geometry of Projective Varieties
- Nonlinear algebra and applications
- A characterization of the algebraic degree in semidefinite programming
- Linear optimization on varieties and Chern-Mather classes
- Discriminants and nonnegative polynomials
- The multivariate eigenvalues of symmetric tensors
- Robust approximation of chance constrained optimization with polynomial perturbation
- Faster one block quantifier elimination for regular polynomial systems of equations
- A polynomial optimization framework for polynomial quasi-variational inequalities with moment-SOS relaxations
- Conditional Euclidean distance optimization via relative tangency
- Computing local minimizers in polynomial optimization under genericity conditions
- The algebraic degree of the Wasserstein distance
- Algebraic degree of optimization over a variety with an application to P-norm distance degree
- Algebraic degrees of generalized Nash equilibrium problems
- All saddle points for polynomial optimization
- Solving polynomial variational inequality problems via Lagrange multiplier expressions and moment-SOS relaxations
- Grassmann and flag varieties in linear algebra, optimization, and statistics: an algebraic perspective
- Linear optimization with cones of moments and nonnegative polynomials
This page was built for publication: Algebraic degree of polynomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5189569)
