# Sufficient Optimality and Sensitivity Analysis of a Parameterized Min-Max Programming

Authors: Huijuan Xiong; Yu Xiao; Chaohong Song
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Sufficient optimality and sensitivity of a parameterized min-max programming with fixed feasible set are analyzed. Based on Clarke's subdifferential and Chaney's second-order directional derivative, sufficient optimality of the parameterized min-max programming is discussed first. Moreover, under a convex assumption on the objective function, a subdifferential computation formula of the marginal function is obtained. The assumptions are satisfied naturally for some application problems. Moreover, the formulae based on these assumptions are concise and convenient for algorithmic purpose to solve the applications.


---

## Body

## 1. Introduction

In this paper, sufficient optimality and sensitivity analysis of a parameterized min-max programming are given. The paper is triggered by a local reduction algorithmic strategy for solving following nonsmooth semi-infinite min-max-min programming (SIM3P, see [1, 2], etc. for related applications reference):(1.1)min⁡xf(x)s.t.g(x)=max⁡y∈Ymin⁡1≤i≤q{gi(x,y)}≤0.
With the local reduction technique, the SIM3P can be rewritten as a bilevel programming first, where the lower problem is the following parameterized min-max programming Px (see [3–5] for related reference of local reduction strategy):
(1.2)min⁡yg(x,y)=max⁡1≤i≤q{-gi(x,y)}s.t.y∈Y.
To make the bilevel strategy applicable to SIM3P, it is essential to discuss the second-order sufficient optimality of Px and give sensitivity analysis of the parameterized minimum y(x) and corresponding marginal function g(x,y(x)).Sensitivity analysis of optimization problems is an important aspect in the field of operation and optimization research. Based on different assumptions, many results on kinds of parametric programming have been obtained ([6–9], etc.). Among these, some conclusions on parameterized min-max programming like (1.2) have also been given. For example, based on variation analysis, parameterized continuous programming with fixed constraint was discussed in [7]. Problem like (1.2) can be seen as a special case. Under the inf-compactness condition and the condition objective function is concave with respect to the parameter, directional derivative computational formula of marginal function for (1.2) can be obtained directly. However, concave condition cannot be satisfied for many problems. Recently, Fréchet subgradients computation formula of marginal functions for nondifferentiable programming in Asplund spaces was given ([9]). By using Fréchet subgradients computation formula in [9], subgradient formula of marginal function for (1.2) is direct. But the formula is tedious, if utilizing the formula to construct optimality system of (1.1), the system is so complex that it is difficult to solve the obtained optimality system.For more convenient computational purpose, the focus of this paper is to establish sufficient optimality and simple computation formula of marginal function for (1.2). Based on Clarke's subdifferential and Chaney's second-order directional derivative, sufficient optimality of the parameterized programming Px is given first. And then Lipschitzian continuousness of the parameterized isolated minimizer y(x) and the marginal function g(y(x),x) is discussed; moreover, subdifferential computation formula of the marginal function is obtained.


## 2. Main Results

LetY in (1.2) be defined as Y={y∈Rm:hi(y)≤0,i=1,…,l}, where hi(·) and i=1,…,l, are twice continuously differentiable functions on Rm, and gi(·,·) in (1.2) are twice continuously differentiable functions on Rn×m. In the following, we first give the sufficient optimality condition of (1.2) based on Clarke's subdifferential and Chaney's second-order directional derivative, and then make sensitivity analysis of the parameterized problem Px.


### 2.1. Sufficient Optimality Conditions ofPx

