News

Development of CUDA based methods for Polynomial Global Optimization using the Bernstein Polynomial Approach

 
 

Prof. P. S. V. Nataraj

Principal Investigator
Professor in Systems and Control Engineering Group
Indian Institute of Technology Bombay
Mumbai, India

Email: nataraj@sc.iitb.ac.in


The Global Optimization Problem
Figure: The Global Optimization Problem

Global optimization is the problem of finding the global minimum of a function over a given search space. Global optimization problems occur widely in almost all areas of science and engineering. Many methods for solving global optimization problems are available [1], [2], and they find the minimum value of a function on a given domain. Such techniques include Generalized Benders Decomposition, Branch-and-Bound, Outer Approximation, and Generalized Outer Approximation. However these techniques do not guarantee that they can always find the global minimum of the function.

The Bernstein polynomial method is a recent technique for finding the global minimum of polynomial functions. The Bernstein method is based on the idea that if a polynomial is written in the Bernstein form [3], then the range is bounded by the minimum and maximum Bernstein coefficients. Moreover, the bounds are sharp if and only if these coefficients are also the vertex coefficients. Using these beautiful properties and the tool of domain subdivision, the Bernstein approach to global polynomial optimization is being developed at IIT Bombay. The remarkable feature of the Bernstein optimization approach is that it guarantees finding the global minimum. Further, no initial guess is needed for starting the optimization; an initial search box bounding the domain of interest will do. Recently, a free to use SCILAB based toolbox based on this approach was developed and released by the IIT Bombay group for worldwide use. The software is available from http://atoms.scilab.org/toolboxes/Global_Optim_toolbox. More than 1000 downloads of this software have taken place till now.

On the other hand, NVIDIA has been developing the CUDA (Compute Unified Device Architecture) [4] parallel computing architecture. This architecture enables dramatic increases in computing performance by harnessing the power of the GPU (Graphics Processing Unit). CUDA gives developers access to the virtual instruction set and memory of the parallel computational elements in CUDA GPUs. CUDA provides both a low level API and a higher level API. The next generation GPU (code named Fermi) is a standard on NVIDIA's GPU; it has been designed from the ground up to natively support more programming languages such as C++.

CUDA has been enthusiastically received in several areas of scientific research. However, a survey of the literature and the internet reveals that global optimization approaches specially designed for CUDA GPUs are not yet available.

We have initiated development of new global optimization methods based on the Bernstein polynomial approach for CUDA GPUs. We believe that the new Bernstein polynomial approaches will be able to more efficiently solve global optimization problems, especially where number of variables are large.

Current work

The first task in the Bernstein approach is to compute the coefficients of the Bernstein form of polynomials. There are various methods to compute Bernstein coefficients, see [7]. Computation of the Bernstein coefficients in turn involves computation of binomial coefficients. For the latter task, a popular method is based on the routine nchoosek of MATLAB [5]. An alternate, perhaps more efficient method, is Comb6 [6]. We programmed these methods for CUDA C, as both serial and parallel CUDA C versions. We then applied them for constructing large matrices of binomial coefficients. The matrices were of up to 1024 x 1024 size. The computations were done on Intel's 64 bit i7 3.07 GHz processor, MS-Windows 7.0, VC++ 2010, CUDA 3.2 toolkit, with NVIDIA's Fermi Tesla C2050 single GPU.

With the parallel CUDA C version of Comb6, we obtained speedup by factors of 175, 359, and 23030 over the serial CUDA Comb6 version, nchoosek method in C, and nchoosek method in MATLAB, respectively.

A forthcoming paper in the Second International Conference on Meta Computing, Goa, India, Dec. 2011 (see www.icomec.org) describes this work.

Future work

In the near future, we plan to develop a complete method based on CUDA GPUs in the Bernstein optimization framework. This is a challenging task for multivariate polynomials, and more so when the number of variables is large. Of course, we also will have to develop an efficient CUDA based software for applying this method to application problems.

References

[1] R. Horst and P.M Pardalos, Handbook of Global Optimization, Vol. 1. Dordrecht: Kluwer Academic Publishers, 1995.

[2] P. M. Pardalos and H. E. Romei Jn, Handbook of Global Optimization Vol.2, Dordrecht : Kluwer Academic Publishers, 2002.

[3] G. G. Lorentz, Bernstein polynomials, New York: Chelsea Publishing Company, 1988.

[4] see the website http://developer.download.nvidia.com/compute/cuda/3_2/toolkit/docs/CUDA_C_Programming_Guide.pdf

[5] http://www.mathworks.com/products/matlab/

[6] Y. Manolopoulos, "Binomial coefficients computation: Recursion or iteration?", SIGCSE Bulletin, Vol. 34, no.4, pp. 65-67, Dec 2002.

[7] S. Ray, "A new approach to range computation of polynomials using the Bernstein form", PhD
Thesis, Indian Institute of Technology, Bombay, India, 2007.

Publications from our group (related to global optimization and its applications)

