×

An SQP algorithm for finely discretized continuous minimax problems and other minimax problems with many objective functions. (English) Zbl 0858.49027

SIAM J. Optim. 6, No. 2, 461-487 (1996); erratum ibid. 8, No. 1, 284-285 (1998).
A sequential quadratic programming (SQP) method for finely discretized continuous minimax problems is introduced and analyzed. The minimax problem is (P) \(\min\max_{\omega\in\Omega}\psi(x,\omega)\), where \(\Omega\) is a discrete set. In the \(k\)th iteration of the SQP method a descent direction is computed by selecting a smaller set \(\Omega_k\subset\Omega\) and solving a quadratic problem modeling (P) with \(\Omega\) replaced by \(\Omega_k\). If \(\Omega_k\) is significantly smaller than \(\Omega\), this leads to a significant reduction in the cost of computing search directions. A line search is used to ensure global convergence. The line search procedure, the update of the set \(\Omega_k\), and the update of the Hessian approximation used in the quadratic subproblem are coordinated. It is shown that under certain (standard) assumptions every accumulation point of the sequence generated by the SQP method is a Karush-Kuhn-Tucker point. Local convergence rates of the algorithm are proven. Numerical results are presented and the performance of the algorithm is compared with those of two other algorithms for this problem class.

MSC:

90C20 Quadratic programming
90C34 Semi-infinite programming
65K05 Numerical mathematical programming methods