We consider a class of nonsmooth generalized semi-infinite programming problems. We apply results from parametric optimization to the lower level problems of generalized semi-infinite programming problems to get estimates for the value functions of the lower level problems and thus derive necessary optimality conditions for generalized semi-infinite programming problems. We also derive some new estimates for the value functions of the lower level problems in terms of generalized differentiation and further obtain the necessary optimality conditions.

1. Introduction

Generalized semi-infinite programming problem (GSIP) is of the form

()

where Y(x): = {y ∈ ℝ^m∣v(x, y) ≤ 0}. GSIP is different from the standard semi-infinite programming in that its index set Y is dependent on x.

This first systematic study of GSIP was Hettich and Still [1] where the reduction method was used to reduce GSIP into standard nonlinear programming problems and second-order optimality conditions were derived. Necessary optimality conditions at an optimal solution

for (1) with differentiable data are as follows there exist nonnegative numbers λ₀, …, λ_p, not all zero, such that

()

where L(x, y, α, β) = αg(x, y)−〈β, v(x, y)〉 and each (α^j, β^j) is the usual FJ-multiplier of the lower level problem at its optimal solution

()

This condition was first derived by Jongen et al. [2] in an elementary way without any constraint qualifications or any kind of reduction approaches. They also proposed a constraint qualification under which it follows that λ₀ > 0 and discussed some geometrical properties of the feasible set which do not appear in standard semi-infinite case. The optimality conditions are further explored by Rückmann and Shapiro [3] and Stein [4].

GSIP in itself is of complex and exclusive structures such as the nonclosedness of the feasible set, nonconvexity, nonsmoothness, and bilevel structure and thus a difficult problem to solve see, for example, [2, 5, 6]. We also refer to [7–10] for some recent study on the structure of GSIP.

It is obvious that GSIP can be rewritten equivalently as the nonlinear programming problem

()

where ϕ(x) is the optimal value of Q(x). Then we can relate GSIP to the min-max problem

()

see [3] for more details. On the other hand, GSIP can be related to the following bilevel problem:

()

The problem (6) is a special bilevel optimization problem in that its upper level constraint is the same as the objective function of its lower level problem. However, there is a slight difference between GSIP problem (1) and problem (6). The feasible set of (6) is a subset of (1) in that the feasible set of (1) is the combination of the feasible set of (6) and the complement of dom Y. For more comparisons between GSIP and bilevel problems, see Stein and Still [11].

The bilevel problem (6) is equivalent to the following problem:

()

where Ω = {(x, y)∣g(x, y) ≤ 0, v(x, y) ≤ 0} and G(x, y) = ϕ(x) − g(x, y). This approach was used by Dempe and Zemkoho [12] to study bilevel optimization problems. For general references of bilevel optimization, see [13].

In this paper we concentrate on the optimality conditions of nonsmooth GSIP whose defining functions are Lipschitz continuous. Similar works are [14, 15]. We achieve this via the lower level optimal value function reformulation and then derive its necessary optimality conditions via the generalized differentiation. One of the key steps is to estimate the generalized gradients of the lower level optimal value function which involves parametric optimization. We will consider two cases with different approaches related to the two reformulations of GSIP as previously mentioned. Firstly, we develop optimality conditions via the min-max formulation with Lipschitz lower level optimal value function. Secondly, we develop optimality conditions via bilevel formulation under the assumption of partial calmness.

2. Preliminaries

In this section, we present some basic definitions and results from variational analysis [16, 17]. Given a set A in ℝⁿ, the regular normal cone

of A at

is defined by

()

The (general) normal cone N_A of A at

is defined by

()

Given a function

and a point

with

finite, denote by epi f the epigraph of f. The regular subdifferential of f at

is defined by

()

The general (basic, limiting) and singular subdifferential of f at

are defined, respectively, by

()

The upper regular subdifferential of f at

is defined by

, and the upper subdifferential of f is defined by

