The hierarchy of local minimums in polynomial optimization

DOI10.1007/S10107-014-0845-2zbMATH Open1323.65071arXiv1311.4228OpenAlexW2062075554MaRDI QIDQ2349136FDOQ2349136

Authors: Jiawang Nie 

Publication date: 19 June 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: This paper studies the hierarchy of local minimums of a polynomial in the space. For this purpose, we first compute H-minimums, for which the first and second order optimality conditions are satisfied. To compute each H-minimum, we construct a sequence of semidefinite relaxations, based on optimality conditions. We prove that each constructed sequence has finite convergence, under some generic conditions. A procedure for computing all local minimums is given. When there are equality constraints, we have similar results for computing the hierarchy of critical values and the hierarchy of local minimums. Several extensions are discussed.

Full work available at URL: https://arxiv.org/abs/1311.4228

Recommendations

• Polynomial optimization with real varieties
• A new hierarchy of SDP-relaxations for polynomial programming
• Global optimization with polynomials and the problem of moments
• Local saddle points for unconstrained polynomial optimization
• Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization

zbMATH Keywords

polynomial optimizationcritical pointoptimality conditionsum of squaressemidefinite relaxationlocal minimum

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)

Cites Work

• Detecting Global Optimality and Extracting Solutions in GloptiPoly
• All Real Eigenvalues of Symmetric Tensors

Cited In (26)

• Local minima, marginal functions, and separating hyperplanes in discrete optimization
• The maximum tensor complementarity eigenvalues
• Higher-degree tensor eigenvalue complementarity problems
• Tensor complementarity problems. II: Solution methods
• Calculating entanglement eigenvalues for nonsymmetric quantum pure states based on the Jacobian semidefinite programming relaxation method
• Distributionally robust optimization with moment ambiguity sets
• Learning diagonal Gaussian mixture models and incomplete tensor decompositions
• Computing geometric measure of entanglement for symmetric pure states via the Jacobian SDP relaxation technique
• Minimizer Extraction in Polynomial Optimization Is Robust
• Tensor eigenvalue complementarity problems
• Local saddle points for unconstrained polynomial optimization
• Homogenization for polynomial optimization with unbounded sets
• Real eigenvalues of nonsymmetric tensors
• On types of isolated KKT points in polynomial optimization
• A Semidefinite Relaxation Method for Partially Symmetric Tensor Decomposition
• A proximal alternating minimization algorithm for the largest C-eigenvalue of piezoelectric-type tensors
• Global uniqueness and solvability of tensor variational inequalities
• On types of degenerate critical points of real polynomial functions
• An efficient alternating minimization method for fourth degree polynomial optimization
• Complexity aspects of local minima and related notions
• Convex generalized Nash equilibrium problems and polynomial optimization
• An adaptive high order method for finding third-order critical points of nonconvex optimization
• Title not available (Why is that?)
• Loss functions for finite sets
• Low order polynomial bounds on the expected performance of local improvement algorithms
• A semidefinite method for tensor complementarity problems

Uses Software

• RAGlib
• SeDuMi
• GloptiPoly
• YALMIP

This page was built for publication: The hierarchy of local minimums in polynomial optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2349136)