Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-013 (July 28, 2011)

A Regularized Explicit Exchange Method for Semi-Infinite Programs with an Infinite Number of Conic Constraints
by Takayuki Okuno, Shunsuke Hayashi and Masao Fukushima

pdf File

The semi-infinite program (SIP) is normally represented with infinitely many inequality constraints, and has been studied extensively so far. However, there have been very few studies on the SIP involving conic constraints, even though it has important applications such as Chebychev-like approximation, Filter design, and so on. In this paper, we focus on the SIP with a convex objective function and in finitely many conic constraints, called an SICP for short. We show that, under the Robinson constraint qualification, an optimum of the SICP satisfies the KKT conditions that can be represented only with a finite subset of the conic constraints. We also introduce two exchange type algorithms for solving the SICP. We first provide an explicit exchange method, and show that it has global convergence under the strict convexity assumption on the objective function. We then propose an algorithm combining a regularization method with the explicit exchange method, and establish the global convergence of the hybrid algorithm without the strict convexity assumption.