An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex

详细信息    查看全文

• 作者：Etienne de Klerk ; Monique Laurent ; Zhao Sun
• 关键词：Polynomial optimization over a simplex ; PTAS ; Bernstein approximation ; 90C30 ; 90C60
• 刊名：Mathematical Programming
• 出版年：2015
• 出版时间：July 2015
• 年：2015
• 卷：151
• 期：2
• 页码：433-457
• 全文大小：537 KB
• 参考文献：1.Altomare, F., Campiti, M.: Korovkin-type approximation theory and its applications. De Guyter studies in mathematics, vol. 17. Walter de Guyter publishers, Berlin (1994)View Article
  2.Bellare, M., Rogaway, P.: The complexity of approximating a nonlinear program. Math. Program. 69, 429-41 (1995)MATH MathSciNet
  3.Bomze, I.M., de Klerk, E.: Solving standard quadratic optimization problems via semidefinite and copositive programming. J. Global Optim. 24(2), 163-85 (2002)View Article MATH MathSciNet
  4.Bomze, I.M., Gollowitzer, S., Yildirim, E.A.: Rounding on the standard simplex: regular grids for global optimization. J. Global Optim. 59(2-), 243-58 (2014)
  5.Bos, L.P.: Bounding the Lebesque function for Lagrange interpolation in a simplex. J. Approx. Theory 38, 43-9 (1983)View Article MATH MathSciNet
  6.Ditzian, Z.: Inverse theorems for multidimensional Bernstein operators. Pac. J. Math. 121(2), 293-19 (1986)View Article MATH MathSciNet
  7.Ditzian, Z.: Best polynomial approximation and Bernstein polynomial approximation on a simplex. Indag. Math. 92, 243-56 (1989)View Article MathSciNet
  8.Ditzian, Z., Zhou, X.: Optimal approximation class for multivariate Bernstein operators. Pac. J. Math. 158, 93-20 (1993)View Article MATH MathSciNet
  9.Johnson, N.L., Kotz, S., Balakrishnan, N.: Discrete Multivariate Distributions. Wiley, New York (1997)MATH
  10.de Klerk, E., den Hertog, D., Elabwabi, G.: On the complexity of optimization over the standard simplex. Eur. J. Oper. Res. 191(3), 773-85 (2008)View Article MATH
  11.de Klerk, E., Laurent, M., Parrilo, P.: A PTAS for the minimization of polynomials of fixed degree over the simplex. Theor. Comput. Sci. 361(2-), 210-25 (2006)View Article MATH
  12.de Klerk, E., Laurent, M.: Error bounds for some semidefinite programming approaches to polynomial minimization over the hypercube. SIAM J. Optim. 20(6), 3104-120 (2010)View Article MATH MathSciNet
  13.Knoblauch, A.: Closed-form expressions for the moments of the binomial probability distribution. SIAM J. Appl. Math. 69(1), 197-04 (2008)View Article MATH MathSciNet
  14.Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796-17 (2001)View Article MATH MathSciNet
  15.Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Túran. Can. J. Math. 17, 533-40 (1965)View Article MATH MathSciNet
  16.Nesterov, Y.: Random Walk in a Simplex and Quadratic Optimization over Convex Polytopes. CORE Discussion Paper 2003/71, CORE-UCL, Louvain-La-Neuve (2003)
  17.Nesterov, Y., Wolkowicz, H., Ye, Y.: Semidefinite programming relaxations of nonconvex quadratic optimization. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming, pp. 361-19. Kluwer Academic Publishers, Norwell (2000)View Article
  18.Sagol, G., Yildirim, E.A.: Analysis of Copositive Optimization Based Bounds on Standard Quadratic Optimization. Technical Report. Department of Industrial Engineering, Koc University, Sariyer, Istanbul, Turkey (2013)
  19.Vavasis, S.: Approximation algorithms for concave quadratic programming. In: Floudas, C.A., Pardalos, P. (eds.) Recent Advances in Global Optimization, pp. 3-8. Princeton University Press, Princeton (1998)
  20.Yildirim, E.A.: On the accuracy of uniform polyhedral approximations of the copositive cone. Optim. Methods Softw. 27(1), 155-73 (2012)View Article MATH MathSciNet
  
• 作者单位：Etienne de Klerk (1)
  Monique Laurent (1) (2)
  Zhao Sun (1)
  
  1. Tilburg University, PO Box 90153, 5000 LE, Tilburg, The Netherlands
  2. Centrum Wiskunde and Informatica (CWI), Postbus 94079, 1090 GB, Amsterdam, The Netherlands
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems—it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties of Bernstein approximation on the simplex. We also refine a known error bound for the scheme for polynomials of degree three. The main contribution of the paper is to provide new insight into the PTAS by establishing precise links with Bernstein approximation and the multinomial distribution.