A Feasible Descent Bundle Method For A Class Of Unconstrained Nonconvex Minimax Problems

Minimax problems are a special kind of nonsmooth optimization problems,and they are looking for "optimal" solution under the "worst" condition.The problems in the practical life have a wide range of applications,a lot of math problems can be solved by converting them to minimax problems under certain conditions.The methods for solving minimax problems with convex component functions has been relatively mature,but the nonconvex minimax problems remain to be studied further.In this thesis,a feasible descend bundle method for solving a class of unconstrained nonconvex minimax problems is studied.Firstly,the idea of redistribution bundle method is adopted to make component functions local convexification.Then the original subproblem is turned into quadratic programming subproblem by using the idea of approximate bundle method.After that,employing the dual space theory and combining the relationship between the original subproblem's and it's dual subproblem's optimal solution,the new iteration points are get.Afterwards the idea of incremental bundle method is used to reset the bundle set,expand the bundle set,or update and expand the bundle set.Then a feasible descent bundle method for solving a class of unconstrained nonconvex minimax problems is designed.Finally,the proposed algorithm's convergence is analyzed.There are four parts in this thesis,the main contents are showed as follows:In the first chapter,some basic concepts and theorems related to unconstrained nonconvex minimization problems are given at first.Secondly,the main ideas and concrete algorithms of the general bundle method are introduced.Finally,the basic principles of incremental bundle method are expounded.This chapter is the theoretical basis for the following chapters.In the second chapter,the main thoughts for a class of unconstrained nonconvex minimax problems are studied.Firstly,component functions are made local convexification by using the idea of redistribution bundle method,then a model function is constructed for the local convexification function by applying the cutting-plane technology.After that,the idea of the proximal bundle method is used to construct the quadratic programming subproblem which can be used to generate the next tentative point,and the study on the approximate solution of subproblem's expression and related properties is carried out.Afterwards the feasible strategies which can ensure the decrease of the objective function and feasibility of the iterative points are elaborated.Finally the update strategy of the bundle set is proposed.This chapter lays a foundation for the following algorithm structure.In the third chapter,a feasible descent bundle method is proposed for the class of unconstrained nonconvex minimax problems after synthesizing the theoretical framework in the previous chapters.After that,the basic framework and parameter setting for the algorithm are instruct,then the specific steps of the algorithm are given.In the end,some explanations about the algorithm are proposed.In the fourth chapter,the convergence of the feasible descent bundle algorithm for nonconvex unconstrained minimax problems is proved.At first,it is proved that the main iteration of the algorithm is terminated after finite times.Then the point satisfying the approximate optimal condition obtained after finite-times iterations is testified,at the same time the point is the approximate optimal solution of the original problem,thus the convergence of the algorithm is proved.