An Inexact Bundle Method For Solving The Routing Selection Problem In Telecommunication Networks

Routing selection problem in telecommunication networks is a concrete practical problem,which plays a vital role in internet optimization.However,in practical problems,the exact values of the function can not be obtained,and the implementation of the specific algorithm will become very difficult.Therefore,we consider disturbing the computation of function to make the application range of the algorithm wider.With this idea and motivation and noting that the real function values can not be obtained in practical calculation,based on Lemaréchal's application of bundle method to solve routing selection problem in telecommunication networks,this thesis adds disturbance to the exact function value in its dual model and constructs an inexact approximate function,so that the routing selection problem in telecommunication networks model can be applied to more cases and its practical value increases.Note that the objective function of the dual problem of routing selection problem in telecommunication networks includes two parts.We have added disturbance to one part in the early stage,and this thesis mainly considers adding disturbance to the other part.Then,the dual problem is transformed into an equivalent unconstrained optimization problem by using the indicator function.From the dual point of view,the explicit expression of the optimal solution of the primal problem and dual problem for the inexact approximate optimization model is studied,and some relevant conclusions for the inexact model are obtained.Then,the bundle algorithm based on inexact data for solving routing selection problem in telecommunication networks is presented,and the convergence analysis based on inexact information bundle algorithm is given.Finally,the relationship between the optimal solution of the primal problem and the dual problem is explored.In the first part,firstly some theoretical knowledge and specific concepts of nonsmooth optimization are given;Then,the specific algorithms of classical cutting-planes method,general bundle method,general bundle method's specific algorithm and some classical sub-problem models are introduced,which lays a theoretical foundation for subsequent research.In the second part,the basic model of routing selection problem in telecommunication networks is firstly introduced.Then,based on the original model,the construction of its inexact model is given.Finally,the indicator function is used to transform the dual problem of the inexact model of routing selection problem in telecommunication networks into an equivalent unconstrained optimization problem.The dual problem of its inexact model and the explicit expression of its optimal solution are studied,and some important corresponding conclusions are given.In the third part,an inexact bundle algorithm based on routing selection problem in telecommunication networks is introduced.Firstly,the setting of some parameters and the basic framework of the algorithm based on inexact data are given,and then the specific steps of the algorithm are presented.Compared with the existing algorithms,an inexact bundle algorithm is presented which is easier to implement for routing selection problem in telecommunication networks.Then,the convergence of the algorithm of the inexact model of routing selection problem in telecommunication networks is given.This paper expounds the convergence of the algorithm in the cases of infinitely many ascent steps and finitely many ascent steps(followed by infinitely many null steps),and the corresponding concrete proof process is discussed.In the fourth part,based on the fact that the optimal solution of the dual problem of the inexact model is related to the optimal solution of the primal problem,the optimal solution of the primal problem is explored.The discussion is also based on the two cases of infinitely many ascent steps and finitely many ascent steps(followed by infinitely many null steps).