- A PTAS for the minimization of polynomials of fixed degree over the simplex Etienne de Klerk (e.deklerkuvt.nl) Monique Laurent (moniquecwi.nl) Pablo Parrilo (parriloMIT.EDU) Abstract: We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy of upper bounds $p_{\Delta(k)}$ converging to $p_{\min}$ as $k\longrightarrow \infty$. These upper approximations are intimately linked to a hierarchy of lower bounds for $p_{\min}$ constructed via P\'olya's theorem about representations of positive forms on the simplex. Revisiting the proof of P\'olya's theorem allows us to give estimates on the quality of these upper and lower approximations for $p_{\min}$. Moreover, we show that the bounds $p_{\Delta(k)}$ yield a polynomial time approximation scheme for the minimization of polynomials of fixed degree $d$ on the simplex, extending an earlier result of Bomze and De Klerk for degree $d=2$. Keywords: global optimization, semidefinite programming, positive polynomial, sum of squares of polynomials, approximation algorithm Category 1: Global Optimization (Theory ) Category 2: Combinatorial Optimization (Approximation Algorithms ) Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: Unpublished, preprint, March 2004, revised in October 2004. To appear in Theretical Computer Science Download: [Postscript]Entry Submitted: 02/01/2005Entry Accepted: 02/01/2005Entry Last Modified: 05/24/2005Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.