Algorithms for unconstrained global optimization of nonlinear (polynomial) programming problems: The single and multi-segment polynomial B-spline approach

We investigate the use of the polynomial B-spline form for unconstrained global optimization of multivariate polynomial nonlinear programming problems. We use the B-spline form for higher order approximation of multivariate polynomials. We first propose a basic algorithm for global optimization that uses several accelerating algorithms such as cut-off test and monotonicity test. We then propose an improved algorithm consisting of several additional ingredients, such as a new subdivision point selection rule and a modified subdivision direction selection rule. The performances of the proposed basic and improved algorithms are tested and compared on a set of 14 test problems under two test conditions. The results of the tests show the superiority of the improved algorithm with multi-segment B-spline over that of the single segment B-spline, in terms of the chosen performance metrics. We also compare the quality of the set of all global minimizers found using the proposed algorithms (basic & improved) with those using well-known solvers BARON and Gloptipoly, on a smaller set of four test problems. The problems in the latter set have multiple global minimizers. The results show the superiority of the proposed algorithms, in that they are able to capture all the global minimizers, whereas Gloptipoly and BARON fail to do so in some of the test problems.