In this paper, we propose basic and improved algorithms based on polynomial B-spline form for constrained global optimization of multivariate polynomial functions. The proposed algorithms are based on a branch-and-bound framework. In improved algorithm we introduce several new ingredients, such as B-spline box consistency and B-spline hull consistency algorithm to prune the search regions and make the search more efficient. The performance of the basic and improved algorithm is tested and compared on set of test problems. The results of the tests show the superiority of the improved algorithm over the basic algorithm in terms of the chosen performance metrics for 7 out-off 11 test problems. We compare optimal value of global minimum obtained using the proposed algorithms with CENSO, GloptiPoly and several state-of-the-art NLP solvers, on set of 11 test problems. The results of the tests show the superiority of the proposed algorithm and CENSO solver (open source solver for global optimization of B-spline constrained problem) in that it always captures the global minimum to the user-specified accuracy.
Keywords: Polynomial B-spline, global optimization, polynomial optimization, constrained optimization
@article{RO_2021__55_6_3743_0,
author = {Gawali, Deepak D. and Patil, Bhagyesh V. and Zidna, Ahmed and Nataraj, P. S. V.},
title = {Constrained global optimization of multivariate polynomials using polynomial {B-spline} form and {B-spline} consistency prune approach},
journal = {RAIRO. Operations Research},
pages = {3743--3771},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {6},
doi = {10.1051/ro/2021179},
mrnumber = {4353561},
zbl = {1486.90153},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021179/}
}
TY - JOUR AU - Gawali, Deepak D. AU - Patil, Bhagyesh V. AU - Zidna, Ahmed AU - Nataraj, P. S. V. TI - Constrained global optimization of multivariate polynomials using polynomial B-spline form and B-spline consistency prune approach JO - RAIRO. Operations Research PY - 2021 SP - 3743 EP - 3771 VL - 55 IS - 6 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021179/ DO - 10.1051/ro/2021179 LA - en ID - RO_2021__55_6_3743_0 ER -
%0 Journal Article %A Gawali, Deepak D. %A Patil, Bhagyesh V. %A Zidna, Ahmed %A Nataraj, P. S. V. %T Constrained global optimization of multivariate polynomials using polynomial B-spline form and B-spline consistency prune approach %J RAIRO. Operations Research %D 2021 %P 3743-3771 %V 55 %N 6 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021179/ %R 10.1051/ro/2021179 %G en %F RO_2021__55_6_3743_0
Gawali, Deepak D.; Patil, Bhagyesh V.; Zidna, Ahmed; Nataraj, P. S. V. Constrained global optimization of multivariate polynomials using polynomial B-spline form and B-spline consistency prune approach. RAIRO. Operations Research, Tome 55 (2021) no. 6, pp. 3743-3771. doi: 10.1051/ro/2021179
[1] , and , Global minimization using an Augmented Lagrangian method with variable lower-level constraints. Math. Program. 125 (2010) 139–162. | MR | Zbl | DOI
[2] , and , Introduction to Interval Analysis. Siam, Philadelphia (2009). | Zbl
[3] , On Calculating with B-splines. J. Approximation Theory 6 (1972) 50–62. | MR | Zbl | DOI
[4] and , A Collection of Test Problems for Constrained Global Optimization Algorithms. Vol. 455. Springer (1990). | MR | Zbl | DOI
[5] , , , , , , , and , Handbook of Test Problems in Local and Global Optimization. Springer Science & Business Media (2013). | MR | Zbl
[6] , The Bernstein algorithm. Interval Comput. 6 (1993) 154–168. | MR | Zbl
[7] , and , Solving nonconvex optimization problems in systems and control: a polynomial B-spline approach. In: Modelling, Computation and Optimization in Information Systems and Management Sciences. Springer (2015) 467–478. | Zbl
[8] , and , Algorithms for unconstrained global optimization of nonlinear (polynomial) programming problems: the single and multi-segment polynomial B-spline approach. Comput. Oper. Res. 87 (2017) 205–220. | MR | Zbl | DOI
[9] , , and , A B-spline global optimization algorithm for optimal power flow problem. In: World Congress on Global Optimization. Springer (2019) 58–67.
[10] Global library. available online at http://www.gamsworld.org/global/globallib.
[11] , A MIQCP formulation for B-spline constraints. Optim. Lett. 12 (2018) 713–725. | MR | Zbl | DOI
[12] and , Mathematical programming formulations for piecewise polynomial functions. J. Global Optim. 77 (2020) 455–486. | MR | Zbl | DOI
[13] and , Global optimization with spline constraints: a new branch-and-bound method based on B-splines. J. Global Optim. 65 (2016) 401–439. | MR | Zbl | DOI
[14] and , Global Optimization Using Interval Analysis, 2nd edition. Revised and Expanded. Vol. 264, Marcel DEKKER, INC., New York (2004). | MR | Zbl
[15] and , Gloptipoly: global optimization over polynomials with matlab and sedumi. ACM Trans. Math. Softw. (TOMS) 29 (2003) 165–194. | MR | Zbl | DOI
[16] and , Solving nonconvex optimization problems. IEEE Control Syst. Mag. 24 (2004) 72–83. | DOI
[17] and , Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands (1995). | MR | Zbl | DOI
[18] , Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics. Vol. 1. Springer Science & Business Media (2001). | MR | Zbl | DOI
[19] , Rigorous Global Search: Continuous Problems. Vol. 13, Springer Science & Business Media (2013). | MR | Zbl
[20] , Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11 (2001) 796–817. | MR | Zbl | DOI
[21] and , Methods for bounding the range of a polynomial. J. Comput. Appl. Math. 58 (1995) 193–199. | MR | Zbl | DOI
[22] and , Interval approximation of higher order to the ranges of functions. Comput. Math. App. 31 (1996) 101–109. | MR | Zbl
[23] and , Spline Methods Draft. Department of Informatics, Centre of Mathematics for Applications, University of Oslo (2008).
[24] Mathworks Inc., MATLAB version 8.0.0.783 (R 2012 b), Inc. Natick, Massachusetts, United States (2012).
[25] , , and , Computing the range of values of real functions using B-spline form. Appl. Math. Comput. 233 (2014) 85–102. | MR | Zbl
[26] and , An algorithm for constrained global optimization of multivariate polynomials using the Bernstein form and John optimality conditions. Opsearch 46 (2009) 133–152. | MR | Zbl | DOI
[27] and , Constrained global optimization of multivariate polynomials using Bernstein branch and prune algorithm. J. Global Optim. 49 (2011) 185–212. | MR | Zbl | DOI
[28] NEOS Server for optimization. http://www.neos-server.org/neos/solvers/ (2018).
[29] , Approximate branch-and-bound global optimization using B-spline hypervolumes. Adv. Eng. Softw. 45 (2012) 11–20. | DOI
[30] , Global optimization of polynomial mixed-integer nonlinear problems using the Bernstein form. Ph.D. thesis. Indian Institute of Technology, Bombay (2012).
[31] , and , Global optimization of mixed-integer nonlinear (polynomial) programming problems: the bernstein polynomial approach. Computing 94 (2012) 325–343. | MR | Zbl | DOI
[32] and , Computer Methods for the Range of Functions. Ellis Horwood Limited, Chichester, England (1984). | MR | Zbl
[33] and , New Computer Methods for Global Optimization. Ellis Horwood Limited, Chichester, England (1988). | MR | Zbl
[34] , CS3621 Introduction to computing with geometry notes. http://www.cs.mtu.edu/shene/COURSES/cs3621/NOTES/ (2014).
[35] and , Global optimization of nonconvex nonlinear programs via interval analysis. Comput. Chem. Eng. 18 (1994) 889–897. | DOI
[36] , and , Solving polynomial systems using a branch and prune approach. SIAM J. Numer. Anal. 34 (1997) 797–827. | MR | Zbl | DOI
Cité par Sources :
