数理解析研究所講究録
第 1773 巻 2012 年 13-2313

無限個の錐制約付き半無限計画問題におけるKKT 条件の導出奥野 貴之 (Takayuki Okuno ) *林 俊介 (Shunsuke Hayashi) \dag er
福島 雅夫 (Masao Fukushima) \d ag er

京都大学大学院情報学研究科数理工学専攻
Department of Applied Mathematics and Physics
Graduate School of Informatics, Kyoto University

Abstract
The semi-infinite program (SIP) is normally represenfed 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, eventhough it has important applications such as Chebyshev-like approximation,filter design, and so on.
In this paper, we focus on the SIP with a convex objective function andinfinitely many conic constraints, called an SICP for short. We show that,
under Slater constraint qualification, an optimum of the SICP satisfies the
KKT conditions that can be represented only with a finite subset of the conic
constraints.
$s$

1

Introduction

In this paper, we focus on the following optimization problcm with an infinite $nu$ lrlberof conic constraints:

Minimize$f(x)$

subject to$A(t)^{T}x-b(t)\in C$(1.1)

for all $t\in T$ ,where :
is a continuously differentiable convex function,:and :are continuous functions,is a given compact set, andis a closed convex cone with nonempty interior. We call this problem thesemi-infinite conic program, SICP for short. Throughout this paper, we assume that
SICP (1.1) has a nonempty solution set.
$f$

$b$

$C\subset \mathbb{R}^{m}$

$*$

$A$

$\mathbb{R}^{n}arrow \mathbb{R}$$Tarrow \mathbb{R}^{m}$t-okuno@amp.i.kyoto-u.ac.jp

tshunhaya@amp.i.kyoto-u.ac.jp\ddagger fuku@amp.i.kyoto-u.ac.jp$T\subset \mathbb{R}^{\ell}$$Tarrow \mathbb{R}^{n\cross m}$

14
When $m=1$ and $C=\mathbb{R}_{+}:=\{z\in \mathbb{R}|z\geq 0\}$ , SICP (1.1) reduces to theclassical semi-infinite program (SIP) [3, 5, 7, 9, 10, 13], which has wide applications in engineering, e.g., the air pollution control, the robot trajectory planning, the stress of materials, etc.[7, 9]. So far, many algorithms have been proposed for solving SIPs, such as the discretization method [3], the local reduction
based method [4, 8, 14] and the exchange method [5, 6, 13]. A more general
choice foris the symmetric cone such as the second-order cone (SOC)althe semi-definite cone$C$$\mathcal{K}^{m}$$1d$$\{(z_{1}, z_{2}, \ldots, z_{m})^{T}\in \mathbb{R}^{m}|z_{1}\geq\Vert(z_{2}, z_{3}, \ldots, z_{m})^{T}\Vert_{2}\}$$\{Z\in \mathbb{R}^{mxm}|Z=Z^{T}, Z\succeq 0\}$$S_{+}^{m}$

$:=$

$:=$

.

There are some important applications of SICP (1.1). For example, when is an
SOC, SICP (1.1) can be used to formulate a Chebyshev-like approximation problem
involving vector-valued functions. Specifically, letbe a given compact set,
$F$
:
and
:
and
be given functions. Then, we want todetermine a parametersuch that $\Phi(y)\approx F(u, y)$ for all $y\in Y$ . One relevant
approach is to solve the following problem:$C$$Y\subseteq \mathbb{R}^{n}$$\Phi$$\mathbb{R}^{\ell}\cross Yarrow \mathbb{R}^{m}$$Yarrow \mathbb{R}^{m}$$u\in \mathbb{R}^{p}$

Minimizeu$\max_{y\in Y}\Vert\Phi(y)-F(u, y)\Vert_{2}$By introducing the auxiliary variable
to$Minimu,r$ize

subject to$r\in \mathbb{R}$.

, we can transform the above problem$r$$(\begin{array}{ll} r\Phi(y)- F(u,y)\end{array})\in \mathcal{K}^{m+1}$

for all $y\in Y$,

which is of the form (1.1) when $F$ is affine with respect to .
The main purpose of the paper is to study the Karush-Kuhn-Tucker (KKT)
conditions for SICP (1.1). Although the original KKT conditions for SICP (1.1)
could be described by means of integration and Borel measure, we show that they
can be represented by a finite number of elements in under Slater constraint
qualification.
Throughout the paper, we use the following notations.
denotes the Euclidean$:=\sqrt{z^{T}z}$
norm defined by
.
given
For a
for
cone
denotes$:=\{z\in \mathbb{R}^{m}|z^{T}w\geq 0, \forall w\in C\}$ . For vectors
the dual cone defined by, the conic complementarity condition, $z^{T}w=0,$ $z\in C$ and $w\in C^{d}$ ,andis also written as $C\ni z\perp w\in C^{d}$ . For a nonempty set
and a function$D$$\arg\min_{z\in D}h(z)$ denotes the set of minimizers of:over . In addition,$\delta>0,$
foranddenotes the closed ball with center and radius, i.e., $B(z, \delta):=\{w\in \mathbb{R}^{m}|\Vert w-z\Vert\leq\delta\}$ .
$u$