Definition 2.1 (see [10]).
For a given parameterx, a point y*∈Y is said to be an local minimum of problem Px if there exists a neighborhood U of y* such that
(2.1)g(x,y)≥g(x,y*),∀y∈U∩Y,y≠y*.Assumption 2.2.
For a given parameterx, suppose that Px satisfying the following constraint qualification:
(2.2){d∈Rm:∇hi(y)Td<0,∀i∈Ih(y),y∈Y}≠∅,
where Ih(y)={i={1,…,l}:hi(y)=0}.
For a given parameterx, denote the Lagrange function of Px as L(x,y,λ)=g(x,y)+∑i=1l‍λihi(y), then the following holds.Theorem 2.3.
For a given parameterx, if y* is a minimum of Px, Assumption 2.2 holds, then there exists a λ*∈R+l such that 0∈∂yL(x,y*,λ), where ∂yL(x,y*,λ*) denotes the Clarke's subdifferential of L(x,y*,λ*). Specifically, the following system holds:
(2.3)0∈∂yg(x,y*)+∑i=1l‍λi∇hi(y*),
where ∂yg(x,y) denotes Clarke's subdifferential of g(x,y) with respect to y, it can be computed as co{∇ygi(x,y*):i∈I(x,y*)}, co{·} is an operation of making convex hull of the elements, I(x,y*)={i∈{1,…,q}:g(x,y*)=g(x,y*)}.Proof.
The conclusion is direct from Theorem3.2.6 and Corollary 5.1.8 in [11].Sinceg(x,y)=max1≤i≤p{gi(x,y)} is a directional differentiable function (Theorem 3.2.13 in [11]), the directional derivative of g(x,y) with respect to y in direction d can be computed as follows:
(2.4)gy′(x,y;d)=max⁡{ξTd:∀ξ∈∂yg(x,y),∀d∈Rm}.Definition 2.4 (see [10]).
Letf(x) is a locally Lipschitzian function on Rn, u be a nonzero vector in Rn. Suppose that
(2.5)d∈∂uf(x)={υ∈Rn:∃{xk},{υk},s.t.xk⟶x,υk⟶υ,υk∈∂f(xk)for eachk}
define Chaney's lower second-order directional derivative as follows:
(2.6)f-′′(x,υ,u)=liminf⁡f(xk)-f(x)-υT(xk-x)tk2,
taking over all triples of sequences {xk}, {υk}, and {tk} for which  (a)
tk>0 for each k and {xk}→x;(b)
tk→0 and (xk-x*)/tk converges to u;(c)
{υk}→υ with υk∈∂f(xk) for each k.
Similarly, Chaney's upper second-order directional derivative can be defined as(2.7)f+′′=limsup⁡f(xk)-f(x)-υT(xk-x)tk2,
taking over all triples of sequences {xk}, {υk}, and {tk} for which (a), (b), and (c) above hold.
For parameterized max-type functiong(x,y)=max1≤i≤p{-gi(x,y)}, where x is a given parameter, its Chaney's lower and upper second-order directional derivatives can be computed as follows.Proposition 2.5 (see [12]).
For any given parameterx, Chaney's lower and upper second-order directional derivatives of g(x,y) with respect to y exist; moreover, for any given 0≠u∈Rq, υ∈∂ug(x,y), it has
(2.8)g-′′(x,y;d)=min⁡{12∑i=1q‍ajuT∇y2gi(x,y)u:a∈Tu(g,y,υ)},g+′′(x,y;d)=max⁡{12∑i=1q‍ajuT∇y2gi(x,y)u:a∈Tu(g,y,υ)},
where(2.9)Tu(g,y,υ)={a∃{y(k)},{a(k)},{υ(k)},such  that∈R+q:a(1)y(k)⟶yin  directionu,a∈R+q:a∈R+q:(2)υ(k)⟶υ,andυ(k)∈∂yg(x,y(k)),k=1,2,…,a∈R+q:a∈a(3)a(k)⟶a,a(k)∈Eq,υ(k)=∑i=1pai(k)∇ygi(x,y(k)),a∈R+q:a∈a(4)aj(k)=0,forj∉Kg(y(k))a∈R+q:a∈aa∈},
where Kg(y(k))={i∈Q:gi(x,y(n))=g(x,y(n)),∃y(n)∈B(y,1/n),∀n∈N}, Eq={a∈R+q:∑i=1p‍ai=1}, Q={1,…,q}, and B(y,1/n) denotes the ball centered in y with radius 1/n.Theorem 2.6 (sufficiency theorem).
For a given parameterx∈Rn, Assumption 2.2 holds, then there exists y*∈Rm such that (2.3) holds. Moreover, for any feasible direction d∈Rm of Y, that is, max{∇hi(y*)Td:1≤i≤l}≤0, if d satisfying one of the following conditions:  (1)
gy′(x,y*;d)≠0;(2)
gy′(x,y*;d)=0, ∑i=1l‍λi∇hi(y)Td=0, that is, Ly′(x,y;d)=0, and
(2.10)min⁡{12∑i=1q‍aidT∇y2gi(x,y*)d:a∈Eq}+∑i=1l‍λidT∇2hi(y*)d>0,then y* is a local minimum of Px.Proof.
(1) If not, then there exists sequencestk↓0, dk→d, yk=y*+tkdk∈Y such that
(2.11)g(x,yk)<g(x,y*).
As a result, gy′(x,y*;d)=limt↓0(g(x,y*+td)-g(x,y*))/t=limk→+∞(g(x,y*+tkdk)-g(x,y*))/tk≤0. If gy′(x,y*;d)≠0, then gy′(x,y*;d)<0. From (2.4), we know that ξTd<0for allξ∈∂yg(x,y*). Hence, for the direction d∈Rm, we have
(2.12)ξTd+∑i=1l∇hi(y*)Td<0,ξ∈∂yg(x,y*).
On the other hand, from y* satisfying (2.3), we know that there exists a ξ∈∂yg(x,y*) such that
(2.13)ξTd+∑i=1l∇hi(y*)Td=0,
which leads to a contradiction to (2.12).
(2) From Theorem 4 in [10] and Proposition 2.5, the conclusion is direct.