The Clarke (convexified) normal cone can be defined by two different approaches. On the one hand, it can be defined by the polar cone of the Clarke’s tangent cone

()

where

or defined via the generalized directional derivative of the (Lipschitzian) distant function dist (·, A); see Clarke [18]. On the other hand, it can be defined by the closed convex hull of the (general) normal cone

()

For this definition and also the equivalence of the two definitions, see, for example, Rockafellar and Wets [16].

The Clarke subgradients and Clarke horizon subgradients of f at x are defined by

()

The relationship between the Clarke sub-subdifferentials and basic sub-differentials is also referred to by Mordukhovich [17, Theorem 3.57].

Proposition 1 (see [16].)Let f be proper and lsc around . Then,

()

If, in particular, f is Lipschitz continuous at

, then

()

The normal cone N_A enjoys the robustness property

provided that the setting is finite dimension [17, page 11]. However, this is not true for the convexified cone

; see, for example, Rockafellar [19]. Consider

()

The normal cone

is just the x₃-axis, but

is the x₂x₃-plane for all x = (x₁, 0,0). The following proposition is from Rockafellar [19].

Proposition 2 (see [19].)If A is convex, or if is pointed, then the multifunction is closed at ; that is, for all , , one has .

Proposition 3. The Clarke normal cone has the robustness property

()

provided that N_A(x) is pointed.

Proof. It suffices to prove that . Let v ∈ limsup _y→xco N_A(y). Then there are y_k ∈ A, v_ik ∈ N_A(y_k), i = 1, …, n + 1 such that

()

since the sets N_A(y_k) are cones. Let

. Then {λ_k} is bounded; that is also to say, {v_ik} are bounded for all i. Otherwise,

. That is, v₁ + ⋯+v_n+1 = 0, where v_i is the limit of {v_ik/λ_k} _k for each i. Note that v_i ∈ N_A(x) since N_A(x) = limsup _y→xN_A(y). Thus v₁ = ⋯ = v_n+1 = 0 by the pointedness of N_A(x). On the other hand, ∑_i ∥v_i∥ = 1. This is a contradiction. Thus the sequence {v_ik} is bounded. By taking subsequences, we may assume that v_ik → v_i. Then v_i ∈ N_A(x) and v = v₁ + ⋯+v_n+1. This completes the proof.

The following definitions are required for further development.

Definition 4 (see [17], Definition 1.63.)Let S : X⇉Y be a set-valued mapping with , the domain of S.

(i)
Given , we say that the mapping S is inner semicontinuous at if for every sequence there is a sequence y_k ∈ S(x_k) converging to as k → ∞.
(ii)
S is inner semicompact at if for every sequence there is a sequence y_k ∈ S(x_k) that contains a convergent subsequence as k → ∞.
(iii)
S is μ-inner semicontinuous at (μ-inner semicompact at ) if in above two cases, is replaced by with .

Here the concept of μ-inner semicontinuity/semicompactness is important for our considerations. It is typical that the value function ϕ of the lower level problem Q(x) of GSIP is not continuous, even taking value −∞.

Theorem 5 (subdifferentiation of maximum functions [17, Theorem 3.46]). Consider the maximum function of the form

()

Let ϕ_i be lower semicontinuous around

for

and be upper semicontinuous at

for

. Assume that the qualification holds:

()

Then

()

where

Note that qualification (22) always holds if all related functions are locally Lipschitz.

The following two results are about continuity properties and estimates of subdifferentials of marginal functions which are crucial to our analysis for GSIP problems.

Proposition 6 (limiting subgradients of marginal functions [20]). Consider the parametric optimization problem

()

and let M(x): = {y ∈ G(x)∣μ(x) = φ(x, y)}, G(x): = {y ∈ ℝ^m∣φ_i(x, y) ≤ 0, i = 1, …, l}. For simplicity, one does not consider the case with equality constraints involved.