$T$

$s$

$\Vert\cdot\Vert$$z\in \mathbb{R}^{m}$$\Vert z\Vert$$C\subseteq \mathbb{R}^{m},$$C^{d}$$C^{d}$$z\in \mathbb{R}^{m}$$w\in \mathbb{R}^{m}$$D\subseteq \mathbb{R}^{m}$

$h$

$h$

$\mathbb{R}^{m}arrow \mathbb{R},$$z\in \mathbb{R}^{m}$$B(z, \delta)\subseteq \mathbb{R}^{m}$$z$$\delta$2

Karush-Kuhn-Tucker Conditions

In this section, we provide the optimality conditions for SICP (1.1). When $m=1$
and, SICP (1.1) reduces to the classical semi-infinite program and the
optimality conditions are given as follows [9, Theorem 2].
$C=\mathbb{R}_{+}$

15
Let be an optimum of SICP (1.1) with $m=1$ and. Supposethat the Slater constraint qualification holds for SICP (1.1) with,
$A(t)^{T}x_{0}-b(t)>0(\forallt\inT)$i.e., there exists ansuch that. Then,$t_{p}\in T$ such that $p\leq n$ andthere exist elements$C=\mathbb{R}_{+}$$\overline{x}$$C=\mathbb{R}_{+}$$x_{0}\in \mathbb{R}^{n}$$p$$t_{2},$$t_{1},$$\ldots,$$\nabla f(\overline{x})-\sum_{i=1}^{p}\eta_{i}A(t_{i})=0$,$\mathbb{R}_{+}\ni\eta_{i}\perp A(t_{i})^{T}\overline{x}-b(t_{i})\in \mathbb{R}_{+}(i=1,2, \ldots,p)$

.

(2.1)

In this section, we define the generalized Slater constraint qualification (GSCQ),
and show that the optimality conditions can be represented with finitely many conic
constraints under the GSCQ.
This section consists of two subsections. In Subsection 2.1, we define the GSCQ
and the generalized Abadie constraint qualifications (GACQ) and show that the
GACQ holds under the GSCQ. In Subsection 2.2, we derive the optimality conditionsfor SICP (1.1) by using the results of Subsection 2.1 and Carath\’eodory‘s Theorem.
Before going to the subsections, we provide some propositions, which play important roles in proving the propositions and theorems.
Proposition 2.1. [11] Let$C\subseteq \mathbb{R}^{n}$be an arbitrary nonempty cone. Then, we have$C^{dd}=c1$

Particularly, when$C$

Proof. Choose$C$is a closed convex cone, we have $C=C^{dd}$ .

Proposition 2.2. Let
Then, we have$x\in$

co .

$D\subseteq \mathbb{R}^{n}$be an arbitmry convex set with nonempty interior.

int $D,$ $y\in$ cl $D,$ $\lambda\in[0,1)$$\Rightarrow$$(1-\lambda)x+\lambda y\in$int D.

(2.2)

int $D,$ $y\in$ cl $D$ and $\lambda\in[0,1)$ arbitrarily. We will show that
there exists ansuch that $(1-\lambda)x+\lambda y+B(0, \epsilon)\subseteq D$ , where $B(0, \in)$ $:=\{x\in$. From $y\in$ cl $D$ , we have $y\in D+B(0, \epsilon)$ for any. Therefore,by choosing a sufficiently small, we have$x\in$$\epsilon>0$$\epsilon>0$$\mathbb{R}^{n}|\Vert x\Vert\leq\epsilon\}$$\epsilon>0$$(1-\lambda)x+\lambda y+B(0, \epsilon)\subseteq(1-\lambda)x+\lambda(D+B(0, \epsilon))+B(0, \epsilon)$$=(1-\lambda)(x+(1-\lambda)^{-1}(1+\lambda)B(0, \epsilon))+\lambda D$$\subseteq(1-\lambda)D+\lambda D=D$,

where the equalities hold since $\alpha X+\beta X=(\alpha+\beta)X$ for any
convex set $X$ , and the last inclusion is due to $x\in$ int D.

2.1$\alpha,$$\beta\geq 0$

and any$\square$Generalized Slater and Abadie constraint qualifications

