A New Strategy For Selecting Subdivision Point In The Bernstein Approach To Polynomial Optimization
Shashwati Ray, P. S. V. Nataraj · 2010
In the Bernstein approach to polynomial range finding, we propose a new rule for selection of the point where the domain subdivision is to be done. For a given direction of subdivision, instead of subdividing a box at its midpoint (as is done in the existing literature), we propose to subdivide the box at a point where the partial derivative of the polynomial (in the direction of subdivision) equals zero. The location of this point is estimated using the variation diminishing property of the derivative polynomial in the Bernstein form. We then compare the performance of the proposed rule for subdivision point with that of the existing midpoint subdivision rule, on nine polynomial problems of different dimensions-varying from two to eight dimensions. We evaluate both the rules using three different existing subdivision direction selection rules, and find the proposed rule to be overall more efficient in computational time and number of subdivisions.