### 2.2. Sensitivity Analysis of ParameterizedPx

In the following, we make sensitivity analysis of parameterized min-max programmingPx, that is, study variation of isolated local minimizers and corresponding marginal function under small perturbation of x.For convenience of discussion, for any given parameterx, denote y*(x) as a minimizer of Px, υ(x)=min{g(x,y):y∈Y} as the corresponding marginal function value and make the following assumptions first.Assumption 2.7.
For givenx∈Rn, the parametric problem Px is a convex problem, specifically, gi(x,y) and i=1,…,q are concave functions with respect to that variables y and hj(y),j=1,…,l are convex functions.Assumption 2.8.
LetIh(y)={i∈L:hi(y)=0}, {∇hi(y):i∈Ih(y)} are linearly independent.Definition 2.9 (see Definition 2.1, [13]).
For a givenx-, y-∈Y is said to be an isolated local minimum with order i (i = 1 or 2) of Px- if there exists a real m>0 and a neighborhood V of y- such that
(2.14)g(x-,y)>g(x-,y-)+12m‖y-y-‖i,∀y∈V∩Y,y≠y-.Theorem 2.10.
For a givenx∈Rn, Assumptions 2.2–2.8 hold, then the following conclusions hold:  (1)
ify*(x) with corresponding multiplier λ* is the solution of (2.3), then y*(x) is a unique first-order isolated minimizer of Px;(2)
for any minimumy*(x), it is a locally Lipschitzian function with respect to x, that is, there exists a L1>0, δ>0 such that
(2.15)‖y*(xk)-y*(x)‖≤L1‖xk-x‖,∀xk∈U(x,δ),y*(xk)∈Y(xk),
where Y(xk) denotes minima set of Pxk;(3)
for any minimumy*(x), marginal function υ(x)=g(x,y*(x)) is also a locally Lipschitz function with respect to x, and ∂υ(x)⊆S(x), where
(2.16)S(x)=co⁡{∇xgi(x,y*(x)),i∈I(x,y*(x))},
and I(x,y*(x))={i∈{1,…,q}:gi(x,y*(x))=g(x,y*(x))}. As a result,
(2.17)∂υ(x)={∑i∈I(x,y*(x))λi∇xgi(x,y*(x)):λi≥0,∑i∈I(x,y*(x))λi=1}.Proof.
(1) From Assumption2.7, it is direct that y*(x) is a global minimizer of Px. We only prove y*(x) is a first-order isolated minimizer.
If the conclusion does not hold, then there exists a sequence{yk}∈Y(x) converging to y*(x), yk≠y*(x), and a sequence mk, mk>0, and mk converges to 0 such that
(2.18)g(x,yk)≤g(x,y*(x))+12mk‖yk-y*‖,yk∈Y.
Take dk=(yk-y*(x))/∥yk-y*(x)∥, for simplicity, we suppose dk→d, with ∥d∥=1. Let tk=∥yk-y*(x)∥, then from yk∈Y, dk→d and Y is compact, we have
(2.19)y*(x)+tkd∈Y,tk⟶0,
that is,
(2.20)∇hi(y*(x))Td≤0,∀i∈I(x,y*(x)).
From Assumption 2.8, we know that ∑i∈I(x,y*(x))‍∇hi(y*(x))Td≠0. As a result, we have ∑i∈I(x,y*(x))‍∇hi(y*(x))Td<0.
From the first equation of (2.3), we know that there exists a z∈∂yg(x,y*(x)) such that for any feasible direction d, zTd=-∑i∈I(x,y*(x))‍λi∇hi(y*(x))Td>0. Hence,
(2.21)gy′(x,y*(x);d)=max⁡{ξTd:ξ∈∂yg(x,y*(x))}≥zTd>0.
On the other hand, from y*(x) is a minimizer, we know that gy′(x,y*(x);d)≥0, this leads to a contradiction;
(2) from Assumption2.8 and Theorem 3.1 in [13], the conclusion is direct;
(3) sinceg(x,y) is a locally Lipschitzian function with respect to x and y, then there exists δ>0, δ′>0, and L2>0 such that for any x1∈U(x,δ), y∈U(y*(x),δ′), it has
(2.22)|g(x1,y*(x))-g(x,y*(x))|≤L2‖x1-x‖,|g(x,y)-g(x,y*(x))|≤L2‖y-y*(x)‖.
As to x1∈U(x,δ), from the conclusion in (1.2), there exists a a L1>0 such that ∥y*(x1)-y*(x)∥≤L1∥x1-x∥. As a result,
(2.23)|υ(x1)-υ(x)|=|g(x1,y*(x1)-g(x,y*(x)))|=|g(x1,y*(x1))-g(x1,y*(x))+g(x1,y*(x))-g(x,y*(x))|≤|g(x1,y*(x1))-g(x1,y*(x))|+|g(x1,y*(x))-g(x,y*(x))|≤L2‖y*(x1)-y*(x)‖+L2‖x1-x‖≤L2(1+L1)‖x1-x‖.
Hence, the marginal function υ(x) is a local Lipschitzian function with respect to x.
LetS^(x)={-∇xgi(x,y(x)),i∈I(x,y(x))}, then S(x)=co{ξ,ξ∈S^(x)}. We prove that S^(x) is closed first, that is, prove for any sequence {xk}⊂Rn, xk→x-, zk∈S^(xk), zk→z, it has z∈S^(x-).
Fromzk∈S^(xk), there exist yk∈Y(xk); ik∈I(xk,yk) such that zk=-∇xgik(xk,yk). Without loss of generality, suppose that {yk} converges to y-; {ik} converges to i-. From Proposition 3.3 in [14], it has y-∈Y(x-), and i-∈I(x-,y-) and from ∇xgi-(x,y) is a continuous function, it has z=limk→+∞zk=limk→+∞∇xgik(xk,yk)=∇xgi-(x-,y-)∈S^(x). As a result, S^(x) is a closed set.
From Theorem3.2.16 in [11], for any ξ∈∂υ(x), there exists xk∈Rn, xk→x such that ∇υ(xk) exists and ξ=limk→+∞∇υ(xk). In addition, for arbitrary d∈Rn, it has
(2.24)∇υ(xk)Td=υ′(xk;d)=lim⁡t↓0υ(xk+td)-υ(xk)t=lim⁡t↓0g(xk+td,y*(xk+td))-g(xk,y*(xk))t≤lim⁡t↓0g(xk+td,y*(xk))-g(xk,y*(xk))t=max⁡i∈I(xk,y){-∇xgi(xk,y)Td}.
From the definition of S(xk), ∃zk∈S(xk) such that zkTd=maxi∈I(xk,y){-∇xgi(xk,y)Td}. Hence, it has ∇υ(xk)Td≤zkTd.
Fromzk→z∈S^(x)⊂S(x), ∇υ(xk)→ξ and ∇υ(xk)Td≤zkTd, it has ξTd≤zTd, that is, for arbitrary d∈Rn and ξ∈∂υ(x), there exists z∈S(x) such that ξTd≤zTd.
If∂υ(x)⊂S(x) does not hold, then there exists a ξ∈∂υ(x) and ξ∉S(x). From S(x) is a compact convex set and separation theorem ([15]), there exists a d∈Rn such that ξTd<0 and for arbitrary z∈S(x), zTd≥0, which leads to a contradiction. As a result, ∂υ(x)⊂S(x) holds. From ∂υ(x)⊂S(x) and S(x)=co{∇xgi(x,y*(x)),i∈I(x,y*(x))}, computation formula (2.17) is direct.