In the case of the convex optimization problem with finitely many lequality constraints, it is known that Abadie’s constraint qualification holds under Slater constraint qualification, and then the KKT conditions serve as a necessary and sufficient$i\iota$$s$16condition for the global optimality [1]. In this subsection, we define the generalized
Slater and Abadie constraint qualifications (GSCQ and GACQ) for SICP (1.1). andshow that the GACQ always holds under 1 GSCQ. Let be an arbitrary feasible
solution of SICP (1.1), and be the feasible solution set of SICP (1.1), that is,$t1$,$\overline{x}$$(^{\backslash }$$S$$S:=\{x\in \mathbb{R}^{n}|A(t)^{T}x-b(t)\in C(\forall t\in T)\}$.

We define the following cones:$G_{t}(\overline{x}):=\{\alpha(A(t)^{T}\overline{x}-b(t))|\alpha\leq 0\}$$\Lambda_{t}(\overline{x}):=C+G_{t}(\overline{x})$

,
(2.3)

,

$C_{t}(\overline{x}):=\{y\in R^{n}|A(t)^{T}y\in cl\Lambda_{t}(\overline{x})\}$$C_{S}( \overline{x}):=\bigcap_{t\in T}C_{t}(\overline{x})$

(2.4)

,

.

(2.5)

, and theWe Ilotc that the closure ofis the tangent cone of atdual cone ofcharacterizes the directions satisfying the conic complementarity.
conditions for, i.e.,(See Proposition 2.9 below.) Also,is a generalization of the linearized coneas defined in [2], for the case where $|T|<\infty$ and.
Now, we define GSCQ and GACQ by using thc above cones.
$C$$\Lambda_{t}(\overline{x})$$A(t)^{T}\overline{x}-b(t)$$\Lambda_{t}(\overline{x})$$A(t)^{T}\overline{x}-b(t)$$\Lambda_{t}(\overline{x})^{d}=\{y\in \mathbb{R}^{m}|C\ni y\perp A(t)^{T}\overline{x}-b(t)\in C\}$
$C_{S}(\overline{x})$$C=\mathbb{R}_{+}$

Definition 2.3 (GSCQ). We say that the generalized Slater constmint qualification(GSCQ) holds for SICP (1.1) if there exists somesuch that$x_{0}\in \mathbb{R}^{n}$$A(t)^{T}x_{0}-b(t)\in$(2.6)

int $C(\forall t\in T)$ .

be the feasible set and a feasible solution
Definition 2.4 (GACQ). Let and$(l.l)$
Then,
say
,
we
that the genemlized Abadie constraint
respectively.
SICP
of
$S$

qualification $GACQ$ holds at$\overline{x}\in S$$\overline{x}\in S$

if$C_{S}(\overline{x})\subseteq T_{S}(\overline{x})$where$C_{S}(\overline{x})$is defined by (2.5) and$T_{S}(\overline{x})$

,

(2.7)

is the tangent cone to

$S$

at .
$\overline{x}$Next, we show that the GACQ holds under the GSCQ. To this end, we show thefollowing two lemmas by using the following set:
$C_{\mathring{s}}(\overline{x})$$:= \bigcap_{t\in T}\{y\in \mathbb{R}^{n}|A(t)^{T}y\in$Notice that

$C_{\mathring{S}}(\overline{x})$int$C+G_{t}(\overline{x})\}$

.

(2.8)

is not empty for the GSCQ.

Lemma 2.5. Assume that the GSCQ holds for SICP (1.1). Let be an arbitmry
be defined by (2.5) and (2.8),
andfeasible solution of SICP (1.1). Let
respectively. Then,.
cl
is nonempty and$\overline{x}$$C_{S}(\overline{x})$$C_{\mathring{s}}(\overline{x})$$C_{\mathring{S}}(\overline{x})$$C_{S}(\overline{x})=$$C_{s}^{o}(\overline{x})$17
Proof. If we haveclcl

, thenmust be nonempty since.
So, we only show
. Notice that
. Then, we havecl, sinceis closed. Thus, it suffices to showcl.
Let
be chosen arbitrarily. Then, we have to show that there exists somesuch that $y^{k}arrow y$ as $karrow\infty$ . By the GSCQ, there is ansuch that $A(t)^{T}x_{0}-b(t)\in$ int for any $t\in T$ . Let. Then, we have$A(t)^{T}y_{0}=(A(t)^{T}x_{0}-b(t))-(A(t)^{T}\overline{x}-b(t))\in$ int. Since int
is an open convex set, we have
$C_{S}(\overline{x})=$$C_{\mathring{S}}(\overline{x})$$C_{S}(\overline{x})=$$C_{S}(\overline{x})\supseteq$$C_{\mathring{S}}(\overline{x})$$0\in C_{S}(\overline{x})$$C_{S}^{o}(\overline{x})$$C_{S}(\overline{x})\supseteq C_{\mathring{S}}(\overline{x})$$C_{\mathring{s}}(\overline{x})$$C_{S}(\overline{x})$$C_{S}(\overline{x})\subseteq$$C_{\mathring{s}}(\overline{x})$$y\in C_{S}(\overline{x})$$\{y^{k}\}\subseteq C_{\mathring{S}}(\overline{x})$$x_{0}\in \mathbb{R}^{n}$$C$$y_{0}$$:=x_{0}-\overline{x}$$C+G_{t}(\overline{x})$$A(t)^{T}y_{0}\in$for any $t\in T$ . Since
we haveint$y\in C_{S}(\overline{x})$$C+G_{t}(\overline{x})=$and cl$A(t)^{T}y\in$Applying Proposition 2.2 with
$y:=A(t)^{T}y$ , we have

$D$

$:=$

int int$\Lambda_{t}(\overline{x})=$cl int
$($

int

$($

$C+G_{t}(\overline{x}))$.

cl $(C+G_{t}(\overline{x}))=$ cl int$($$C+G_{t}(\overline{x}))$$C+G_{t}(\overline{x}),$$A(t)^{T}((1-\eta)y+\eta y_{0})\in$$C+G_{t}(\overline{x})$

int

$x$

$C+G_{t}(\overline{x}))^{1}$,.
$:=A(t)^{T}y_{0},$$\lambda$$:=1-\eta$ and(2.9)$C+G_{t}(\overline{x})$for any $t\in T$ and $\eta\in(0,1]$ . Let
be a sequence such that$:=(1-\eta_{k})y+\eta_{k}y_{0}$andbe defined by. Then, (2.9) implies that $A(t)^{T}y^{k}\in$int
for any and $t\in T$ . Therefore,
and.
$\{\eta_{k}\}\subseteq(0,1]$$\{y^{k}\}$$\lim_{karrow\infty}\eta_{k}=0$$y^{k}$$k$$C+G_{t}(\overline{x})$$\lim_{karrow\infty}y^{k}=y$$\{y^{k}\}\subseteq C_{\mathring{s}}(\overline{x})$This completes the proof.

$\square$Lemma 2.6. Assume that the GSCQ holds for SICP (1.1). Let
and $t\in T$ , letfeasible solution of SICP (1.1). For$y\in \mathbb{R}^{n}$$\alpha_{y}(t)\in \mathbb{R}$.

$\alpha_{y}(t):=\max_{\alpha\in[0,1]}\{\alpha|A(t)^{T}(\overline{x}+\alpha y)-b(t)\in C\}$

Then, for any$y\in C_{\mathring{S}}(\overline{x})$be an arbitmry
be defined by(2.10), we have$\inf_{t\in T}\alpha_{y}(t)>0$

Proof. Let$\overline{x}$.

and $t\in T$ be chosen arbitrarily. First note that,since is feasible to SICP (1.1). Then. we first prove $\alpha_{y}(t)>0$ . To this end, it
suffices to show the existence of $\alpha\in(0,1]$ such that$y\in C_{\mathring{s}}(\overline{x})$$\alpha_{y}(t)\geq 0$$\overline{x}$$A(t)^{T}(\overline{x}+\alpha y)-b(t)\in$

Since
of

, we have $A(t)^{T}y\in$ int
implies the existence of some$y\in C_{\mathring{S}}(\overline{x})$$G_{t}(\overline{x})$$C+G_{t}(\overline{x})$$\beta\geq 0$

int C.

, which together with the definition

such that$\beta(A(t)^{T}\overline{x}-b(t))+A(t)^{T}y\in$When $\beta=0,$ $(2.12)$ reduces to $A(t)^{T}y\in$ int
and Proposition 2.2 implies$C$(2.11)

int C.

(2.12), which together with $A(t)^{T}\overline{x}-b(t)\in C$$\frac{1}{2}A(t)^{T}y+\frac{1}{2}(A(t)^{T}\overline{x}-b(t))=\frac{1}{2}(A(t)^{T}(\overline{x}+y)-b(t))\in$This equality can be obtained easily from the fact that cl (int )$\overline{1}$
$C$

$=C$

18
, and hence, $A(t)^{T}(\overline{x}+y)-b(t)\in$ int $C$ . We thus have (2.11) with $\alpha=1$ . When$\beta>0$ , by multiplying (2.12) by, we have $A(t)^{T}(\overline{x}+\beta^{-1}y)-b(t)\in$ int $C$ . Dueto Proposition 2.2, we have $A(t)^{T}(\overline{x}+sy)-b(t)\in$ int $C$ for any $s\in(0, \beta^{-1}]$ , which
implies $A(t)^{T}( \overline{x}+\min(\beta^{-1},1)y)-b(t)\in$ int $C$ . Hence, we also have (2.11).

int

$C$

$\beta^{-1}$. Suppose to the contrary that there
In what follows, we show
as $karrow\infty$ . Let be an arbitrary
exists a sequencesuch that. Then, by taking an appropriate subsequence, we haveaccumulation point of$\inf_{t\in T}\alpha_{y}(t)>0$$\alpha_{y}(t^{k})arrow 0$$\{t^{k}\}\subseteq T$$t^{*}$$\{t^{k}\}$$\lim_{karrow\infty}t^{k}=t^{*}$,.

(2.13)

int C.

(2.14)$\lim_{karrow\infty}\alpha_{y}(t^{k})=0$

From (2.11), there exists an a $>0$ such that$A(t^{*})^{T}(\overline{x}+\overline{\alpha}y)-b(t^{*})\in$

Hence, by the continuity of functions

and , we have

$A$

$b$

$A(t^{k})^{T}(\overline{x}+\overline{\alpha}y)-b(t^{k})\in$

int(2.15)$C$

sufficiently large. From (2.15) and (2.10). we havetogether with (2.13) implies. However, this contradicts

for all$k$$0<\overline{\alpha}\leq\alpha_{y}(t^{k})$$\overline{\alpha}=0$$\overline{\alpha}>0$, which. Hence, wehave $\inf_{t\in T}\alpha_{y}(t)>0$ .
口Now, we show the main theorem of this section, which claims that the GSCQ
implies the GACQ for SICP (1.1).

Theorem 2.7. Let be an arbitmry feasible solution of SICP (1.1). Assume that
the GSCQ holds. Then, the $GACQ$ holds at .
$\overline{x}$$\overline{x}$Proof. Letfrom Lemmabe defined by (2.8). Then we have cl, we only have to show
2.5. Therefore, due to the closedness of$C_{s}^{O}(\overline{x})=C_{S}(\overline{x})$$C_{\mathring{S}}(\overline{x})$$T_{S}(\overline{x})$$C_{\mathring{S}}(\overline{x})\subseteq T_{S}(\overline{x})$Letbe chosen arbitrarily and(2.10). Then, we have$y\in C_{S}^{o}(\overline{x})$.

$\alpha_{y}:=\inf_{t\in T}\alpha_{y}(t)$, where$\alpha_{y}(t)$is given by(2.16)$A(t)^{T}(\overline{x}+\beta y)-b(t)\in C$

for any
and $t\in T$ , since $A(t)^{T}\overline{x}-b(t)\in C$ and. Hence, we can choose
By Lemma 2.6, we have
. By (2.16), we have$\beta\in[0, \alpha_{y}]$$\alpha_{y}>0$$C$

is convex.

$\{b_{k}\}\subseteq(0, \alpha_{y}]$such that$\lim_{karrow\infty}b_{k}=0$$A(t)^{T}(\overline{x}+b_{k}y)-b(t)\in C$

which implics
by$\overline{x}+b_{k}y\in S$$(\forall t\in T)$

for all . Now, recall that the definition of$k$$T_{S}( \overline{x}):=\{y\in \mathbb{R}^{n}|\lim_{karrow\infty}a_{k}(x_{k}-\overline{x})=y,\lim_{karrow\infty}x_{k}=\overline{x},$Thus, by setting
completed.

$x_{k}$,$:=\overline{x}+b_{k}y$and$a_{k}$$:=1/b_{k}$$x_{k}\in S,$, we have$T_{S}(\overline{x})$is given$a_{k}\geq 0(k=1,2, \ldots)\}$$y\in T_{S}(\overline{x})$(2.17). The proof is
口

.

19
2.2

The KKT conditions for SICPAs we have shown in the previous subsection, the GACQ holds under the GSCQ.
In this subsection, by using this result, we show that the optimality condition for
SICP (1.1) can be represented as the KKT conditions with finitely many conic constraints. It is well known that the following Carath\’eodory‘s Theorem plays a significant role in deriving the optimality condition for the ordinary SIP with inequality
constraints. The theorem is also important in deriving the optimality conditions for
SICP (1.1).
Lemma 2.8. (Carath\’eodory‘s Theorem [11, Theorem 17.1]) Let
be anarbitmry nonempty set, and co $D$ be the convex hull of D. Then, for any $x\in$ co ,$s_{p}\in D$ andthere exist elements
positive numbers
such that $p\leq n+1,$, and.
$D\subseteq \mathbb{R}^{n}$

$D$

$p$

$s_{1},$$s_{2},$$p$$\ldots,$$\sum_{i=1}^{p}\lambda_{i}=1$$\lambda_{1},$$\lambda_{2},$$\ldots,$$\lambda_{p}>0$$x=\lambda_{1}s_{1}+\lambda_{2}s_{2}+\cdots+\lambda_{p}s_{p}$The conic complementarity condition that appears in the KKT conditions is
written as $C\ni y(t)\perp A(t)^{T}x-b(t)\in C$ with a Lagrange multiplier vector $y(t)$ .
The next proposition claims that the dual cone ofdefined by (2.3) characterizes
the Lagrange multiplier $y(t)$ .
$\Lambda_{t}(\overline{x})$Proposition 2.9. Let $t\in T$ be chosen arbitrarily, and be an arbitmry feasible
solution of SICP (1.1). Let
be defined by (2.3). Then, we have$\overline{x}$$\Lambda_{t}(\overline{x})$$\Lambda_{t}(\overline{x})=co(C\cup G_{t}(\overline{x}))$,$\Lambda_{t}(\overline{x})^{d}=C\cap G_{t}(\overline{x})^{d}$$=\{y\in \mathbb{R}^{m}|C\ni y\perp A(t)^{T}\overline{x}-b(t)\in C\}$.

20
Now, in order to obtain the optimality condition for SICP (1.1), we introduce
the following cones:$H_{t}(\overline{x}):=\{z\in \mathbb{R}^{n}|z=A(t)\lambda_{J}.\lambda\in\Lambda_{t}(\overline{x})^{d}\}$$H( \overline{x}):=\bigcup_{t\in T}H_{t}(\overline{x})$,(2.18)(2.19),

where $t\in Ta1$ 1
is a feasible solution. Note thatis a convex cone but may
not be closed, andis a cone but may not be closed or convex.
.
The next proposition shows the relation between
and$d\overline{x}$$H_{t}(\overline{x})$$H_{t}(\overline{x})$$H(\overline{x})$$C_{S}(\overline{x})$Proposition 2.10. Let
be an arbitrary feasible solution of SICP $(l.l)$ . Letandbe defined by (2.5) and (2.19), respectively. Then, we have$\overline{x}\in S$$H(\overline{x})$$C_{S}(\overline{x})$$C_{S}(\overline{x})^{d}\subseteq clcoH(\overline{x})$Proof. It suffices to prove$C_{S}(\overline{x})\supseteq H(\overline{x})^{d}$arbitrarily. Since
and$\{y, A(t)\lambda\}\geq 0$ . Note that $t\in T$ andwe havecl co.
$y\in H(\overline{x})^{d}$$A(t)^{T}y\in\Lambda_{t}(\overline{x})^{dd}=$. Choose.

$y\in H(\overline{x})^{d},$$t\in T$and$\lambda\in\Lambda_{t}(\overline{x})^{d}$, we havewere chosen arbitrarily. Therefore,clfor any $t\in T$ , which implies$\langle A(t)^{T}y,$$A(t)\lambda\in H_{t}(\overline{x})\subseteq H(\overline{x})$$\lambda\rangle=$$\lambda\in\Lambda_{t}(\overline{x})^{d}$$\Lambda_{t}(\overline{x})=$$\Lambda_{t}(\overline{x})$口$y\in C_{S}(\overline{x})$The following lemma is also important for the proof of the subsequent theorem.

Lemma 2.11. Assume that the GSCQ holds for SICP (1.1). Let
be an arbitmry
point satisfying (2.6) and $z\in C$ be an arbitrary vector. Then, there exists somesuch that$x_{0}$$\epsilon>0$(2.20)$(A(t)^{T}x_{0}-b(t))^{T}z\geq\epsilon\Vert z\Vert$

for any $t\in T$ .
Proof. For simplicity, let $y(t)$ $:=A(t)^{T}x_{0}-b(t)$ . When $z=0$ , inequality (2.20)

holds obviously for any $t\in T$ . So we only consider the case where $z\neq 0$ . Let$\delta(t):=\frac{y(t)^{T}z}{\Vert z\Vert}$.

(2.21)To show (2.20). it suffices to prove $i_{I}1f_{t\in T}\delta(t)>0$ . Suppose thatforcontradiction. Then, we must have $\inf_{t\in T}\delta(t)=0$ since $y(t)\in$ int $C$ and $z\in C$
implies $\delta(t)\geq 0$ . Due to the compactness of , there exist some subsequenceand. Moreover,
and $t^{*}\in T$ such thatthe continuity of $y(t)$ yields $\lim_{karrow\infty}y(t^{k})=y(t^{*})$ . Then, by (2.21), we obtain$y(t^{*})^{T}z=0$ . However, this contradicts $0\neq z\in C$ and $y(t^{*})\in$ int $C$ . Therefore, we$\inf_{t\in T}\delta(t)\leq 0$$T$$\{t^{k}\}\subseteq T$

have $\inf_{t\in T}\delta(t)>0$ .

$\lim_{karrow\infty}\delta(t^{k})=0$$\lim_{karrow\infty}t^{k}=t^{*}$

口Now, we are in the position to show the theorem on the optimality condition for
SICP (1.1).

21
Theorem 2.12 (Optimality condition). Assume that the GSCQ holds for SICP
(1.1). Let
be an arbitmry optimizer of SICP (1.1). Then, there exist
andsuch that $p\leq n+1$ and$x^{*}$$T$$y_{1},$$y_{2},$$t_{1},$$\ldots,$$\ldots,$$t_{p}\in$$y_{p}\in \mathbb{R}^{m}$$\nabla f(x^{*})-\sum_{i=1}^{p}A(t_{i})y_{i}=0$,(2.22)$C\ni y_{i}\perp A(t_{i})^{T}x^{*}-b(t_{i})\in C(i=1,2, \ldots,p)$

Proof. From$t_{2},$.

(2.23)and [12, Theorem 3.6], we have.
$hol(ls$$H(x^{*})$
Also we have
, where the first inclusion
cl co
since
from Theorem 2.7, and the second inclusion follows from
Proposition 2. 10. Therefore, we have$x^{*} \in\arg\min_{x\in S}f(x)$$\nabla f(x^{*})\in T_{S}(x^{*})^{d}$$T_{S}(x^{*})^{d}\subseteq C_{S}(x^{*})^{d}\subseteq$$C_{S}(x^{*})\subseteq T_{S}(x^{*})$,$\nabla f(x^{*})\in clcoH(x^{*})$

which indicates the existence of a sequence$\{z^{k}\}\subseteq$$\lim_{karrow\infty}z^{k}=\nabla f(x^{*})$

co $H(x^{*})$ such that.

By Lemma 2.8, (2.18) and (2.19), there exist $n+1$ nonnegative scalars2
such that
and$0$$\alpha_{n+1}^{k}\geq$$\alpha_{1)}^{k}\alpha_{2}^{k},$$\ldots,$$\sum_{i=1}^{n+1}\alpha_{i}^{k}=1$$z^{k}= \sum_{i=1}^{n+1}A(t_{i}^{k})\alpha_{i}^{k}\lambda_{i}^{k}$,$\lambda_{i}^{k}\in\Lambda_{t_{i}^{k}}(x^{*})^{d}$(2.24).

Denotefor each in (2.24).
In what follows, we show that the sequenceis bounded and any accumulation point satisfies (2.22) and (2.23). From the GSCQ, there exists an
such
that
int for each . By
and Lemma 2.11,
there exists
such that$y_{i}^{k}$$i$$:=\alpha_{i}^{k}\lambda_{i}^{k}\in\Lambda_{t_{i}^{k}}(x^{*})^{d}$$\{y_{i}^{k}\}$$x_{0}\in \mathbb{R}^{n}$$A(t_{i}^{k})^{T}x_{0}-b(t_{i}^{k})\in$

$C$

$i$

$y_{i}^{k}\in\Lambda_{t_{i}^{k}}(x^{*})^{d}\subseteq C$$\epsilon>0$$\{y_{i}^{k}, A(t_{i}^{k})^{T}x_{0}-b(t_{i}^{k})\}\geq\epsilon\Vert y_{i}^{k}\Vert$for each . Since$i$$y_{i}^{k}\in\Lambda_{t_{i}^{k}}(x^{*})^{d}\subseteq G_{t_{i}^{k}}(x^{*})^{d}$$\langle y_{i}^{k},$(2.25)

from Proposition 2.9, we have$A(t_{i}^{k})^{T}x^{*}-b(t_{i}^{k})\}\leq 0$(2.26).