(i)
Assume that M is μ-inner semicontinuous at (the graph of M ), that φ and all φ_i are Lipschitz continuous around , and that the following qualification condition is satisfied:
()

One has the inclusions

()

(ii)
Assume that M is μ-inner semicompact at , and all φ and φ_i are Lipschitz continuous around for all , and qualification (25) holds for all , . Then
()

Proposition 7 (Lipschitz continuity of marginal functions [21, Theorem 5.2]). Continue to consider the parametric problem (24) in Proposition 6. Then the following assertions hold.

(i)
Assume that M is μ-inner semicontinuous at and φ is locally Lipschitz around this point. Then μ is Lipschitz around provided that it is lsc around and G is Lipschitz-like around .
(ii)
Assume that M is μ-inner compact at and φ is locally Lipschitz around for all . Then μ is Lipschitz around provided that it is lsc around and G is Lipschitz-like around for all .

3. Main Results

Now we are prepared to develop the optimality conditions for GSIP problem (1). Given a local solution

of problem (1), associate it with the following min-max problem

()

where ϕ(x): = sup _y∈Y(x)g(x, y). Let Y₀(x): = {y ∈ Y(x) : ϕ(x) = g(x, y)}. Denote by

()

solves GSIP (1), then

also solves problem

()

and thus by generalized Fermat′s rule (cf. [16, Theorem 10.1]), we have

()

So, calculus for the maximum function and the estimate of subdifferentials are essential to proceed. From (31) and Theorem 5, there exists μ ∈ [0,1] such that (if ϕ is Lipschitz)

()

Note that for a Lipschitz function ϕ,

()

Theorem 8 (optimality for GSIP with Lipschitz lower level optimal value function). Consider the GSIP problem (1), and let be its locally optimal solution. Assume that all functions f, g, and v are Lipschitz continuous, Y₀ is ϕ-inner semicompact at , and Y is Lipschitz-like at for all . Then there is and , , , i = 1, …, l, j = 1, …, k such that and

()

If in addition g and all components of v are regular at all

, then the optimality is of the form

()

Note that −∂(−g) = ∂⁺g.

Proof. Under regularity and Lipschitz continuity, since the following calculus rule for basic subgradients holds (see [16, Corollary 10.11]):

()

the last two equations follow directly from the first one. Note that the function −ϕ is in position of μ in Proposition 6. Under our assumptions, by Proposition 7, −ϕ is Lipschitz continuous and the estimate of

()

solves GSIP, then it also solves min _xF(x). By (31), (32), and (33), there exists μ ∈ [0,1] such that

()

Combining (37) and (38), there is

and λ_j ≥ 0,

, i = 1, …, l, j = 1, …, k such that

and

()

Letting

, i = 1, …, l, j = 1, …, k, we obtain the desired result.

Corollary 9. In addition to the assumptions in Theorem 8, assume that f, g, and v are continuously differentiable. Then the optimality condition at the optimal point is that there exist and , , , i = 1, …, l, j = 1, …, k such that and

()

Next we consider the case where the lower level value function ϕ may fail to be Lipschitz and give estimates for the subdifferentials of ϕ and thus further derive the optimality conditions for GSIP. However, it requires to use the Clarke subdifferentials.

Proposition 10. Consider the parametric optimization problem same as (24):

()

with corresponding solution mapping M : X⇉Y. Let

. Assume that the following conditions hold:

(i)
φ is lower semicontinuous at ;
(ii)
M is μ-inner semicompact at and is nonempty and compact;
(iii)
if , , , i ≤ n + 1, and ∑_i u_i + v_i = 0, then u_i = v_i = 0, w_i = 0;
(iv)
the cones and for all are pointed.

Then one has the inclusion

()

Proof (sketch: the definition of ∂-= cl co {∂+∂∞}). The proof is divided into two parts. First the set on the right hand of the required inclusion, denoted by Λ, is closed. The second step is to justify that ∂ + ∂^∞ ⊂ Λ.

