Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01hm50tv795
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorAhmadi, Amir Ali
dc.contributor.authorZhang, Jeffrey
dc.contributor.otherOperations Research and Financial Engineering Department
dc.date.accessioned2020-11-20T05:59:23Z-
dc.date.available2020-11-20T05:59:23Z-
dc.date.issued2020
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/dsp01hm50tv795-
dc.description.abstractIn this thesis, we settle the computational complexity of some fundamental questions in polynomial optimization. These include the questions of (i) finding a local minimum, (ii) testing local minimality of a candidate point, and (iii) deciding attainment of the optimal value. Our results characterize the complexity of these three questions for all degrees of the defining polynomials left open by prior literature. Regarding questions (i) and (ii), we show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c$) of a local minimum of an $n$-variate quadratic function over a polytope. This result answers a question of Pardalos and Vavasis that appeared in 1992 on a list of seven open problems in complexity theory for numerical optimization. By contrast, through leveraging techniques from algebraic geometry, we show that a local minimum of a cubic polynomial can be found efficiently by semidefinite programming. Interestingly, we prove that second-order points of cubic polynomials admit an efficient semidefinite representation, even though their critical points are NP-hard to find. We also give an efficiently-checkable necessary and sufficient condition for local minimality of a point for a cubic polynomial. Regarding question (iii), we prove that testing whether a quadratically constrained quadratic program with a finite optimal value has an optimal solution is NP-hard. We also show that testing coercivity of the objective function, compactness of the feasible set, and the Archimedean property associated with the description of the feasible set are all NP-hard. The latter property is the assumption on which convergence of the Lasserre hierarchy relies. We also give a new characterization of coercive polynomials that lends itself to a hierarchy of semidefinite programs. In our final chapter, we present a semidefinite programming relaxation for the problem of finding approximate Nash equilibria in bimatrix games. We show that for a symmetric game, a $1/3$-Nash equilibrium can be efficiently recovered from any rank-2 solution to this relaxation. We also propose semidefinite programming relaxations for NP-hard problems related to Nash equilibria, such as that of finding the highest achievable welfare under any Nash equilibrium.
dc.language.isoen
dc.publisherPrinceton, NJ : Princeton University
dc.relation.isformatofThe Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: <a href=http://catalog.princeton.edu> catalog.princeton.edu </a>
dc.subjectComputational complexity
dc.subjectLocal Minima
dc.subjectPolynomial optimization
dc.subjectSemidefinite programming
dc.subjectSum of squares polynomials
dc.subject.classificationOperations research
dc.subject.classificationApplied mathematics
dc.subject.classificationComputer science
dc.titleComplexity Aspects of Fundamental Questions in Polynomial Optimization
dc.typeAcademic dissertations (Ph.D.)
Appears in Collections:Operations Research and Financial Engineering

Files in This Item:
File Description SizeFormat 
Zhang_princeton_0181D_13487.pdf1.09 MBAdobe PDFView/Download


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.