A Study On Theory And Algorithms Of Level-Value Approximation To Global Optimization

The thesis is devoted to a study on "Theory and Algorithms of Level-Value Approximation to Global Optimization".Our main works are proposing two algorithms of level-value approximation to global optimization,and study their convegence, computationul complexity,etc.Our main results are in the following.In the first,we propose a deterministic level-value approximation method for solving global optimization problems.The method is based on solving an equationÏ…(c)=0 with a single variable c(the level value),by using Newton's method.We firstly define a functionÏ…(c) and study its properties,which provide a theory base of the deterministic level-value approximation algorithm.Then we propose the conceptual algorithm of the deterministic level-value approximation method and prove its convergence.Follows this,we give a implementation of this conceptual algorithm based on the number theory technique,and prove its convergence by inspecting and verifying this algorithm satisfies the conditions of convergence of inexact Newton's method.We extend the deterministic level-value approximation method to solve global optimization problems with robust objective function and constrains,and propose a implementation of the deterministic level-value approximation method by using Monte-Carlo method with importance sampling,and prove its convergence.Numberical results show that,this algorithm has wide range suitability,better accuracy and better efficiency in pratice.In addition,we study thc performance of this implementable algorithm with different distributions.In the second,we propose a stochastic level-value approximation method for solving global optimization problems.We also study the convergence and computationul complexity of this algorithm.The method combines ideas of Pure Adaptive Search (PAS),Pure Random Search(PRS) and Importance Sampling,and use the idea of the Cross- Entropy method(CE).It has asymptotical convergence and expectation polynomial complexity,at the same time,since it requests less analytic properties of problems(Indeed,it only requests function value),the method can be widely applied in engineering calculation.Numberical results show the effectiveness of this method. We extend it to solve Quadratic Integer Convex Programming(QICP),the numberical results show its advantages in computational-time and accuracy,compares with some classical random algorithms for integer programming.In the third,we modify two classical algorithms for sovling global optimization problems.We firstly modify the integral level-set method.Since we combine importance sampling and the main idea of thc cross-entropy method,our modified method preserve better efficeincy and accuracy,as well as overcome the difficulty which convergence of implementable algorithm can not be proved in theory.Follows this,we modify the cross-entropy method,at the "selection" step of our modified method,we select those points in the current level-set as elite samples,thus we guarantee asymptotical convergence of our modified cross-entropy method.Numberical results show these modified methods are as effectual as their corresponding original algorithms at least. But we proved convergence of the modified methods while as the original methods have not.The thesis is organized as the following.In chapter 1,we summarize some algorithms and thoery for solving global optimization,and introduce in brief the main works of the thesis.In chapter 2 and 3,we propose a deterministic level-value approximation method and two algorithms of its implementations,one is based on number theory technique while another is based on importance sampling.In chapter 4,we propose a stochastic level-value approximation method,and study convergence and computationul complexity of this algorithm,and extend it to solve Quadratic Integer Convex Programming(QICP).In chapter 5,we modify two classical algorithms,one is the integral level-set method and another is the cross-entropy method,we prove them asymptotical convergence.Finally,in chapter 6,we give a summary of this thesis,and give some ideas of the future research.