## 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

## Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method

Optimization problems with cardinality constraints are very dicult mathematical programs which are typically solved by global techniques from discrete optimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between the local minima is also discussed in … Read more