Complexity aspects of local minima and related notions

• DOI: 10.48550/arxiv.2008.06148
• Publication Date: 2020-01-01
• Authors: Amir Ali Ahmadi; Jeffrey Zhang
• Keywords: Maxima and minima; Cubic function

We consider the notions of (i) critical points, (ii) second-order (iii) local minima, and (iv) strict minima for multivariate polynomials. For each type point, as a function degree polynomial, we study complexity deciding (1) if given point is that type, (2) polynomial has type. Our results characterize these two questions all degrees left open by prior literature. main contributions reveal many turn out to be tractable cubic In particular, present an efficiently-checkable necessary sufficient condition minimality polynomial. also show minimum can efficiently found solving semidefinite programs size linear in number variables. By contrast, it strongly NP-hard decide point. prove set points any spectrahedron, conversely spectrahedron projection our final section, briefly potential application finding polynomials design third-order Newton method.