A projected conjugate gradient method for sparse minimax problems

A new method for nonlinear minimax problems is presented. The method is of the trust region type and based on sequential linear programming. It is a first order method that only uses first derivatives and does not approximate Hessians. The new method is well suited for large sparse problems as it only requires that software for sparse linear programming and a sparse symmetric positive definite equation solver are available. On each iteration a special linear/quadratic model of the function is minimized, but contrary to the usual practice in trust region methods the quadratic model is only defined on a one dimensional path from the current iterate to the boundary of the trust region. Conjugate gradients are used to define this path. One iteration involves one LP subproblem and requires three function evaluations and one gradient evaluation. Promising numerical results obtained with the method are presented. In fact, we find that the number of iterations required is comparable to that of state-of-the-art quasi-Newton codes.Research supported by The Nordic Council of Ministers, The Icelandic Science Council, The University of Iceland Research Fund and The Danish Natural Science Research Council.