Research On Hybrid Bundle Method For Routing Selection Problem In Telecommunication Networks

The bundle method is one of the most effective and promising methods to solve non-smooth optimization problems^[1,2].The general bundle method is based on the cutting-plane method,it overcomes the shortcoming of the poor stability of the cutting-plane method.The bundle method stores the iteration information given by the black box into the"bundle",and uses the previous iteration information to construct the sub-problem for obtaining the next candidate point.The bundle method will remember the current"best"candidate points until we find the optimal solution.In this thesis,the routing selection problem in telecommunication networks is studied and the dual problem is constructed after the approximation of the objective function is obtained,and we can get the explicit expression of the optimal solution to the dual sub-problem and some relevant conclusions by using the general bundle method.Based on the proximal bundle method and the trust region bundle method,a hybrid bundle method is presented and applied to the dual sub-problem of the routing selection problem in telecommunication networks,explicit expression of the optimal solution and some significant conclusions are obtained,which are of great significance to the construction of the hybrid bundle algorithm and the convergence analysis.Finally,the framework of the hybrid bundle algorithm,the relevant conclusions and the convergence analysis of the algorithm are given,and then we can get the relationship of the optimal values between the dual problem and the original problem.In this thesis,the hybrid bundle method is applied to study the routing selection problem in telecommunication networks which is a non-smooth optimization problem,the structure of the thesis is as follows:In the first part,several methods for solving non-smooth optimization problems are introduced:the steepest descent method,the sub-gradient method,the cutting-plane method,and the bundle method.The research status of the hybrid bundle method and routing selection problem in telecommunication network are also presented.Then the basic knowledge and related theories involved in this thesis are explained,which are the theoretical basis of the following parts.In the second part,the general bundle method for solving the dual problem of the routing selection problem in telecommunication networks is discussed.Firstly,the routing selection problem in telecommunication network is introduced,and by using the approximate model,we obtain the dual problem--the maximization problem of concave function.Then some adjustments are made to the general bundle method to make it suitable for the current maximization problem of concave function,and at the same time we get the explicit expression of the optimal solution and some conclusions.The third part focuses on the hybrid bundle method for solving the dual problem of the routing selection problem in telecommunication networks.Firstly,we give the basic idea of the hybrid bundle method to construct the dual problem of the routing selection problem in telecommunication networks,the explicit expression of the optimal solution to the sub-problem and the important conclusions related to the aggregate linearization are obtained.Next,the algorithm framework and convergence analysis of the hybrid bundle method for solving the dual problem of the routing selection problem in telecommunication networks are given.Convergence analysis is mainly divided into the following three cases:firstly,when the setU_s is empty and appears infinitely many times;secondly,the algorithm produces an infinite number of ascend steps;thirdly,the algorithm produces finite ascend steps.According to the analysis of the above three cases,we find the hybrid bundle algorithm for solving the dual problem of the routing selection problem in telecommunication network is of better convergence.Finally,based on the dual theories,the relationship of the optimal values between the dual problem and the original problem is given.