Optimality and duality of semi-infinite programming

Semi-infinite programming – optimization in finite-dimensional spaces with infinitely many constraints – arises in various fields of engineering such as general approximation, resource allocation in decentralized systems, decision making under competition, multi-objective optimization, and filter design in signal processing. Since an infinite-dimensional constraint can be transformed into a single constraint with an optimal-value function under some conditions, semi-infinite programming can be regarded as a simple case of hierarchical optimization. In this sense, the theory of semi-infinite programming gives a fundamental background of general hierarchical mathematical programming. In this paper, we formulate convex semi-infinite programming problems in a functional analytic setting and explore the primal–dual structure underlying these problems by investigating their global duality and local differential properties. With assumptions that the constraint function is continuous with respect to its index parameter and that the index set is compact Hausdorff, we redefine the constraint function as an operator whose range is the Banach space consisting of continuous functions defined on the index set and equipped with the uniform norm. The order in the range space is given by a cone consisting of all nonnegative functions on the index set. A Karush–Kuhn–Tucker (KKT) type condition is given as an optimality condition for such a cone-constrained nonlinear programming problem, where the Lagrange multiplier is defined as a regular Borel measure on the index set. It is then shown that the set of multipliers satisfying the KKT type condition necessarily includes a measure with finite support unless it is empty. Hence any constraint qualification ensures the existence of such a discrete measure usually called the Haar measure. This observation justifies a classical result that can be traced back to Fritz John's 1948 paper. On the other hand, it is well known that strong duality holds for convex programming under Slater's constraint qualification. The corresponding dual problem for semi-infinite programming is then formulated in the space of finite signed regular Borel measures on the index set. The local KKT theory and the global duality theory are naturally related through the fact that the set of multipliers satisfying the KKT condition coincides with the set of solutions to the dual problem, which leads to an immediate consequence that the set of dual solutions always includes a measure with finite support under the Slater condition. Emphasis is also given to converse duality, i.e., how to retrieve primal information from dual information, especially for semi-infinite (not necessarily strictly) convex quadratic programming (hence including linear programming).