A Feasible Bundle Method For Solving Inequality Constrained Minmax Problems

In real life,we often cannot simply consider only one kind of limitations or only one optimization goal when facing many problems,Instead,we can comprehensively consider multiple optimization goals to find an optimal solution under a variety of conditions.Just like two people playing chess,every time the opponent makes a move,a restriction condition is imposed on the player.Under such conditions,the player considers a variety of chess plans and looks for a plan that is most beneficial to himself.This idea is called game theory,and it is an important branch of operational research.The idea is also the origin of the minimax problems.This thesis mainly studies the minimax problem with inequality constraints(?)f(x)s.t.c(x)?0,where f(x)=max{fi(x),i?I},c(x)=max{cl(x),l?L}.Aiming at such problems,we first transform the constrained optimization problem into an unconstrained optimization problem by using the improved function,and then combine with the ideas of proximal bundle method to construct a quadratic programming sub-problem to solve.During this process,the incremental method,the component function selection mechanism and the bundle modification strategy are embedded.Then an overall algorithm for solving the original problem is proposed.Finally,the convergence analysis of the algorithm is given.The overall structure of this thesis is as follows:In chapter 1,some theorems and definitions related to non-smooth optimization problems and inequality constraint minimax problems are introduced,as well as several commonly used methods to solve non-smooth optimization problems,which lay a theoretical foundation for later research.In chapter 2,an optimization problem is studied that the objective function is a single function,and the constraint function is a maximum function.Firstly,we introduce the idea of the incremental method for the maximum function,which will greatly reduce the problem of excessive calculation of the bundle method.Then the proximal bundle method is combined with the improved function method to construct the sub-problem to generate the next trial point,at the same time,the sub-problem is solved in the dual space.Finally,the corresponding feasible bundle method is given to pave the way for further research in the third chapter.The third chapter is the main body of this thesis.It studies the optimization problem whose objective function and constraint function are the type of the maximum function.Firstly,we extend the problem-solving ideas in Chapter 2 and use the improved function to transform the constrained optimization problem into an unconstrained optimization problem.When defining the sub-gradient of the improvement function,the selection mechanism of the component function is added so that the selected component function has the same value as the maximum function at the point yj.Secondly,a bundle modification strategy for this problem is given.From the definition of the sub-gradient of the improved function,it can be deduced that the direction yk+1-yj is the descent direction of the function H xk(·)at the point yj,so we can find a "better" test point yj than the point yj.At the same time,we use two lemmas to prove that replacing the old point yj with a new point yj can still get an approximate optimal solution to the problem.At the end of this chapter,we give an algorithm with a bundle modification strategy for the original problem.The approximate optimal solution is obtained after applying the bundle modification strategy,in order to make the difference as small as possible the algorithm adds a bundle reset step to delete the elements in the bundle that increase the above difference,and then proceed to the next iteration.In chapter 4,we prove that the algorithm proposed in Chapter 3 is convergent whether it generates a finite number of descent steps(followed by zero steps)or it generates an infinite number of descent steps,the constructed algorithm has the property of global convergence.