Let , , , and

()

where

, i = 1, …, n + 1. We have to show that u ∈ Λ. We may assume that

, i = 1, …, n + 1, as

is compact. We show first that the sequence

is bounded. Suppose on the contrary that ∥z^k∥ → ∞. Then for each i,

()

Multiplying (44) by

and taking summation over i, we have

()

Note that for each i, by definition of

()

Let

. Then by assumption (iv) and Proposition 3 one has

, and thus

. Then

()

where

. Let

. Then v_1i + v_2i = 0 from (43). Combining (45) and (47), we have

()

Based on the assumption (iii), we have (u_1i, v_1i) = (0,0), (u_2i, v_2i) = (0,0). This contradicts the fact that (u_1i, v_1i, u_2i, v_2i) is of norm 1, and thus {z^k} is bounded. Then have convergent subsequences, say . Thus u = ∑ λ_iu_i with u_i = x_1i + x_2i. That is to say, Λ is closed.

Next, we justify that ∂ + ∂^∞ ⊂ Λ. Assume that , . Under the semicompactness assumption, invoking [17, Theorem 1.108], one gets that

()

Employing the sum rule from [17, Theorem 3.36] to the two above leads to

()

which completes the proof.

Theorem 11 (convexified normal cone to inequality system [22]). Consider G defined by inequality system G(x) = {y∣ϕ(x, y) ≤ 0}. Let ϕ be Lipschitz, and the qualification (non-smooth MFCQ) at holds:

()

where

. Then

()

As mentioned, GSIP can be relaxed into the following bilevel programming problem:

()

The feasible set of above problem is a subset of the feasible set M of (1). Thus, if

solves GSIP and

and

, then

also solves problem (6). The perturbed version of the above bilevel problem is

()

Problem (6) is said to be partially calm at

[23] if

()

Under the partial calmness condition, problem (6) can be transformed into the problem below, for some constant κ > 0,

()

Theorem 12 (necessary conditions of optimality of GSIP). Let be an optimal solution of GSIP with , and . Let the data functions f, g, and v be Lipschitz and the partial calmness condition (55) hold at for some . Assume that the following conditions hold:

(i)
Qualification (51) holds for Ω : = {(x, y)∣v(x, y) ≤ 0, g(x, y) ≤ 0} at .
(ii)
Y₀ is ϕ-inner semicompact at and .
(iii)
If , , , i ≤ n + 1, and ∑_i u_i + v_i = 0, then u_i = v_i = 0 and w_i = 0.
(iv)
The cones and for all are pointed.

Then there is κ > 0, λ_i ≥ 0,

, i = 1, …, r such that

, and

()

Proof. Let Ω = {(x, y)∣v(x, y) ≤ 0, g(x, y) ≤ 0}. Under our assumptions, GSIP can be relaxed into problem (6) and also solves (6) for all . Due to the partial calmness of (6), we also have that solves (56). Under the qualification assumption, the necessary optimality condition for problem (56) is (see, e.g., [24, Theorem 5.1] or [22, Theorem 6.2])

()

If v ∈ ∂⁺(−ϕ)(x), then . Indeed, by definition,

()

Thus,

, and from (58),

()

Applying Proposition 10 to −ϕ, there are λ_i ≥ 0, , i = 1, …, r such that and

()

So, noting that ,

()

This completes the proof.

Conflict of Interests

The authors declare that there is no conflict of interests.

Acknowledgments

This work is supported by the National Science Foundation of China (11001289) and the Key Project of Chinese Ministry of Education (211151).

References

