An SQP Algorithm for Finely Discretized SIP Problems and Other Problems with Many Constraints

Abstract

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