Research On Proximal Bundle Method For Utility Value Optimization Problem Of Train Timetable

The optimization problem of train timetable utility value studied in this thesis belongs to non-smooth optimization problems.Bundle method is one of the most practical,efficient and potential methods for solving non-smooth optimization problems.The initial bundle method is based on the cutting-planes method,which preserves the previous iterative information and uses the iterative information to establish an information bundle,while it is appended with the descent step detection.The advantage of the bundle method is that it combines the descent property of the steepest descent method and the stability of the black box method,which can guarantee the descent of the objective function and some certain stability property.This thesis discusses the optimization problem of train timetable utility value.After executing the Lagrangian relaxation of the objective function,we introduce the indicator function to transform the relaxed constrained problem into an unconstrained problem.Then the dual sub-problem of the train timetable utility value optimization problem is constructed by applying the dual theory and the proximal bundle method,and the explicit expression of the optimal solution of the dual sub-problem and some related conclusions are obtained.At last,the algorithm framework and relevant conclusions of the proximal bundle method for the optimization of train timetable utility values are presented,and the convergence analysis of the proposed algorithm is performed.The full text is divided into three parts,the main research contents are as follows:In the first chapter,the basic concepts involved in the research process of this thesis are given at first,and then some relevant methods for solving non-smooth optimization problems are presented: steepest descent method,subgradient method,cutting-planes method,bundle method and proximal bundle method,which lays the foundation for the subsequent research.In the second chapter,the dual problem of train timetable utility optimization is discussed.Firstly,the mathematical model of the utility value optimization problem of the train timetable is constructed,and the dual problem of the original problem is obtained by using the Lagrange relaxation method.Then,the dual problem is transformed into an unconstrained problem by using the indicator function,and the utility value sub-problem of the dual problem is constructed by adding quadratic terms and introducing control parameters to adjust the step size.Finally,according to the optimality conditions of the sub-problem,the explicit expression of its optimal solution is obtained,and some relevant conclusions of the corresponding utility value sub-problem of the dual problem are given.In the third chapter,the research focuses on the algorithm of the proximal bundle method of the dual problem of the train timetable utility value optimization problem.First of all,based on the previous discussion,the algorithm of the proximal bundle method for solving the dual problem of the train timetable utility optimization problem is given.Next,the corresponding algorithm is analyzed in depth,including the convergence analysis of the algorithm and the proof of relevant conclusions.In the part of convergence analysis,the discussion is mainly divided into two cases: case 1,the algorithm generates an infinite number of descent steps;case 2,the algorithm generates the last descent step,followed by an infinite number of null steps.In the process of analyzing and proving the convergence of the above two cases,we find that the proposed proximal bundle algorithm of the dual problem of the train timetable utility value optimization problem has good convergence property.