## 2.1. Sufficient Optimality Conditions ofPx

Definition 2.1 (see [10]).
For a given parameterx, a point y*∈Y is said to be an local minimum of problem Px if there exists a neighborhood U of y* such that
(2.1)g(x,y)≥g(x,y*),∀y∈U∩Y,y≠y*.Assumption 2.2.
For a given parameterx, suppose that Px satisfying the following constraint qualification:
(2.2){d∈Rm:∇hi(y)Td<0,∀i∈Ih(y),y∈Y}≠∅,
where Ih(y)={i={1,…,l}:hi(y)=0}.
For a given parameterx, denote the Lagrange function of Px as L(x,y,λ)=g(x,y)+∑i=1l‍λihi(y), then the following holds.Theorem 2.3.
For a given parameterx, if y* is a minimum of Px, Assumption 2.2 holds, then there exists a λ*∈R+l such that 0∈∂yL(x,y*,λ), where ∂yL(x,y*,λ*) denotes the Clarke's subdifferential of L(x,y*,λ*). Specifically, the following system holds:
(2.3)0∈∂yg(x,y*)+∑i=1l‍λi∇hi(y*),
where ∂yg(x,y) denotes Clarke's subdifferential of g(x,y) with respect to y, it can be computed as co{∇ygi(x,y*):i∈I(x,y*)}, co{·} is an operation of making convex hull of the elements, I(x,y*)={i∈{1,…,q}:g(x,y*)=g(x,y*)}.Proof.
The conclusion is direct from Theorem3.2.6 and Corollary 5.1.8 in [11].Sinceg(x,y)=max1≤i≤p{gi(x,y)} is a directional differentiable function (Theorem 3.2.13 in [11]), the directional derivative of g(x,y) with respect to y in direction d can be computed as follows:
(2.4)gy′(x,y;d)=max⁡{ξTd:∀ξ∈∂yg(x,y),∀d∈Rm}.Definition 2.4 (see [10]).
Letf(x) is a locally Lipschitzian function on Rn, u be a nonzero vector in Rn. Suppose that
(2.5)d∈∂uf(x)={υ∈Rn:∃{xk},{υk},s.t.xk⟶x,υk⟶υ,υk∈∂f(xk)for eachk}
define Chaney's lower second-order directional derivative as follows:
(2.6)f-′′(x,υ,u)=liminf⁡f(xk)-f(x)-υT(xk-x)tk2,
taking over all triples of sequences {xk}, {υk}, and {tk} for which  (a)
tk>0 for each k and {xk}→x;(b)
tk→0 and (xk-x*)/tk converges to u;(c)
{υk}→υ with υk∈∂f(xk) for each k.
Similarly, Chaney's upper second-order directional derivative can be defined as(2.7)f+′′=limsup⁡f(xk)-f(x)-υT(xk-x)tk2,
taking over all triples of sequences {xk}, {υk}, and {tk} for which (a), (b), and (c) above hold.
For parameterized max-type functiong(x,y)=max1≤i≤p{-gi(x,y)}, where x is a given parameter, its Chaney's lower and upper second-order directional derivatives can be computed as follows.Proposition 2.5 (see [12]).
For any given parameterx, Chaney's lower and upper second-order directional derivatives of g(x,y) with respect to y exist; moreover, for any given 0≠u∈Rq, υ∈∂ug(x,y), it has
(2.8)g-′′(x,y;d)=min⁡{12∑i=1q‍ajuT∇y2gi(x,y)u:a∈Tu(g,y,υ)},g+′′(x,y;d)=max⁡{12∑i=1q‍ajuT∇y2gi(x,y)u:a∈Tu(g,y,υ)},
where(2.9)Tu(g,y,υ)={a∃{y(k)},{a(k)},{υ(k)},such  that∈R+q:a(1)y(k)⟶yin  directionu,a∈R+q:a∈R+q:(2)υ(k)⟶υ,andυ(k)∈∂yg(x,y(k)),k=1,2,…,a∈R+q:a∈a(3)a(k)⟶a,a(k)∈Eq,υ(k)=∑i=1pai(k)∇ygi(x,y(k)),a∈R+q:a∈a(4)aj(k)=0,forj∉Kg(y(k))a∈R+q:a∈aa∈},
where Kg(y(k))={i∈Q:gi(x,y(n))=g(x,y(n)),∃y(n)∈B(y,1/n),∀n∈N}, Eq={a∈R+q:∑i=1p‍ai=1}, Q={1,…,q}, and B(y,1/n) denotes the ball centered in y with radius 1/n.Theorem 2.6 (sufficiency theorem).
For a given parameterx∈Rn, Assumption 2.2 holds, then there exists y*∈Rm such that (2.3) holds. Moreover, for any feasible direction d∈Rm of Y, that is, max{∇hi(y*)Td:1≤i≤l}≤0, if d satisfying one of the following conditions:  (1)
gy′(x,y*;d)≠0;(2)
gy′(x,y*;d)=0, ∑i=1l‍λi∇hi(y)Td=0, that is, Ly′(x,y;d)=0, and
(2.10)min⁡{12∑i=1q‍aidT∇y2gi(x,y*)d:a∈Eq}+∑i=1l‍λidT∇2hi(y*)d>0,then y* is a local minimum of Px.Proof.
(1) If not, then there exists sequencestk↓0, dk→d, yk=y*+tkdk∈Y such that
(2.11)g(x,yk)<g(x,y*).
As a result, gy′(x,y*;d)=limt↓0(g(x,y*+td)-g(x,y*))/t=limk→+∞(g(x,y*+tkdk)-g(x,y*))/tk≤0. If gy′(x,y*;d)≠0, then gy′(x,y*;d)<0. From (2.4), we know that ξTd<0for allξ∈∂yg(x,y*). Hence, for the direction d∈Rm, we have
(2.12)ξTd+∑i=1l∇hi(y*)Td<0,ξ∈∂yg(x,y*).
On the other hand, from y* satisfying (2.3), we know that there exists a ξ∈∂yg(x,y*) such that
(2.13)ξTd+∑i=1l∇hi(y*)Td=0,
which leads to a contradiction to (2.12).
(2) From Theorem 4 in [10] and Proposition 2.5, the conclusion is direct.


