Higher-Order Newton Methods with Polynomial Work per Iteration

 We present generalizations of Newton’s method that incorporate derivatives of an arbitrary order $$d$$ but maintain a polynomial dependence on dimension in their cost per iteration. At each step, our $$d^{\text{th}}$$-order method uses semidefinite programming to construct and minimize a sum of squares-convex approximation to the $$d^{\text{th}}$$-order Taylor expansion of the function we wish … Read more

Complexity Aspects of Fundamental Questions in Polynomial Optimization

In 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 … Read more

On the Complexity of Finding a Local Minimizer of a Quadratic Function over a Polytope

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 \ge 0$) of a local minimizer of an $n$-variate quadratic function over a polytope. This result (even with $c=0$) answers a question of Pardalos and Vavasis that appeared in 1992 on a … Read more

Complexity Aspects of Local Minima and Related Notions

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 … Read more

On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization

We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known “Frank-Wolfe type” theorems … Read more

Semidefinite Programming and Nash Equilibria in Bimatrix Games

We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium (NE) problem and provide a number of valid inequalities to improve the quality of the relaxation. If a rank-1 solution to this SDP is … Read more