An SQP Algorithm for Finely Discretized Continuous Minimax Problems and Other Minimax Problems with Many Objective Functions

A common strategy for achieving global convergence in the solution of semi-infinite programming (SIP) problems, and in particular continuous minimax problems, is to (approximately) solve a sequence of discretized problems, with progressively finer discretization meshes. Finely discretized minimax and SIP problems, as well as other problems with many more objectives/constraints than variables, call for algorithms in which successive search directions are computed based on a small but significant subset of the objectives/constraints, with ensuing reduced computing cost per iteration and decreased risk of numerical difficulties. In this paper, a sequential quadratic programming (SQP)-type algorithm is proposed that incorporates this idea in the particular case of minimax problems. The general case will be considered in a separate paper. The quadratic programming subproblem that yields the search direction involves only a small subset of the objective functions. This subset is updated at each iteration in such a way that global convergence is ensured. Heuristics are suggested that take advantage of a possible close relationship between “adjacent” objective functions. Numerical results demonstrate the efficiency of the proposed algorithm.