Let S be a compact semialgebraic set and let f be a polynomial nonnegative on S. Schmüdgen’s Positivstellensatz then states that for any \eta>0, the nonnegativity of f+\eta on S can be certified by expressing f+\eta as a conic combination of products of the polynomials that occur in the inequalities defining S, where the coefficients … Read more
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
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
We consider the problem of fitting a polynomial function to a set of data points, each data point consisting of a feature vector and a response variable. In contrast to standard polynomial regression, we require that the polynomial regressor satisfy shape constraints, such as monotonicity, Lipschitz-continuity, or convexity. We show how to use semidefinite programming … Read more
In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a known ambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distribution that give nature too much … Read more
In this paper, we study polynomial norms, i.e. norms that are the dth root of a degree-d homogeneous polynomial f. We first show that a necessary and sufficient condition for f^(1/d) to be a norm is for f to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from dth … Read more
SOSTOOLS is a free MATLAB toolbox for formulating and solving sum of squares (SOS) optimization programs. It uses a simple notation and a flexible and intuitive high-level user interface to specify the SOS programs. Currently these are solved using SeDuMi, a well-known semidefinite programming solver, while SOSTOOLS handles internally all the necessary reformulations and data … Read more