1 Hettich R. and Still G., Second order optimality conditions for generalized semi-infinite programming problems, Optimization. (1995) 34, no. 3, 195–211, https://doi.org/10.1080/02331939508844106, MR1346690, ZBL0855.90129.
10.1080/02331939508844106
Google Scholar
2 Jongen H. Th., Rückmann J.-J., and Stein O., Generalized semi-infinite optimization: a first order optimality condition and examples, Mathematical Programming A. (1998) 83, no. 1, 145–158, https://doi.org/10.1016/S0025-5610(97)00099-3, MR1644020, ZBL0949.90090.
10.1007/BF02680555
Web of Science® Google Scholar
3 Rückmann J. J. and Shapiro A., First-order optimality conditions in generalized semi-infinite programming, Journal of Optimization Theory and Applications. (1999) 101, no. 3, 677–691, https://doi.org/10.1023/A:1021746305759, MR1692184, ZBL0956.90055.
10.1023/A:1021746305759
Web of Science® Google Scholar
4 Stein O., First-order optimality conditions for degenerate index sets in generalized semi-infinite optimization, Mathematics of Operations Research. (2001) 26, no. 3, 565–582, https://doi.org/10.1287/moor.26.3.565.10583, MR1849885.
10.1287/moor.26.3.565.10583
Web of Science® Google Scholar
5 Still G., Generalized semi-infinite programming: theory and methods, European Journal of Operational Research. (1999) 119, no. 2, 301–313, 2-s2.0-0033308857, https://doi.org/10.1016/S0377-2217(99)00132-0, ZBL0933.90063.
10.1016/S0377-2217(99)00132-0
Web of Science® Google Scholar
6 Stein O., Bi-Level Strategies in Semi-Infinite Programming, 2003, 71, Kluwer Academic, Boston, Mass, USA, Nonconvex Optimization and its Applications, MR2025879.
10.1007/978-1-4419-9164-5
Google Scholar
7 Günzel H., Jongen H. Th., and Stein O., On the closure of the feasible set in generalized semi-infinite programming, Central European Journal of Operations Research. (2007) 15, no. 3, 271–280, https://doi.org/10.1007/s10100-007-0030-2, MR2355903, ZBL1151.90562.
10.1007/s10100-007-0030-2
Web of Science® Google Scholar
8 Günzel H., Jongen H. Th., and Stein O., Generalized semi-infinite programming: the symmetric reduction ansatz, Optimization Letters. (2008) 2, no. 3, 415–424, https://doi.org/10.1007/s11590-007-0069-y, MR2399471.
10.1007/s11590-007-0069-y
Web of Science® Google Scholar
9 Guerra-Vázquez F., Jongen H. Th., and Shikhman V., General semi-infinite programming: symmetric Mangasarian-Fromovitz constraint qualification and the closure of the feasible set, SIAM Journal on Optimization. (2010) 20, no. 5, 2487–2503, https://doi.org/10.1137/090775294, MR2678402.
10.1137/090775294
Web of Science® Google Scholar
10 Jongen H. Th. and Shikhman V., Generalized semi-infinite programming: the nonsmooth symmetric reduction ansatz, SIAM Journal on Optimization. (2011) 21, no. 1, 193–211, https://doi.org/10.1137/100786757, MR2765495.
10.1137/100786757
Web of Science® Google Scholar
11 Stein O. and Still G., On generalized semi-infinite optimization and bilevel optimization, European Journal of Operational Research. (2002) 142, no. 3, 444–462, https://doi.org/10.1016/S0377-2217(01)00307-1, MR1922367, ZBL1081.90063.
10.1016/S0377-2217(01)00307-1
Web of Science® Google Scholar
12 Dempe S. and Zemkoho A. B., The generalized Mangasarian-Fromowitz constraint qualification and optimality conditions for bilevel programs, Journal of Optimization Theory and Applications. (2011) 148, no. 1, 46–68, https://doi.org/10.1007/s10957-010-9744-8, MR2747745, ZBL1223.90061.
10.1007/s10957-010-9744-8
Web of Science® Google Scholar
13 Shimizu K., Ishizuka Y., and Bard J. F., Nondifferentiable and Two-level Mathematical Programming, 1997, Kluwer Academic, Boston, Mass, USA, https://doi.org/10.1007/978-1-4615-6305-1, MR1429865.
10.1007/978-1-4615-6305-1
Google Scholar
14 Kanzi N. and Nobakhtian S., Necessary optimality conditions for nonsmooth generalized semi-infinite programming problems, European Journal of Operational Research. (2010) 205, no. 2, 253–261, https://doi.org/10.1016/j.ejor.2009.12.025, MR2595227, ZBL1188.90261.
10.1016/j.ejor.2009.12.025
Web of Science® Google Scholar
15 Kanzi N., Lagrange multiplier rules for non-differentiable DC generalized semi-infinite programming problems, Journal of Global Optimization. (2013) 56, no. 2, 417–430, https://doi.org/10.1007/s10898-011-9828-5, MR3063173.
10.1007/s10898-011-9828-5
Web of Science® Google Scholar
16 Rockafellar R. T. and Wets R. J. B., Variational Analysis, 1998, 317, Springer, Berlin, Germany, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].
10.1007/978-3-642-02431-3
Web of Science® Google Scholar
17 Mordukhovich B. S., Variational Analysis and Generalized Differentiation. I: Basic Theory, 2006, 330, Springer, Berlin, Germany, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], MR2191744.
10.1007/3-540-31247-1
Google Scholar
18 Clarke F. H., Optimization and Nonsmooth Analysis, 1983, John Wiley & Sons, New York, NY, USA, Canadian Mathematical Society Series of Monographs and Advanced Texts, MR709590, ZBL0627.68010.
Google Scholar
19 Rockafellar R. T., The Theory of Subgradients and Its Applications to Problems of Optimization. Convex and Nonconvex, 1981, 1, Heldermann, Berlin, Germany, R & E, MR623763.
Google Scholar
20 Mordukhovich B. S., Nam N. M., and Yen N. D., Subgradients of marginal functions in parametric mathematical programming, Mathematical Programming B. (2009) 116, no. 1-2, 369–396, https://doi.org/10.1007/s10107-007-0120-x, MR2421286, ZBL1177.90377.
10.1007/s10107-007-0120-x
Web of Science® Google Scholar
21 Mordukhovich B. S. and Nam N. M., Variational stability and marginal functions via generalized differentiation, Mathematics of Operations Research. (2005) 30, no. 4, 800–816, https://doi.org/10.1287/moor.1050.0147, MR2185816.
10.1287/moor.1050.0147
Web of Science® Google Scholar
22 Mordukhovich B. S., Nam N. M., and Phan H. M., Variational analysis of marginal functions with applications to bilevel programming, Journal of Optimization Theory and Applications. (2012) 152, no. 3, 557–586, https://doi.org/10.1007/s10957-011-9940-1, MR2886360, ZBL1268.90127.
10.1007/s10957-011-9940-1
Web of Science® Google Scholar
23 Ye J. J. and Zhu D. L., Optimality conditions for bilevel programming problems, Optimization. (1995) 33, no. 1, 9–27, https://doi.org/10.1080/02331939508844060, MR1333152, ZBL0820.65032.
10.1080/02331939508844060
Google Scholar
24 Dempe S., Dutta J., and Mordukhovich B. S., New necessary optimality conditions in optimistic bilevel programming, Optimization. (2007) 56, no. 5-6, 577–604, https://doi.org/10.1080/02331930701617551, MR2362708, ZBL1172.90481.
10.1080/02331930701617551
Web of Science® Google Scholar

All articles

Optimality Conditions for Nonsmooth Generalized Semi-Infinite Programs

Abstract

1. Introduction

2. Preliminaries

3. Main Results

Conflict of Interests

Acknowledgments

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Optimality Conditions for Nonsmooth Generalized Semi-Infinite Programs

Abstract

1. Introduction

2. Preliminaries

3. Main Results

Conflict of Interests

Acknowledgments

References

References

Related

Information