A smoothing trust-region Newton-CG method for minimax problem

This paper presents a smooth approximate method with a new smoothing technique and a standard unconstrained minimization algorithm in the solution to the finite minimax problems. The new smooth approximations only replace the original problem in some neighborhoods of the kink points with a twice continuously differentiable function, its gradient and Hessian matrix are the combination of the first and the second order derivative of the original functions respectively. Compared to the other smooth functions such as the exponential penalty function, the remarkable advantage of the new smooth function is that the combination coefficients of its gradient and the Hessian matrix have sparse properties furthermore, the maximal possible difference value between the optimal values of the smooth approximate problem and the original one is determined by a fixed parameter selected previous. An algorithm to solve the equivalent unconstrained problem by using the trust-region Newton conjugate gradient method is proposed in the solution process finally, some numerical examples are reported to compare the proposed algorithm with SQP algorithm that implements in MATLAB toolbox and the algorithm in [E. Polak, J. O. Royset, R. S. Womersley, Algorithms with adaptive smoothing for finite minimax problems, Journal of Optimization Theory and Applications 119 (3) (2003) 459-484] based on the exponential penalty function, the numerical results prove that the proved algorithm is efficient. (c) 2008 Elsevier Inc. All rights reserved.