It, then, follows from (2.26) and (2.25) that$\{y_{i}^{k},$$A(t_{i}^{k})^{T}(x_{0}-x^{*})\rangle\geq\epsilon\Vert y_{i}^{k}\Vert$.

(2.27)

From (2.24), (2.27) and, we have. Moreover, since
is convergent, there exists $M>0$ such$(z^{k})^{T}(x_{0}-x^{*})\leq
M$that
for all . Therefore, we have$(z^{k})^{T}(x_{0}-x^{*})= \sum_{i=1}^{n+1}\{y_{i}^{k},$ $A(t_{i}^{k})^{T}(x_{0}-$$y_{i}^{k}=\alpha_{i}^{k}\lambda_{i}^{k}$$x^{*}) \rangle\geq\sum_{i=1}^{n+1}\epsilon\Vert y_{i}^{k}\Vert$$\{z^{k}\}$$k$$M \geq\epsilon\sum_{i=1}^{n+1}\Vert y_{i}^{k}\Vert$.

2If we have $p<n+1$ scalars, then we can set $\alpha_{p+1}^{k}=\alpha_{p+2}^{k}=\cdots=\alpha_{n+1}^{k}=0$ without loss ofgenerality.

22
which implies the boundedness of. Now, let and be arbitrary accumulation
points of, respectively. Then there exist subsequences such thatand$n+1$ . From (2.24) withandfor each $i=1,2,$
and the continuity of function , we obtain.
Hence, we have (2.22). Fromand Proposition 2.9, it follows thatfor each . Since is closed, we have $y_{i}\in C$ and$A(t_{i})^{T}x^{*}-b(t_{i})\in C$ . Moreover, we have$A(t_{i})^{T}x^{*}-b(t_{i})\}=0$ , since the function$A(t)^{T}x^{*}-b(t)\}$ is continuous at any
defined by
and $t\in T$ .
Therefore, (2.23) is obtained.
$\{y_{i}^{k}\}$$\{y_{i}^{k}\}$$z^{k}arrow\nabla f(x^{*}),$$t_{i}$$y_{i}$$\{t_{i}^{k}\}$$t_{i}^{k}arrow t_{i}$$y_{i}^{k}arrow y_{i}$$\ldots,$$A$$y_{i}^{k}=\alpha_{i}^{k}\lambda_{i}^{k}$$\nabla f(x^{*})=\sum_{i=1}^{n+1}A(t_{i})y_{i}$$y_{i}^{k}\in\Lambda_{t_{i}^{k}}(x^{*})^{d}$$C\ni y_{i}^{k}\perp A(t_{i}^{k})^{T}x^{*}-b(t_{i}^{k})\in C$