Journal papers

  • P. S. V. Nataraj and M. Arounassalame, “An Interval Newton Method based on the Bernstein Form for bounding the Zeros of Polynomial Systems”, Reliable computing, Vol 15, pp. 109-119, 2011.
  • S. Ray and P. S. V. Nataraj, “A new strategy for selecting subdivision point in the Bernstein approach to polynomial optimization”, Reliable computing, Vol 14, pp.117-137, 2010.
  • P. S. V. Nataraj and Shanta Sondur, “The extrapolated interval global optimization algorithm”, Journal of Global Optimization, Volume (50), No. 2, pp. 249-70, 2011.
  • P. S. V. Nataraj and M. Arounassalame “Constrained global optimization of multivariate polynomials using Bernstein branch and prune algorithm”, Journal of Global Optimization, Vol. 49, No.2, pp.185-212, 2011.
  • S. Ray and P. S. V. Nataraj, “An efficient algorithm for range computation of polynomials using the Bernstein form”, Journal of Global Optimization, Volume 45, Number 3, November, pages 403-426, 2009.
  • P. S. V. Nataraj and M. Arounassalame, “An algorithm for constrained global optimization of multivariate polynomials using the Bernstein form and John optimality conditions”, OPSEARCH, Volume 46, Number 2, June 2009, pp. 133-152.
  • P. S. V. Nataraj and M. Arounassalame, “A new subdivision algorithm for Bernstein Polynomial Approach to Global Optimization”, International Journal of Automation and Computing, Vol. 4, no. 4, pp. 342-352, 2007.
  • P. S. V. Nataraj and K. Kotecha, “An improved interval global optimization algorithm using higher order inclusion function forms”, Journal of Global Optimization, Vol. 32, No. 1, pp. 35-63, May 2005.
  • P. S. V. Nataraj and K. Kotecha, “Global optimization with higher order inclusion function forms – Part 1: A combined Taylor-Bernstein form”, Reliable Computing , Vol. 10, No. 1, pp 27-44, 2004.
  • P. S. V. Nataraj and K. Kotecha, “Higher order convergence for multidimensional functions with a new Taylor-Bernstein form as inclusion function”, Reliable Computing, Vol. 9, issue 3, pages 185-203, 2003.
  • P. S. V. Nataraj and K. Kotecha, “An Algorithm for global optimization using the Taylor-Bernstein form as an inclusion function”, Journal of Global Optimization, Vol. 24, pp. 417-436, 2002.

Conference papers

  • Bhagyesh V. Patil and P. S. V. Nataraj, “Application of the Bernstein Form for Reliable Global Optimization of Mixed-Integer Problems in Process Synthesis and Design”, Proc. 2nd International Conference On Reliability, Safety And Hazard - Risk-Based Technologies And Physics-Of Failure Methods (ICRESH-2010), BARC, India, December 14-16, 2010.
  • Dhiraj B. Magare, Bhagyesh V. Patil, Vishwesh A. Vyavahare and P. S. V. Nataraj, “A Scilab Based Open Source Toolbox for Global Optimization Using the Bernstein Form”, Proc. 2nd International Conference On Reliability, Safety And Hazard - Risk-Based Technologies And Physics-Of Failure Methods (ICRESH-2010), BARC, India, December 14-16, 2010.
  • Bhagyesh V. Patil, P.S.V. Nataraj, and S. Bhartiya, “Global Optimization of Mixed-Integer Nonlinear Programming Problems: The Bernstein Polynomial Approach”, International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, France, 2010.
  • P. S. V. Nataraj and N. Kubal, Adaptive QFT control using hybrid global optimization and constraint propagation techniques. Proceedings of the IEEE conference on decision and control; 2008. p.1001-5.
  • P. S. V. Nataraj and M. Arounassalame, “Global Optimization of Multivariate Polynomials using New Bernstein Subdivision Algorithm”, Proc. International Conference on Advances in Control and Optimization of Dynamical Systems (ACODS-2007), Bangalore, India, February 2007.
  • P. S. V. Nataraj and M. Arounassalame, “A new subdivision algorithm for Global optimization based on the Bernstein Polynomial Approach”, Proc. of the International Conference on Advances in control and optimization of Dynamic systems (ACODS-2007), Bangalore, India, pp. 15-22, Feb. 2007.
  • P. S. V. Nataraj and M. Arounassalame, “Solving Polynomial systems using combined Bernstein Krawczyk Subdivision Algorithm”, Proc. of the International Conference on Computer Aided Engineering 2007 (CAE 2007) , IIT Madras, India, pp. 682-689, Dec. 2007.

Ph. D Theses (related to global optimization and its applications)

  • Arounassalame M, "Global Optimization of Polynomials using the Bernstein Form and its Applications to Systems and Control Engineering", IIT Bombay, 2009.
  • Nandkishor S Kubal, " Applications of interval global optimization to robust stability analysis and control", IIT Bombay, 2008.
  • Shanta Sondur, "Application of Extrapolation Methods to Range Finding Algorithms and Global Optimization", IIT Bombay, 2008.
  • Shashwati Ray, "A new approach to range computation of polynomials using the Bernstein form", IIT Bombay, 2007.
  • Tharewal Sachin Shrihari , "Automated Synthesis of QFT Controllers and Prefilters using Interval Global Optimization Techniques", IIT Bombay, 2005.
  • Kotecha Ketan Virendrabhai, "Higher order inclusion function forms and their application in interval global optimization", IIT Bombay, 2003.

On-going Ph. D thesis research (related to global optimization and its applications)

  • Bhagyesh V. Patil, “Global optimization of mixed-integer nonlinear polynomial programming problems using the Bernstein form”, IIT Bombay, Joined in Jan 2008.
  • Priyadarshan S. Dhabe, “A new approach to global optimization based on Bernstein polynomial and GPU computing”, IIT Bombay, Joined in July 2010.
  • Jeyasenthil R., “Robust Control and GPU Computing”, IIT Bombay, Joined in Jan 2011.


 
 
FacebookTwitterLinkedInGoogle+Pinterest