A Refined Error Analysis for Fixed-Degree Polynomial Optimization over the Simplex
- PDF / 297,768 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 168 Views
A Refined Error Analysis for Fixed-Degree Polynomial Optimization over the Simplex Zhao Sun
Received: 9 June 2014 / Revised: 17 August 2014 / Accepted: 26 August 2014 / Published online: 11 September 2014 Ó Operations Research Society of China, Periodicals Agency of Shanghai University, and SpringerVerlag Berlin Heidelberg 2014
Abstract We consider the problem of minimizing a fixed-degree polynomial over the standard simplex. This problem is well known to be NP-hard, since it contains the maximum stable set problem in combinatorial optimization as a special case. In this paper, we revisit a known upper bound obtained by taking the minimum value on a regular grid, and a known lower bound based on Po´lya’s representation theorem. More precisely, we consider the difference between these two bounds and we provide upper bounds for this difference in terms of the range of function values. Our results refine the known upper bounds in the quadratic and cubic cases, and they asymptotically refine the known upper bound in the general case. Keywords Polynomial optimization over the simplex Global optimization Nonlinear optimization Mathematics Subject Classification
90C30 90C60
1 Introduction and Preliminaries Consider the problem of minimizing a homogeneous polynomial f 2 R½x of degree d on the (standard) simplex Dn :¼ fx 2 Rnþ :
n X
xi ¼ 1g:
i¼1
Z. Sun (&) Tilburg University, PO Box 90153, 5000 LE Tilburg, the Netherlands e-mail: [email protected]
123
380
Z. Sun
That is the global optimization problem f :¼ min f ðxÞ; or f :¼ max f ðxÞ: x2Dn
ð1:1Þ
x2Dn
Here we focus on the problem of computing the minimum f of f over Dn . This problem is well known to be NP-hard, as it contains the maximum stable set problem as a special case (when f is quadratic). Indeed, given a graph G ¼ ðV; EÞ with adjacency matrix A, Motzkin and Straus [8] show that the maximum stability number aðGÞ can be obtained by 1 ¼ min xT ðI þ AÞx; aðGÞ x2DjVj where I denotes the identity matrix. Moreover, one can w.l.o.g. assume f is P homogeneous. Indeed, if f ¼ ds¼0 fs , where fs is homogeneous of degree s, then Pn ds P minx2Dn f ðxÞ ¼ minx2Dn f 0 ðxÞ, setting f 0 ¼ ds¼0 fs : i¼1 xi For problem (1.1), many approximation algorithms have been studied in the literature. In fact, when f has fixed degree d, there is a polynomial time approximation scheme (PTAS) for this problem, see [1] for the case d ¼ 2 and [5, 7] for d > 2. For more results on its computational complexity, we refer to [3, 6]. We consider the following two bounds for f : an upper bound fDðn;rÞ obtained by ðrdÞ
taking the minimum value on a regular grid and a lower bound fmin based on Po´lya’s representation theorem. They both have been studied in the literature, see ðrdÞ e.g., [1, 5, 7] for fDðn;rÞ and [5, 14, 15] for fmin . The two ranges fDðn;rÞ f and ðrdÞ
f fmin have been studied separately and upper bounds for each of them have been shown in the above-mentioned works. In this paper, we study these two ranges at the same time. More precisely, we ðrdÞ analyze the l
Data Loading...
