We review complexity results for minimizing polynomials over the standard simplex and unit hypercube.In addition, we show that there exists a polynomial time approximation scheme (PTAS) for minimizing Lipschitz continuous functions and functions with uniformly bounded Hessians over the standard...

In this paper we prove the counterintuitive result that the quadratic least squares approximation of a multivariate convex function in a finite set of points is not necessarily convex, even though it is convex for a univariate convex function. This result has many consequences both for the field...

We consider the problem of minimizing a univariate function f on an interval [a, b]. When f is a polynomial, we review how this problem may be reformulated as a semidefinite programming (SDP) problem, and review how to extract all global minimizers from the solution of the SDP problem. For...

Polynomials, trigonometric polynomials, and rational functions are widely used for the discrete approximation of functions or simulation models. Often, it is known beforehand, that the underlying unknown function has certain properties, e.g., nonnegative or increasing on a certain region....

We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in the paper: D. Cvetkovic, M....

We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E....

In this paper we present the algorithmic framework and practical aspects of implementing a parallel version of a primal-dual semidefinite programming solver on a distributed memory computer cluster. Our implementation is based on the CSDP solver and uses a message passing interface (MPI), and...