$k$

$C$

$\langle y_{i},$$\theta(y, t)$$:=\langle y,$$y\in \mathbb{R}^{m}$$\square$3

Concluding remarks

For the semi-infinite program with an infinite number of conic constraints (SICP),
we have shown that the KKT conditions can be represented with finitely many conic
constraints, as long as the Slater constraint qualification holds. It is an interesting
subject of future research to extend the result to the more general SICP without
the convexity assumption on the objective and constraint functions.

References[1] M. S. Bazaraa and C. M. Shetty. Foundations of optimization, volume 122of Lecture Notes in Economics and Mathematical Systems. Springer-Verlag,
Berlin, Heidelberg, New York, 1976.
[2] G. Giorgi, A. Guerraggio, and J. Thierfelder. Mathematics of optimization:
Smooth and Nonsmooth Case. Elsevier Science, 2004.
[3] M. A. Goberna and M. A. $L6pez$ . Semi-infinite Progmmming: Recent Advances.
Kluwer Academic Publishers, Dordrecht, 2001.
[4] G. Gramlich, R. Hettich, and E. W. Sachs. Local convergence of SQP methods
in semi-infinite programming. SIAM Joumal on optimization, 5:641-658, 1995.
[5] H. C. Lai and S.-Y. Wu. On linear semi-infinite programming problems. Numerical Functional Analysis and optimization, 13:287-304, 1992.

