A Bundle Method For Minimax Problem

The minimax problem is one of an important non-differentiable optimization problems, itdoes not only has broader applications in engineering designing electronic microcircuitsprogramming、game theory and so on,but also has very close relationship with nonlinearequations、multiple objective programming、nonlinear programming.At present,there are some methods,e.g. line search method, SQP method, trust regionmethod and the active-set method, for solving minimax problems.For example,C.Charalambous and A.R.Conn gave the line search method. W.Murry and L.Overtonpresented the projection lagrange method. A.Vardi presented the trust region method with theactive-set．These methods have stronger theory conditions and narrower applications. Butnow, bundle method is recognized one of the most effective and promising methods forsolving non smooth optimization problems, and it has been successfully applied to manypractice fields. Therefore, in the paper,we consider to apply the bundle method to solveminimax problem.Application of bundle method to solve the problem is common practice:By usingsubgradient is generated by a linear function form of the objective function of a convex slicelinear approximation model. Application bundle method to solve the problem usually way isusing linear function from the subgradient.Then each iteration is by the solution of quadraticprogramming get the search direction. At the same time,using subgradient choice andbundle technology restrict storage times the number of gradient. Therefore, this paper isdivided into three sections.In section1we describe the common problems of mathematical programming model,and present general steps and algorithm of the application of the proposed method of thebundle method to solve the problem.In section2we introduce minimax problem, and using bundle method to solve minimaxproblem. And given descent rule, constructor method of subgradient set and algorithm ofiterative procedure, proved to make use of polymerization subgradient can reduce the iterationprocess the stored subgradient of information.In section3we prove the convergence theorem, it theoretically proved it is one of moregeneral and real and efficient algorithms.