## 2.2. Sensitivity Analysis of ParameterizedPx

In the following, we make sensitivity analysis of parameterized min-max programmingPx, that is, study variation of isolated local minimizers and corresponding marginal function under small perturbation of x.For convenience of discussion, for any given parameterx, denote y*(x) as a minimizer of Px, υ(x)=min{g(x,y):y∈Y} as the corresponding marginal function value and make the following assumptions first.Assumption 2.7.
For givenx∈Rn, the parametric problem Px is a convex problem, specifically, gi(x,y) and i=1,…,q are concave functions with respect to that variables y and hj(y),j=1,…,l are convex functions.Assumption 2.8.
LetIh(y)={i∈L:hi(y)=0}, {∇hi(y):i∈Ih(y)} are linearly independent.Definition 2.9 (see Definition 2.1, [13]).
For a givenx-, y-∈Y is said to be an isolated local minimum with order i (i = 1 or 2) of Px- if there exists a real m>0 and a neighborhood V of y- such that
(2.14)g(x-,y)>g(x-,y-)+12m‖y-y-‖i,∀y∈V∩Y,y≠y-.Theorem 2.10.
For a givenx∈Rn, Assumptions 2.2–2.8 hold, then the following conclusions hold:  (1)
ify*(x) with corresponding multiplier λ* is the solution of (2.3), then y*(x) is a unique first-order isolated minimizer of Px;(2)
for any minimumy*(x), it is a locally Lipschitzian function with respect to x, that is, there exists a L1>0, δ>0 such that
(2.15)‖y*(xk)-y*(x)‖≤L1‖xk-x‖,∀xk∈U(x,δ),y*(xk)∈Y(xk),
where Y(xk) denotes minima set of Pxk;(3)
for any minimumy*(x), marginal function υ(x)=g(x,y*(x)) is also a locally Lipschitz function with respect to x, and ∂υ(x)⊆S(x), where
(2.16)S(x)=co⁡{∇xgi(x,y*(x)),i∈I(x,y*(x))},
and I(x,y*(x))={i∈{1,…,q}:gi(x,y*(x))=g(x,y*(x))}. As a result,
(2.17)∂υ(x)={∑i∈I(x,y*(x))λi∇xgi(x,y*(x)):λi≥0,∑i∈I(x,y*(x))λi=1}.Proof.
(1) From Assumption2.7, it is direct that y*(x) is a global minimizer of Px. We only prove y*(x) is a first-order isolated minimizer.
If the conclusion does not hold, then there exists a sequence{yk}∈Y(x) converging to y*(x), yk≠y*(x), and a sequence mk, mk>0, and mk converges to 0 such that
(2.18)g(x,yk)≤g(x,y*(x))+12mk‖yk-y*‖,yk∈Y.
Take dk=(yk-y*(x))/∥yk-y*(x)∥, for simplicity, we suppose dk→d, with ∥d∥=1. Let tk=∥yk-y*(x)∥, then from yk∈Y, dk→d and Y is compact, we have
(2.19)y*(x)+tkd∈Y,tk⟶0,
that is,
(2.20)∇hi(y*(x))Td≤0,∀i∈I(x,y*(x)).
From Assumption 2.8, we know that ∑i∈I(x,y*(x))‍∇hi(y*(x))Td≠0. As a result, we have ∑i∈I(x,y*(x))‍∇hi(y*(x))Td<0.
From the first equation of (2.3), we know that there exists a z∈∂yg(x,y*(x)) such that for any feasible direction d, zTd=-∑i∈I(x,y*(x))‍λi∇hi(y*(x))Td>0. Hence,
(2.21)gy′(x,y*(x);d)=max⁡{ξTd:ξ∈∂yg(x,y*(x))}≥zTd>0.
On the other hand, from y*(x) is a minimizer, we know that gy′(x,y*(x);d)≥0, this leads to a contradiction;
(2) from Assumption2.8 and Theorem 3.1 in [13], the conclusion is direct;
(3) sinceg(x,y) is a locally Lipschitzian function with respect to x and y, then there exists δ>0, δ′>0, and L2>0 such that for any x1∈U(x,δ), y∈U(y*(x),δ′), it has
(2.22)|g(x1,y*(x))-g(x,y*(x))|≤L2‖x1-x‖,|g(x,y)-g(x,y*(x))|≤L2‖y-y*(x)‖.
As to x1∈U(x,δ), from the conclusion in (1.2), there exists a a L1>0 such that ∥y*(x1)-y*(x)∥≤L1∥x1-x∥. As a result,
(2.23)|υ(x1)-υ(x)|=|g(x1,y*(x1)-g(x,y*(x)))|=|g(x1,y*(x1))-g(x1,y*(x))+g(x1,y*(x))-g(x,y*(x))|≤|g(x1,y*(x1))-g(x1,y*(x))|+|g(x1,y*(x))-g(x,y*(x))|≤L2‖y*(x1)-y*(x)‖+L2‖x1-x‖≤L2(1+L1)‖x1-x‖.
Hence, the marginal function υ(x) is a local Lipschitzian function with respect to x.
LetS^(x)={-∇xgi(x,y(x)),i∈I(x,y(x))}, then S(x)=co{ξ,ξ∈S^(x)}. We prove that S^(x) is closed first, that is, prove for any sequence {xk}⊂Rn, xk→x-, zk∈S^(xk), zk→z, it has z∈S^(x-).
Fromzk∈S^(xk), there exist yk∈Y(xk); ik∈I(xk,yk) such that zk=-∇xgik(xk,yk). Without loss of generality, suppose that {yk} converges to y-; {ik} converges to i-. From Proposition 3.3 in [14], it has y-∈Y(x-), and i-∈I(x-,y-) and from ∇xgi-(x,y) is a continuous function, it has z=limk→+∞zk=limk→+∞∇xgik(xk,yk)=∇xgi-(x-,y-)∈S^(x). As a result, S^(x) is a closed set.
From Theorem3.2.16 in [11], for any ξ∈∂υ(x), there exists xk∈Rn, xk→x such that ∇υ(xk) exists and ξ=limk→+∞∇υ(xk). In addition, for arbitrary d∈Rn, it has
(2.24)∇υ(xk)Td=υ′(xk;d)=lim⁡t↓0υ(xk+td)-υ(xk)t=lim⁡t↓0g(xk+td,y*(xk+td))-g(xk,y*(xk))t≤lim⁡t↓0g(xk+td,y*(xk))-g(xk,y*(xk))t=max⁡i∈I(xk,y){-∇xgi(xk,y)Td}.
From the definition of S(xk), ∃zk∈S(xk) such that zkTd=maxi∈I(xk,y){-∇xgi(xk,y)Td}. Hence, it has ∇υ(xk)Td≤zkTd.
Fromzk→z∈S^(x)⊂S(x), ∇υ(xk)→ξ and ∇υ(xk)Td≤zkTd, it has ξTd≤zTd, that is, for arbitrary d∈Rn and ξ∈∂υ(x), there exists z∈S(x) such that ξTd≤zTd.
If∂υ(x)⊂S(x) does not hold, then there exists a ξ∈∂υ(x) and ξ∉S(x). From S(x) is a compact convex set and separation theorem ([15]), there exists a d∈Rn such that ξTd<0 and for arbitrary z∈S(x), zTd≥0, which leads to a contradiction. As a result, ∂υ(x)⊂S(x) holds. From ∂υ(x)⊂S(x) and S(x)=co{∇xgi(x,y*(x)),i∈I(x,y*(x))}, computation formula (2.17) is direct.


## 3. Discussion

In this paper, sufficient optimality and sensitivity analysis of a parameterized min-max programming are given. A rule for computation the subdifferential ofυ(x) is established. Though the assumptions in this paper are some restrictive compared to some existing work, the assumptions hold naturally for some applications. Moreover, the obtained computation formula is simple, it is beneficial for establishing a concise first-order necessary optimality system of (1.1), and then constructing effective algorithms to solve the applications.



---

*Source: 692325-2012-08-17.xml*