[6] S. Hayashi, T. Yamaguchi, N. Yamashita, and M. Fukushima. A matrixsplitting method for symmetric affine second-order cone complementarity problems. Journal of Computational and Applied Mathematics, 175:335-353, 2005.

[7] R. Hettich and K. $0$ . Kortanek. Semi-infinite programming: Theory, methods,
and applications. SIAM Review, 35:380-429, 1993.
[8] C. Ling, L. Qi, G. L. Zhou, and S.-Y. Wu. Global convergence of a robustsmoothing SQP method for semi-infinite programming. Joumal of optimization
Theow and Applications, 129:147-164, 2006.

23[9] M. $L6pez$ and G. Still. Semi-infinite programming. European Journal of Operational Research, 180:491-518, 2007.

[10] R. Reemtsen and J. R\"uckmann. Semi-infinite Programming. Kluwer Academic
Publishers, Boston, 1998.
[11] R. T. Rockafellar. Convex Analysis. Princeton University, Princeton, 1970.
[12] R. T. Rockafellar. Lagrange multipliers and optimality. SIAM Review, 35:183238, 1993.
[13] S.-Y. Wu and D. H. Li and L. Qi and G. Zhou. An iterative method forsolving KKT system of the semi-infinte programming. optimization Methods
and Software, 20:629-643, 2005.
[14] Y. Tanaka, M. Fukushima, and T. Ibaraki. A globally convergent SQP method
for semi-infinite nonlinear optimization. Journal of Computational and Applied
Mathematics, 23:141-153, 1988.