TY - JOUR

T1 - Complexity aspects of local minima and related notions

AU - Ahmadi, Amir Ali

AU - Zhang, Jeffrey

N1 - Funding Information:
This work was supported partially by an AFOSR MURI award, the DARPA Young Faculty Award, the Princeton SEAS Innovation Award, the NSF CAREER Award, the Google Faculty Award, and the Sloan Fellowship .
Publisher Copyright:
© 2021 Elsevier Inc.

PY - 2022/3/5

Y1 - 2022/3/5

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

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

KW - Computational complexity

KW - Critical and second-order points

KW - Local minima

KW - Polynomial optimization

KW - Semidefinite programming

KW - Sum of squares polynomials

UR - http://www.scopus.com/inward/record.url?scp=85119441981&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85119441981&partnerID=8YFLogxK

U2 - 10.1016/j.aim.2021.108119

DO - 10.1016/j.aim.2021.108119

M3 - Article

AN - SCOPUS:85119441981

VL - 397

JO - Advances in Mathematics

JF - Advances in Mathematics

SN - 0001-8708

M1 - 108119

ER -