A Smoothing-Active Set Two-Stage Algorithm For Solving Finite Unconstrained Minimax Problems

The minimax problem is a typical non-smooth optimization problem,and has been widely applied in the fields of transportation,investment decision and game theory,etc.The smoothing algorithm is an effective algorithm to solve this problem,and the minimax problem is transformed into a series of smooth optimization problems with smoothing parameters,when the smoothing parameters tend to infinity,the solutions of the smooth optimization problems tend to a solution of the minimax problem.However,the smooth optimization problems become ill-conditioned for the large smoothing parameters,hence this paper gives an active set strategy for this ill-conditioning problem.For the linear minimax problems,based on the first order optimality conditions,the concept of the strongly active index set is introduced.In the active set strategy,the approximate solution is obtained by the smoothing algorithm,and a strongly active index set is obtained by solving a linear equation or solving a linear programming problem,then an optimal solution and its active index set are computed by an iterative process.Finally,the convergence of the smoothing-active set two-stage algorithm is established for the general linear minimax problems.Preliminary numerical experiments show that the two-stage algorithm is effective.For the non-linear minimax problems,based on the first order optimality conditions,the concept of the linearly independent active index set is introduced.In the active set strategy,the approximate solution is obtained by the smoothing algorithm,and a linearly independent active index set is obtained by solving a equation or solving a family of linear programming problems.Based on the linearly independent active index set,an equivalent smooth equations at the stable point is obtained,the equations are not ill-conditioned under certain conditions,so the Newton method can be used to solve the equations.Finally,under certain conditions,the convergence of the smoothing-active set two-stage algorithm is established.Preliminary numerical experiments show that the algorithm can obtain arbitrary precision solution for the problem satisfying certain conditions,and the approximate solution of the smoothing algorithm can be obtained from the smooth optimization problem corresponding to the small smoothing parameter,so the two-stage algorithm can effectively address the ill-conditioning problem of the smoothing algorithm.