Approximation Algorithms for Lp-Ball and Quadratically Constrained Polynomial Optimization Problems.

摘要

In this thesis, we present polynomial time approximation algorithms for solving various homogeneous polynomial optimization problems and their multilinear relaxations. Specifically, for the problems with Lp ball constraint, where p ∈ [2, infinity], by reducing them to that of determining the Lq-diameter of certain convex body, we show that they can be approximated to within a factor of O((log n)(d --2)/p/nd /2--1) in deterministic polynomial time, where q = p/(p -- 1) is the conjugate of p, n is the number of variables, and d is the degree of the polynomial. We further show that with the help of randomization, the approximation guarantee can be improved to O((log n/ n)d/2--1), which is independent of p and is currently the best for the aforementioned problems. Moreover, we extend the argument of deterministic algorithm mentioned above to solve the quadratically constrained polynomial optimization problems. In particular, for any intersection of ellipsoids K, we can, in polynomial time, construct a random polytope P, which satisfies O([special characters omitted]) · K P K. Then, by reducing the problem to that of evaluating the maximum polytopal norm || · ||P induced by P, over certain convex body, we can approximate the quadratically constrained problem within a factor of O((log n/ mn)d/2--1 log m--1) in polynomial time. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where p ∈ {2, infinity}. We believe that the wide array of tools used in this thesis will have further applications in the study of polynomial optimization problems.;Key words: Polynomial Optimization; Approximation Algorithms; Diameters of Convex Bodies; Convex Programming.