A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints

(1)

A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints

Guidance

Professor Masao FUKUSHIMA

Takeshi EJIRI

2005 Graduate Course in

Department of Applied Mathematics and Physics Graduate School of Informatics

Kyoto University

KYOTO UNIVER SITY FO

U N^KYOTODED 1^JAPAN897

February 2007

(2)

Abstract

Real-world problems are subject to various uncertainties. To cope with difficulties arising in those situations, there has been increasing attention to optimization problems under uncertainty in recent years. However, just a few works have dealt with Mathematical Programs with Equilibrium Constraints (MPEC) under uncertainty. In particular, there have been very few studies on a robust optimization approach to those problems.

In this paper, we formulate an MPEC under uncertainty as a Mathematical Program with

Second-Order Cone Complementarity Constraints (MPSOCCC). Since the MPSOCCC is diffi-

cult to deal with directly, we use a smoothing function to approximate the problem and solve a

sequence of smooth approximation problems to get a solution of the original MPSOCCC. The

main theoretical result of this work is to establish that the proposed smoothing method has the

global convergence property to a stationary point of the MPSOCCC.

(3)

1 Introduction 1

2 Preliminaries 2

2.1 Bilevel program and MPSOCCC . . . . 2 2.2 Jordan algebra associated with the SOC . . . . 3 2.3 Reformulation of SOCCC into equation . . . . 5

3 Smoothing method for problem P 0 7

4 Optimality conditions 9

5 Concluding remarks 20

(4)

1 Introduction

Optimization problems whose constraints contain complementarity conditions or variational in- equalities are called Mathematical Programs with Equilibrium Constraints (MPECs). Although MPECs are very difficult problems to deal with because of their nonconvexity and nondifferentiability, they have high ability of formulating a wide range of practical problems. Therefore researchers have paid much attention to them and actively studied them in recent years. In particular, a bilevel program is a special case of MPEC, which includes many important problems such as a leader-follower decision-making problem. The bilevel program can be reformulated as a Mathematical Program with Complementarity Constraints (MPCC), by replacing the lower- level optimization problem by its KKT conditions. For MPECs, MPCCs and bilevel programs, there are many research results about optimality conditions and effective algorithms, such as branch-and-bound methods [2, 14, 18, 22], complementary pivoting algorithm [4] and smoothing methods [9, 12, 20].

While optimization can be applied to a wide variety of real problems and systems, a majority of the methods dealing with those problems treat the data as exactly known, that is, those methods get a solution by formulating an optimization problem with deterministic data. In problems we really face, however, it is in fact a rare case that the related information is perfectly known, but rather there are uncertain data almost always. To overcome these issues, there have recently been proposed a number of solution methods which even include uncertainty into problem formulation, instead of replacing uncertain data by some fixed data. For example, some methods use the expected values of stochastic data [13], or their variances [8], while other methods called robust optimization [3] seek a solution in the worst possible scenario.

Especially, the worst case optimization is essential in dealing with actual problems with uncertain information, in view of the importance of accident prevention in dangerous operations which might lead to disasters like explosions in a large scale chemical plant, or risk avoidance in the finance field which has grown massively with derivatives such as futures trading. In a robust optimization method, if the data are known to belong to some ellipsoidal set, an optimization problem with uncertain data can be represented as a Second-Order Cone Programming (SOCP) problem [1, 3].

On the other hand, there have been just a few works to deal with MPECs under uncertainty [17, 21]. Particularly, very few studies have been done with regard to a robust optimization method for such problems, in spite of its significance. When there is uncertainty in the lower level optimization problem of a bilevel program, it can be formulated as a bilevel program having SOCP as its lower level problem. This paper discusses Mathematical Programs with Second-Order Cone Complementarity Constraints (MPSOCCC), which arise when the lower level SOCP in the bilevel problem is replaced by its KKT conditions. SOCP includes Linear Programming and Quadratically Constrained Quadratic Programming. Moreover, Second-Order Cone Complementarity Conditions (SOCCC) include the ordinary Complementarity Conditions as a special case. Hence MPSOCCC is an upper class of MPCC.

In this paper, we propose a smoothing method for solving MPSOCCC, and discuss its con-

vergence properties. Similarly to MPCC and MPLCC, MPSOCCC is a nonconvex and nondiffer-

entiable problem in general, and therefore it is difficult to deal with directly. Using a smoothing

(5)

function [11], the proposed method constructs a smooth approximation of the nonsmooth problem. The main result of this paper is that the proposed method is guaranteed to have the global convergence property to a stationary point of the MPSOCCC under some assumptions.

The remainder of this paper is organized as follows: In Section 2, we formulate the MP- SOCCC and review the Jordan algebra associated with the Second-Order Cones. In Section 3, we consider a smoothing function and propose a smoothing method for the MPSOCCC. The optimality conditions and convergence properties are discussed in Section 4. Lastly in Section 5, we make some remarks to conclude this paper.

2 Preliminaries

2.1 Bilevel program and MPSOCCC

We consider the following bilevel programming problem:

P : min

x,y f (x, y) s.t. x ∈ X,

y ∈ Y (x),

where f : < ⁿ

¹

^×n

²

→ < is a continuously differentiable function, X ⊆ < ⁿ

¹

, and Y (x) ⊆ < ⁿ

²

represents the solution set of the following Second-Order Cone Program (SOCP) with parameter x:

SOCP(x) : min

y g(x, y)

s.t. h(x, y) := A(x)y + b(x) = 0, y ∈ K ,

where function g : < ⁿ

¹

^× ⁿ

²

→ < is continuously differentiable, A(x) = [A ₁ (x) · · · A _s (x)] ∈ < ^m ^× ⁿ

²

with A i (x) ∈ < ^m ^× ^l

ⁱ

, b(x) ∈ < ^m , and the set K is the Cartesian product of second-order cones K ^l

ⁱ

= { y = (y ₁ , y ₂ ) ^> ∈ < × < ^l

ⁱ

⁻¹ | y ₁ ≥ k y ₂ k} (i = 1, · · · , s), i.e., K = K ^l

¹

× · · · × K ^l

^s

with n ₂ = l ₁ + · · · + l _s .

First we consider the reformulation of P. For this purpose, we make the following assumptions on problems P and SOCP(x):

A 1. X ⊆ < ⁿ

¹

is nonempty and compact.

A 2. For any x ∈ X , the feasible set of SOCP(x) is nonempty.

A 3. For any x ∈ X , g(x, · ) is strongly convex.

Since the second-order cone K ^l

ⁱ

is a convex set, the problem SOCP(x) is a convex pro-

gramming problem under assumption A3. Moreover, from assumptions A2 and A3, the problem

SOCP(x) has a unique solution for every x ∈ X . However the upper level problem P is generally

not a convex programming problem since the feasible set of P is not a convex set in general,

even when SOCP(x) has a unique solution for all x ∈ X .

(6)

Let I (y) denote the index set such that I (y) := { i | y ⁱ ∈ bd K ^l

ⁱ

} for any y ∈ < ⁿ

²

, where y ⁱ ∈ < ^l

ⁱ

is the block component of y and bd K ^l

ⁱ

denotes the boundary of K ^l

ⁱ

. Furthermore, for the matrix A(x) = [A ₁ (x) · · · A _s (x)], let [A _i (x)] _i _∈I _(y) ∈ < ^m ^× ^P

ⁱ^∈I

^l

ⁱ

denote the submatrix consisting of A _i (x), i ∈ I (y). Similarly, we denote the submatrix with components A _i (x), i / ∈ I (y), by [A _i (x)] _{i /} _∈I _(y) ∈ < ^m ^× ^P

^{i /}^∈I

^l

ⁱ

. With these definitions, we introduce the following assumption.

A 4. For any x ∈ X and any optimal solution y of SOCP(x), there exists an index i such that i / ∈ I (y). Furthermore, [A _i (x)] _{i /} _∈I(y) has full row rank.

The KKT conditions for SOCP(x) are given by

∇ y g(x, y) − η − A(x) ^> ζ = 0, A(x)y + b(x) = 0, y ∈ K , η ∈ K , y ^> η = 0,

(1)

where η ∈ < ⁿ

²

and ζ ∈ < ^m are Lagrange multiplier vectors. The last conditions in the above conditions (1) are called Second-Order Cone Complementarity Constraints (SOCCC). Since SOCP(x) is a convex program under our assumptions, the above KKT conditions (1) become the necessary and sufficient optimality condition for this problem. Thus, by replacing SOCP(x) with its KKT conditions, we can reformulate problem P into the nonlinear programming problem involving SOCCC:

MPSOCCC : min f (x, y) s.t. x ∈ X,

∇ y g(x, y) − η − A(x) ^> ζ = 0, A(x)y + b(x) = 0,

y ∈ K , η ∈ K , y ^> η = 0.

2.2 Jordan algebra associated with the SOC

In this subsection, we introduce Jordan algebra, which provides a useful tool for dealing with SOCs.

For two n-dimensional vectors x = (x ₁ , x ₂ ) ∈ < × < ⁿ⁻¹ and y = (y ₁ , y ₂ ) ∈ < × < ⁿ⁻¹ , we define the Jordan product by

x ◦ y := (x ^> y, x ₁ y ₂ + y ₁ x ₂ ) ^> .

Note that the Jordan product generates an n-dimensional vector from two n-dimensional vectors.

For convenience, we denote x ◦ x by x ² , and define the vector e by e := (1, 0, · · · , 0) ^> . Then Jordan product has the following properties [10]:

Property 1. For any x, y, z ∈ < ⁿ , the following properties hold.

1. e ◦ x = x,

2. x ◦ y = y ◦ x,

(7)

3. (x + y) ◦ z = x ◦ z + y ◦ z, 4. x ◦ (x ² + y) = x ² ◦ (x ◦ y).

Property 1 shows that vector e plays the role of the unit vector. Properties 2 and 3 represent commutativity and distributivity, respectively. Notice that the Jordan product is not associative, that is, x ◦ (y ◦ z) 6 = (x ◦ y) ◦ z in general.

The next proposition shows that the second-order cone complementarity condition can be represented in another form by use of the Jordan product [11]:

Proposition 1. For any two vectors x and y in < ⁿ , the relation

x ∈ K ⁿ , y ∈ K ⁿ , x ^> y = 0 ⇐⇒ x ∈ K ⁿ , y ∈ K ⁿ , x ◦ y = 0 holds.

Next we introduce the spectral factorization of vectors in < ⁿ associated with the second-order cone K ⁿ . Let z = (z ₁ , z ₂ ) ∈ < × < ⁿ ⁻ ¹ . Then we can decompose z as

z = λ ₁ u ^{ ¹ ^} + λ ₂ u ^{ ² ^} , where λ ₁ and λ ₂ are called the spectral values of z defined by

λ _i = z ₁ + ( − 1) ⁱ k z ₂ k , i = 1, 2, (2) and u ^{ ¹ ^} and u ^{ ² ^} are called the spectral vectors of z defined by

u ^{i} =

 

 

 

 1 2

1, ( − 1) ⁱ z ₂ k z ₂ k

if z ₂ 6 = 0, 1

2 1, ( − 1) ⁱ w if z ₂ = 0,

i = 1, 2, (3)

where w ∈ < ⁿ ⁻ ¹ is any vector satisfying k w k = 1. Some of the notable features of spectral values and vectors are the following [11, 15].

Property 2. For any vector z ∈ < ⁿ , the spectral values λ ₁ and λ ₂ given by (2) and spectral vectors u ^{ ¹ ^} and u ^{ ² ^} given by (3) possess the following properties:

1. u ^{ ¹ ^} ◦ u ^{ ² ^} = 0, k u ^{ ¹ ^} k = k u ^{ ² ^} k = 1/ √ 2, 2. u ^{ ⁱ ^} ∈ bd K ⁿ , u ^{ ⁱ ^} ◦ u ^{ ⁱ ^} = u ^{ ⁱ ^} , i = 1, 2, 3. λ 1 ≤ λ 2 , λ 1 ≥ 0 ⇐⇒ z ∈ K ⁿ .

The projection mapping P _K

ⁿ

onto the second-order cone K ⁿ is defined by P _K

ⁿ

(z) := arg min

z

⁰

∈K

ⁿ

k z ⁰ − z k .

By use of the spectral factorization, we can express this function explicitly as follows [11]:

P _K

ⁿ

(z) = max { 0, λ ₁ } u ^{ ¹ ^} + max { 0, λ ₂ } u ^{ ² ^} . (4)

(8)

2.3 Reformulation of SOCCC into equation The SOCCC on K = K ^l

¹

× · · · × K ^l

^s

,

y ∈ K , η ∈ K , y ^> η = 0, (5)

can be written componentwise as follows [11, 15]:

y ⁱ ∈ K ^l

ⁱ

, η ⁱ ∈ K ^l

ⁱ

, (y ⁱ ) ^> η ⁱ = 0 (i = 1, · · · , s), (6) where y = (y ¹ , · · · , y ^s ) ^> ∈ < ^l

¹

×· · ·×< ^l

^s

, η = (η ¹ , · · · , η ^s ) ^> ∈ < ^l

¹

×· · ·×< ^l

^s

. For the decomposed SOCCC (6), we introduce functions ϕ ⁱ : < ^l

ⁱ

× < ^l

ⁱ

→ < ^l

ⁱ

(i = 1, · · · , s) satisfying the following relation:

ϕ ⁱ (y ⁱ , η ⁱ ) = 0 ⇐⇒ y ⁱ ∈ K ^l

ⁱ

, η ⁱ ∈ K ^l

ⁱ

, (y ⁱ ) ^> η ⁱ = 0. (7) By using such functions, we can then define the equivalent equation to SOCCC such that

Φ(y, η) = 0 ⇐⇒ y ∈ K , η ∈ K , y ^> η = 0,

where Φ : < ⁿ

²

× < ⁿ

²

→ < ⁿ

²

is a vector-valued function having functions ϕ ⁱ (i = 1, · · · , s) as block components, i.e.,

Φ(y, η) :=



 

ϕ ¹ (y ¹ , η ¹ ) .. . ϕ ^s (y ^s , η ^s )



  .

In [11], it is showed that the following function ϕ ⁱ

_NR

: < ^l

ⁱ

× < ^l

ⁱ

→ < ^l

ⁱ

(i = 1, · · · , s) defined by using the projection mapping P _K

_li

defined by (4) satisfies the relation (7):

ϕ ⁱ

_NR

(y ⁱ , η ⁱ ) := y ⁱ − P _K

_li

(y ⁱ − η ⁱ ).

This is called the natural residual function. Note that P _K

_li

is not differentiable. Using the functions ϕ ⁱ

_NR

, we define function Φ

NR

: < ⁿ

²

× < ⁿ

²

→ < ⁿ

²

by

Φ

NR

(y, η) :=



 

ϕ ¹

_NR

(y ¹ , η ¹ ) .. . ϕ ^s

_NR

(y ^s , η ^s )



  ,

and H ₀ : < ⁿ

¹

× < ⁿ

²

× < ⁿ

²

× < ^m → < ⁿ

²

× < ^m × < ⁿ

²

by H ₀ (x, y, η, ζ ) :=



 

∇ y g(x, y) − η − A(x) ^> ζ A(x)y + b(x)

Φ

NR

(y, η)



  .

Then we can rewrite the KKT conditions (1) of SOCP(x) as

H ₀ (x, w) := H ₀ (x, y, η, ζ) = 0.

(9)

Using the above relation, instead of MPSOCCC, we can consider the following equivalent nonlinear optimization problem:

P ₀ : min f (x, y) s.t. x ∈ X,

H ₀ (x, y, η, ζ ) = 0.

For any x ∈ X and any optimal solution y of SOCP(x), let (η, ζ) ∈ < ⁿ

²

× < ^m denote a solution of the equation H ₀ (x, y, η, ζ ) = 0. Then for any i / ∈ I (y), we have from (7) that η ⁱ = 0.

Hence the first condition of the KKT conditions (1) is rewritten as η ⁱ + A _i (x) ^> ζ = ∇ y

ⁱ

g(x, y), (i ∈ I (y)),

η ⁱ = 0, A _i (x) ^> ζ = ∇ y

ⁱ

g(x, y), (i / ∈ I (y)). (8) Since matrix [A _i (x)] _{i /} _∈I _(y) has full row rank from assumption A4, the matrix



 I ^P

i∈I(y)

l

i

[A i (x)] ^> _i∈I(y) 0 [A _i (x)] ^> _{i /} _∈I(y)



 has full column rank. Therefore the solution of (8) exists uniquely.

The next theorem shows the equivalence of P and P ₀ .

Theorem 1. Assume that A1–A4 hold. Then the next two statements are equivalent.

1. (x ^∗ , y ^∗ ) is a global (local) optimal solution of problem P.

2. There exists a vector (η ^∗ , ζ ^∗ ) such that (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ) is a global (local) optimal solution of problem P 0 .

Proof. First, we assume that (x ^∗ , y ^∗ ) is a local minimizer of problem P, and show the statement 2. Then from assumption A4, there exists a unique point (η ^∗ , ζ ^∗ ) such that (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ) is a feasible point of P ₀ . Suppose that (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ) is not a local minimizer of P ₀ . Then there exists a sequence { (x ^k , y ^k , η ^k , ζ ^k ) } of feasible points of P ₀ converging to (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ) and satisfying f(x ^k , y ^k ) < f (x ^∗ , y ^∗ ) for all k. For such points (x ^k , y ^k , η ^k , ζ ^k ), however, points (x ^k , y ^k ) are feasible to P for all k, which contradicts the fact that (x ^∗ , y ^∗ ) is a local optimal solution of problem P.

Next, assume that (x ^∗ , y ^∗ ) is a global optimal solution of problem P. By what we have just mentioned, there is a unique vector (η ^∗ , ζ ^∗ ) such that (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ) is a local minimizer of P ₀ . If (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ) is not a global minimizer of P ₀ , then there is another point (¯ x, y, ¯ η, ¯ ζ) satisfying ¯ f(¯ x, y) ¯ < f(x ^∗ , y ^∗ ). The point (¯ x, y) is, however, a feasible point of problem P, which therefore ¯ contradicts the assumption that (x ^∗ , y ^∗ ) is a global optimal solution of problem P.

Conversely, assume now that (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ) is a local minimizer of P ₀ . Since y ^∗ ∈ Y (x ^∗ ),

(x ^∗ , y ^∗ ) is a feasible solution of P. Suppose that (x ^∗ , y ^∗ ) is not a local minimizer of P. Then

there exists a sequence { (x ^k , y ^k ) } of feasible points of problem P which converges to (x ^∗ , y ^∗ )

and satisfies f (x ^k , y ^k ) < f (x ^∗ , y ^∗ ) for all k. From assumption A4, there exists a unique vector

(η ^k , ζ ^k ) such that (x ^k , y ^k , η ^k , ζ ^k ) is a feasible point of problem P ₀ for all k. If (η ^k , ζ ^k ) converges

(10)

to (η ^∗ , ζ ^∗ ), we have a contradiction with the local optimality of (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ). We will assume that (η ^k , ζ ^k ) does not converge to (η ^∗ , ζ ^∗ ), and show contradiction.

To begin with, we assume that the sequence { (η ^k , ζ ^k ) } is unbounded. Since (x ^k , y ^k , η ^k , ζ ^k ) is feasible to problem P ₀ for all k, it follows that

∇ y g(x ^k , y ^k ) − η ^k − A(x ^k ) ^> ζ ^k = 0.

Dividing both sides of this equation by k (η ^k , ζ ^k ) ^> k , and passing to the limit k → ∞ , we have (I A(x ^∗ ) ^> ) η ˜

ζ ˜

!

= 0, (9)

where we assume, without loss of generality, lim _k _→∞ ^(η

^k

^,ζ

^k

⁾

^>

k (η

^k

,ζ

^k

)

^>

k = (˜ η, ζ ˜ ) ^> 6 = 0. From SOCCC and the continuity of functions, we obtain ˜ η ⁱ = 0 for index i / ∈ I (y ^∗ ). Therefore using a similar reasoning for the uniqueness of vector (η, ζ) satisfying (8), the vector (˜ η, ζ) satisfying (9) is ˜ uniquely determined as (˜ η, ζ ˜ ) = 0. But this contradicts (˜ η, ζ) ˜ 6 = 0. Hence the sequence { (η ^k , ζ ^k ) } is bonded. Then, without loss of generality, we can assume that there exists a point (¯ η, ζ ¯ ) such that (η ^k , ζ ^k ) → (¯ η, ζ). By the continuity of the functions, we see that the point (x ¯ ^∗ , y ^∗ , η, ¯ ζ ¯ ) is feasible to problem P ₀ with (x ^∗ , y ^∗ , η, ¯ ζ ¯ ) 6 = (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ). From assumption A4, however, there is a unique vector (η, ζ) such that (x ^∗ , y ^∗ , η, ζ) is feasible to P ₀ . This is a contradiction.

Finally, suppose that (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ) is a global optimal solution of problem P ₀ . If (x ^∗ , y ^∗ ) is not a global optimal solution of problem P, then there exists a feasible solution (¯ x, y) of P ¯ such that f (¯ x, y) ¯ < f(x ^∗ , y ^∗ ). From assumption A4, there exists a unique vector (¯ η, ζ) such ¯ that (¯ x, y, ¯ η, ¯ ζ ¯ ) is a feasible solution of problem P 0 , which contradicts the global optimality of (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ ). Hence the point (x ^∗ , y ^∗ ) is a global optimal solution of problem P.

3 Smoothing method for problem P 0

In the previous section we have shown that problem P ₀ is equivalent to problem P. Problem P ₀ is no longer a bilevel program or an MPEC, but an ordinary nonlinear programming problem.

On the other hand, owing to the nondifferentiability of function H ₀ , we cannot apply algorithms using derivatives of constraint functions, such as Newton-like methods. So in this section, we will discuss a smooth approximation of problem P ₀ , which is obtained by smoothing the function H 0 .

For a nondifferentiable function ψ : < ⁿ → < ^m , we consider a function ψ _µ : < ⁿ → < ^m having the following properties with a parameter µ > 0:

1. For any µ > 0, ψ _µ is differentiable.

2. For any x ∈ < ⁿ , lim _µ _→ ₊₀ ψ _µ (x) = ψ(x).

Any function having these properties is called a smoothing function of ψ.

We will now discuss smoothing functions of ϕ ⁱ

_NR

defined in the previous section. For this purpose, we first consider a continuously differentiable convex function ˆ g : < → < having the properties

α→−∞ lim ˆ g(α) = 0, lim

α→∞ (ˆ g(α) − α) = 0, 0 < ˆ g ⁰ (α) < 1. (10)

(11)

For example, the functions

ˆ

g(α) = ^p α ² + 4 + α /2 and

ˆ

g(α) = log (exp(α) + 1)

have the above properties [7]. With the use of such ˆ g and a parameter µ > 0, we can define P _K

ⁿ

_,µ : < ⁿ → < ⁿ by

P _K

ⁿ

_,µ (z) := µˆ g( λ ₁

µ )u ^{ ¹ ^} + µˆ g( λ ₂ µ )u ^{ ² ^} ,

where λ ₁ and λ ₂ are the spectral values of z defined by (2), and u ^{1} and u ^{2} are the spectral vectors of z defined by (3). Then this function P _K

ⁿ

_,µ becomes a smoothing function of the projection mapping P _K

ⁿ

onto the SOC K ⁿ [11]. Hence using this function, we can define a smoothing function ϕ ⁱ _µ : < ^l

ⁱ

× < ^l

ⁱ

→ < ^l

ⁱ

of ϕ ⁱ

_NR

by

ϕ ⁱ _µ (y ⁱ , η ⁱ ) := y ⁱ − P _K

_li

_,µ (y ⁱ − η ⁱ ).

In addition, let Φ _µ : < ⁿ

²

× < ⁿ

²

→ < ⁿ

²

and H _µ : < ⁿ

¹

× < ⁿ

²

× < ⁿ

²

× < ^m → < ⁿ

²

× < ^m × < ⁿ

²

be defined by

Φ _µ (y, η) :=



 



ϕ ¹ _µ (y ¹ , η ¹ ) .. . ϕ ^s _µ (y ^s , η ^s )



 



and

H _µ (x, w) := H _µ (x, y, η, ζ ) :=



 

∇ y g(x, y) − η − A(x) ^> ζ A(x)y + b(x)

Φ µ (y, η)



  .

Then for any µ > 0, the function H _µ is differentiable and also has the properties of a smoothing function of H ₀ .

According to the above consideration, we can formulate a nonlinear programming problem with parameter µ > 0 as follows:

P _µ : min f (x, y) s.t. x ∈ X,

H _µ (x, w) = 0.

This problem can be seen as an approximation of problem P ₀ having a parameter µ > 0. In particular, P _µ is a smooth optimization problem for any µ > 0.

We now make new assumptions on function H ₀ and the smoothing function H _µ :

A 5. For any x ¯ ∈ X and w ¯ ∈ < ²ⁿ

²

^+m such that H ₀ (¯ x, w) = 0, all the matrices belonging to the ¯

generalized Jacobian ∂ _w H ₀ (¯ x, w) ¯ are nonsingular.

(12)

A 6. For any x ¯ ∈ X and µ > 0, there exists the inverse matrix ∇ w H _µ (¯ x, w) ⁻ ¹ ∈ < ⁽²ⁿ

²

^+m) ^× ⁽²ⁿ

²

^+m) of the Jacobian of H _µ (¯ x, w) for all w ∈ < ²ⁿ

²

^+m . Furthermore, there exists a constant Γ > 0 such that k∇ w H _µ (¯ x, w) ⁻ ¹ k ≤ Γ for all w ∈ < ²ⁿ

²

^+m .

Under assumption A6, Hadmard Theorem [19] ensures that H _µ (¯ x, · ) is homeomorphism of

< ²ⁿ

²

^+m onto < ²ⁿ

²

^+m for any µ > 0 and ¯ x ∈ X , that is, the function H µ (¯ x, · ) is one-to-one and H _µ (¯ x, · ) and H _µ (¯ x, · ) ⁻ ¹ are continuous. Especially, there exists a unique solution of the equation H _µ (¯ x, · ) = 0.

For µ > 0, let F _µ represent the feasible set of P _µ , i.e., F _µ := { (x, w) | x ∈ X, H _µ (x, w) = 0 } . The following theorem implies that there exists an accumulation point of a sequence generated by the smoothing method.

Theorem 2. Assume that A1–A6 hold, and let µ > ¯ 0 be any fixed constant. Then F µ is nonempty and uniformly bounded on [0, µ]. ¯

Proof. From the definition of F _µ , assumption A1, and the fact that the equation H _µ (x, w) = 0 (µ ≥ 0) has at least one solution for any x ∈ X (by assumption A4 or A6), there is (x, w) ∈ F µ for any µ ∈ [0, µ]. As ¯ X is compact, F µ is bounded with respect to the x-component.

Assuming that F µ is not bounded for the w-component, we will derive a contradiction. Under this assumption, there are sequences { µ ^k } , { x ^k } , and { w ^k } such that (x ^k , w ^k ) ∈ F _µ

k

and µ ^k →

˜

µ ∈ [0, µ], ¯ k w ^k k → ∞ as k → ∞ . We can now assume without loss of generality that { x ^k } has a limit point ˜ x ∈ X . By assumptions A2–A4 and A6, there exists a unique ˜ w satisfying ˜ w ∈ F _µ _˜ (˜ x), namely H _µ _˜ (˜ x, w) = 0 holds. On the other hand, from assumption A5 or A6, the (generalized) ˜ Jacobian of H _µ _˜ (˜ x, w) is nonsingular. Hence by the implicit function theorem there exists a ˜ continuous function w(µ, x) satisfying H _µ (x, w(µ, x)) = 0 in a neighborhood of the point (˜ µ, x). ˜ Since the solution of equation H _µ (x, w) = 0 is also determined uniquely in a neighborhood of (˜ µ, x) by assumption A6, it eventually holds for sufficiently large ˜ k that w ^k = w(µ ^k , x ^k ). Since the function w( · , · ) is continuous, and since the sequences { µ ^k } and { x ^k } are both bounded, there exists a constant β > 0 such that lim _k→∞ k w(µ ^k , x ^k ) k ≤ β, which contradicts the unboundedness of the sequence { w ^k } .

4 Optimality conditions

In this section, we discuss optimality conditions for problems P ₀ and P _µ . In the case of µ > 0, P _µ is a smooth nonlinear program and hence the optimality conditions can be written as KKT conditions. Our purpose is to obtain an optimal solution of MPSOCCC or P ₀ from a KKT point of P _µ . To this end, we first refer to the optimality conditions for problem P ₀ .

In the following, we suppose that the set X is specified as X := { x | ˜ g(x) ≤ 0, ˜ h(x) = 0 } , where ˜ g : < ⁿ

¹

→ < ^p and ˜ h : < ⁿ

¹

→ < ^q are both continuously differentiable functions.

Since P ₀ is a nonsmooth problem, we cannot consider the ordinary KKT conditions. In

[9], by using C-subdifferential of nondifferential functions, necessary conditions for optimality

are represented as the following Fritz-John conditions: If the point (x, y, η, ζ) is optimal for

(13)

P ₀ , then there exist vectors δ ∈ < + , θ ∈ < ⁿ

²

, ρ ∈ < ^m , σ ∈ < ⁿ

²

, ν ∈ < ^p + , ξ ∈ < ^q such that (δ, θ, ρ, σ, ν, ξ) 6 = 0 and

 

 



 

  0 ∈ δ



 

 

∇ x f (x, y)

∇ y f (x, y) 0 0



 

  +



 

 

∇ x L(x, y, η, ζ )

∇ y L(x, y, η, ζ)

∇ η L(x, y, η, ζ)

∇ ζ L(x, y, η, ζ)



 

  θ +



 

 

∇ x (A(x)y) + ∇ b(x) A(x) ^>

0 0



 

  ρ

+



 



0 

 

∂ _y

1

ϕ ¹

_NR

(y ¹ , η ¹ ) 0 . ..

0 ∂ _y

^s

ϕ ^s

_NR

(y ^s , η ^s )



 



 

∂ _η

1

ϕ ¹

_NR

(y ¹ , η ¹ ) 0 . ..

0 ∂ _η

^s

ϕ ^s

_NR

(y ^s , η ^s )



 

0 

 

 σ +



 

 

∇ x ˜ g(x) 0 0 0



 

  ν +



 

 

∇ x ˜ h(x) 0 0 0



 

  ξ,

L(x, y, η, ζ) = 0, A(x)y + b(x) = 0,

ϕ ⁱ

_NR

(y ⁱ , η ⁱ ) = 0, (i = 1, · · · , s),

˜ h(x) = 0,

˜

g(x) ≤ 0, ν ≥ 0, ν ^> g(x) = 0, ˜

(11)

where L : < ⁿ

¹

× < ⁿ

²

× < ⁿ

²

× < ^m → < ⁿ

²

is defined by L(x, y, η, ζ ) := ∇ y g(x, y) − η − A(x) ^> ζ.

According to [16], by letting z ⁱ := y ⁱ − η ⁱ , the C-subdifferential of the function ϕ ⁱ

_NR

(y ⁱ , η ⁱ ) is calculated as

∂ _y

i

ϕ ⁱ

_NR

(y ⁱ , η ⁱ ) = I _l

_i

− ∂P _K

_li

(z ⁱ ),

∂ _η

i

ϕ ⁱ

_NR

(y ⁱ , η ⁱ ) = ∂P _K

_li

(z ⁱ ), (12) where in the case of z ₁ ⁱ 6 = ±|| z ₂ ⁱ || , P _K

_li

is differentiable and its derivative is given as

∇ P _K

_li

(z ⁱ ) =

 

 



 

 

0, (z ₁ ⁱ < −k z ⁱ ₂ k ) I _l

_i

, (z ₁ ⁱ > k z ₂ ⁱ k ) 1

2 1 (v ⁱ ) ^>

v ⁱ M

!

, ( −k z ₂ ⁱ k < z ₁ ⁱ < k z ⁱ ₂ k )

(13)

with v ⁱ := z ⁱ ₂

k z ⁱ ₂ k , M := z ₁ ⁱ k z ₂ ⁱ k + 1

!

I _l

_i

₋ ₁ − z ₁ ⁱ

k z ₂ ⁱ k v ⁱ (v ⁱ ) ^> ,

while, in the case of z ₁ ⁱ = ±|| z ₂ ⁱ || , P _K

_li

is not differentiable and its C-subdifferential is given as follows: if z ₂ ⁱ 6 = 0 and z ₁ ⁱ = k z ⁱ ₂ k , then

∂P _K

_li

(z ⁱ ) = co (

I _l

_i

, 1 2

1 (v ⁱ ) ^>

v ⁱ M

!)

, with v ⁱ := z ⁱ ₂

k z ₂ ⁱ k , M := 2I _l

_i

₋₁ − v ⁱ (v ⁱ ) ^> , (14) if z ₂ ⁱ 6 = 0 and z ₁ ⁱ = −k z ₂ ⁱ k , then

∂P _K

_li

(z ⁱ ) = co (

0, 1 2

1 (v ⁱ ) ^>

v ⁱ M

!)

, with v ⁱ := z ₂ ⁱ

k z ⁱ ₂ k , M := v ⁱ (v ⁱ ) ^> , (15)

(14)

finally if z ⁱ = 0, then

∂P _K

_li

(z ⁱ ) = co (

{ 0 } ∪ { I _l

_i

} ∪ ( 1

2 1 (v ⁱ ) ^>

v ⁱ M

!

M = (v ⁱ ₀ + 1)I _l

_i

₋₁ − v ₀ ⁱ v ⁱ (v ⁱ ) ^>

for some | v ⁱ ₀ | ≤ 1 and k v ⁱ k = 1 ))

, (16) where co denotes the convex hull.

If δ 6 = 0 holds in the Fritz-John conditions (11), then we can assume without loss of generality that δ = 1, and conditions (11) become the KKT conditions for problem P ₀ :

 

 



 

  0 ∈



 

 

∇ x f (x, y)

∇ y f (x, y) 0 0



 

  +



 

 

∇ x L(x, y, η, ζ )

∇ y L(x, y, η, ζ )

∇ η L(x, y, η, ζ )

∇ ζ L(x, y, η, ζ )



 

  θ +



 

 

∇ x (A(x)y) + ∇ b(x) A(x) ^>

0 0



 

  ρ

+



 



0 

 

∂ _y

¹

ϕ ¹

_NR

(y ¹ , η ¹ ) 0 . ..

0 ∂ _y

^s

ϕ ^s

_NR

(y ^s , η ^s )



 



 

∂ _η

1

ϕ ¹

_NR

(y ¹ , η ¹ ) 0 . ..

0 ∂ _η

^s

ϕ ^s

_NR

(y ^s , η ^s )



 

0 

 

 σ +



 

 

∇ x g(x) ˜ 0 0 0



 

  ν +



 

 

∇ x ˜ h(x) 0 0 0



 

  ξ,

L(x, y, η, ζ) = 0, A(x)y + b(x) = 0,

ϕ ⁱ

_NR

(y ⁱ , η ⁱ ) = 0, (i = 1, · · · , s),

˜ h(x) = 0,

˜

g(x) ≤ 0, ν ≥ 0, ν ^> g(x) = 0. ˜

(17)

Now let ˜ I (x) denote the index set of the active constraints in ˜ g _i (x) ≤ 0, i.e., ˜ I (x) :=

{ i | ˜ g _i (x) = 0 } . We introduce the following linear independence assumption.

A 7. For any point (x, y, η, ζ ) satisfying the Fritz-John conditions (11), vectors ∇ g ˜ _i (x) (i ∈ I ˜ (x)), ∇ ˜ h _j (x) (j = 1, · · · , q) are linearly independent.

Under this assumption, it can be shown that every Fritz-John point satisfies the KKT conditions (17).

Theorem 3. Assume that A1, A2, A5 and A7 hold. If (x, y, η, ζ ) satisfies Fritz-John conditions (11) with multipliers (δ, θ, ρ, σ, ν, ξ), then δ is not equal to zero.

Proof. Suppose that (x, y, η, ζ ) satisfies the Fritz-John conditions (11) with δ = 0. Then there

(15)

exist (θ, ρ, σ, ν, ξ) 6 = 0 satisfying the following system:

0 ∈



 

 

∇ x L(x, y, η, ζ)

∇ y L(x, y, η, ζ)

∇ η L(x, y, η, ζ)

∇ ζ L(x, y, η, ζ)



 

  θ +



 

 

∇ x (A(x)y) + ∇ b(x) A(x) ^>

0 0



 

  ρ

+



 



0 

 

∂ _y

1

ϕ ¹

_NR

(y ¹ , η ¹ ) 0 . ..

0 ∂ _y

^s

ϕ ^s

_NR

(y ^s , η ^s )



 



 

∂ _η

1

ϕ ¹

_NR

(y ¹ , η ¹ ) 0 . ..

0 ∂ _η

^s

ϕ ^s

_NR

(y ^s , η ^s )



 

0 

 

 σ +



 

 

∇ x g(x) ˜ 0 0 0



 

  ν +



 

 

∇ x ˜ h(x) 0 0 0



 

  ξ, (18)

L(x, y, η, ζ ) = 0, A(x)y + b(x) = 0,

ϕ ⁱ

_NR

(y ⁱ , η ⁱ ) = 0, (i = 1, · · · , s),

˜ h(x) = 0,

˜

g(x) ≤ 0, ν ≥ 0, ν ^> g(x) = 0. ˜ (19)

Note that (18) can be rewritten as

0 = ^h ∇ x L(x, y, η, ζ ) ∇ x h(x, y) ∇ x ˜ g(x) ∇ x ˜ h(x) ⁱ



 

  θ ρ ν ξ



 

  , (20)

0 ∈



 



∇ y L(x, y, η, ζ ) A(x) ^>



 

∂ _y

1

ϕ ¹

_NR

(y ¹ , η ¹ ) 0 . ..

0 ∂ _y

^s

ϕ ^s

_NR

(y ^s , η ^s )



 

∇ η L(x, y, η, ζ ) 0



 

∂ _η

¹

ϕ ¹

_NR

(y ¹ , η ¹ ) 0 . ..

0 ∂ _η

^s

ϕ ^s

_NR

(y ^s , η ^s )



 

∇ ζ L(x, y, η, ζ) 0 0



 





  θ ρ σ



  . (21)

Since the matrix on the right-hand side of (21) represents the generalized Jacobian ∂ _w H ₀ (x, w), it is nonsingular by assumption A5. Hence (21) implies that (θ, ρ, σ) = 0. Furthermore it follows from (20) together with the complementarity condition (19) and assumption A7 that (ν, ξ) = 0, which contradicts (θ, ρ, σ, ν, ξ) 6 = 0.

Next we consider optimality conditions for problem P µ . Since problem P µ is a smooth

optimization problem, its KKT conditions state that there exist Lagrange multipliers θ ∈ < ⁿ

²

,

(16)

ρ ∈ < ^m , σ ∈ < ⁿ

²

, ν ∈ < ^p + and ξ ∈ < ^q satisfying

 

 

 

 

 0 ∈



 

 

∇ x f (x, y)

∇ y f (x, y) 0 0



 

  +



 

 

∇ x L(x, y, η, ζ )

∇ y L(x, y, η, ζ )

∇ η L(x, y, η, ζ )

∇ ζ L(x, y, η, ζ )



 

  θ +



 

 

∇ x (A(x)y) + ∇ b(x) A(x) ^>

0 0



 

  ρ

+



 

 

0 

 



∇ y

¹

ϕ ¹ _µ (y ¹ , η ¹ ) 0 . ..

0 ∇ y

^s

ϕ ^s _µ (y ^s , η ^s )



 





 



∇ η

¹

ϕ ¹ _µ (y ¹ , η ¹ ) 0 . ..

0 ∇ η

^s

ϕ ^s _µ (y ^s , η ^s )



 



0 

 

  σ +



 

 

∇ x g(x) ˜ 0 0 0



 

  ν +



 

 

∇ x ˜ h(x) 0 0 0



 

  ξ,

L(x, y, η, ζ) = 0, A(x)y + b(x) = 0,

ϕ ⁱ _µ (y ⁱ , η ⁱ ) = 0, (i = 1, · · · , s),

˜ h(x) = 0,

˜

g(x) ≤ 0, ν ≥ 0, ν ^> g(x) = 0, ˜

(22)

where ∇ y

ⁱ

ϕ ⁱ _µ and ∇ η

ⁱ

ϕ ⁱ _µ are calculated by letting z ⁱ := y ⁱ − η ⁱ as follows [11]:

∇ y

ⁱ

ϕ ⁱ _µ (y ⁱ , η ⁱ ) = I _l

_i

− ∇ P _K

_li

_,µ (z ⁱ ),

∇ η

ⁱ

ϕ ⁱ _µ (y ⁱ , η ⁱ ) = ∇ P _K

_li

_,µ (z ⁱ ), (23)

∇ P _K

_li

_,µ (z ⁱ ) =

 

 



 

 

"

b i c i (v ⁱ ) ^>

c _i v ⁱ a _i I _l

_i

₋ ₁ + (b _i − a _i )v ⁱ (v ⁱ ) ^>

#

, (z ₂ 6 = 0)

ˆ g ⁰ ( z 1

µ )I _l

_i

, (z 2 = 0),

(24)

where

v ⁱ := z ₂ ⁱ k z ₂ ⁱ k , a _i :=

µ

ˆ

g( ^λ _µ

ⁱ²

) − g( ˆ ^λ _µ

ⁱ¹

)

λ ⁱ ₂ − λ ⁱ ₁ , b _i := 1

2 ˆ g ⁰ ( λ ⁱ ₂

µ ) + ˆ g ⁰ ( λ ⁱ ₁ µ )

!

, c _i := 1

2 g ˆ ⁰ ( λ ⁱ ₂

µ ) − ˆ g ⁰ ( λ ⁱ ₁ µ )

!

, (25) λ ⁱ _j := z ₁ ⁱ + ( − 1) ^j k z ₂ ⁱ k , j = 1, 2. (26) The differences between these two optimality conditions (17) and (22) lie in the function ϕ ⁱ

_NR

in (17) and ϕ ⁱ _µ in (22), and the C-subdifferential and the ordinary differential for these functions.

A limit of KKT points for P _µ may be expected to satisfy the optimality conditions (17) for

problem P ₀ under suitable assumptions, as shown in the next theorem. In fact, to get a solution

of MPSOCCC, we may employ a smoothing method which sequentially computes KKT points

for P _µ with µ > 0 tending to zero.

(17)

Theorem 4. Assume that A1, A2 and A7 hold. For any sequence { µ ^k } such that µ ^k > 0 and µ ^k → 0, let (x ^k , y ^k , η ^k , ζ ^k ) satisfy the KKT conditions for P _µ

k

with Lagrange multipliers (θ ^k , ρ ^k , σ ^k , ν ^k ). Assume that the sequence { (x ^k , y ^k , η ^k , ζ ^k , θ ^k , ρ ^k , σ ^k , ν ^k ) } has an accumulation point. Then every accumulation point (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ , θ ^∗ , ρ ^∗ , σ ^∗ , ν ^∗ ) satisfies the optimality conditions (17) for P ₀ .

Proof. Without loss of generality, we assume that the sequence { (x ^k , y ^k , η ^k , ζ ^k , θ ^k , ρ ^k , σ ^k , ν ^k ) } converges to (x ^∗ , y ^∗ , η ^∗ , ζ ^∗ , θ ^∗ , ρ ^∗ , σ ^∗ , ν ^∗ ) as k → ∞ . From the assumptions of the theorem, (x ^k , y ^k , η ^k , ζ ^k , θ ^k , ρ ^k , σ ^k , ν ^k ) satisfies conditions (22) for all k. For the continuity of the functions involved, ∇ f (x ^k , y ^k ), ∇ L(x ^k , y ^k , η ^k , ζ ^k )θ ^k , ∇ h(x ^k , y ^k )ρ ^k , ∇ g(x ˜ ^k )ν ^k , ∇ ˜ h(x ^k )ξ ^k , L(x ^k , y ^k , η ^k , ζ ^k )θ ^k , A(x ^k )y ^k +b(x ^k ), ϕ ⁱ _µ

k

(y ^k , η ^k ), (i = 1, · · · , s), ˜ h(x ^k ), ˜ g(x ^k ) and (ν ^k ) ^> ˜ g(x ^k ) converge to ∇ f (x ^∗ , y ^∗ ),

∇ L(x ^∗ , y ^∗ , η ^∗ , ζ ^∗ )θ ^∗ , ∇ h(x ^∗ , y ^∗ )ρ ^∗ , ∇ g(x ˜ ^∗ )ν ^∗ , ∇ ˜ h(x ^∗ )ξ ^∗ , L(x ^∗ , y ^∗ , η ^∗ , ζ ^∗ )θ ^∗ , A(x ^∗ )y ^∗ + b(x ^∗ ), ϕ ⁱ

_NR

(y ^∗ , η ^∗ ), (i = 1, · · · , s), ˜ h(x ^∗ ), ˜ g(x ^∗ ) and (ν ^∗ ) ^> g(x ˜ ^∗ ), respectively. Hence it is enough to prove that

k→∞ lim ∇ ϕ ⁱ _µ

k

((y ⁱ ) ^k , (η ⁱ ) ^k ) ∈ ∂ϕ ⁱ

_NR

((y ⁱ ) ^∗ , (η ⁱ ) ^∗ ) (27) holds true for every i ∈ { 1, · · · , s } . Moreover, from the relation between (12) and (23), it is sufficient for (27) to show that

k lim →∞ ∇ P _K

_li

_,µ

k

((z ⁱ ) ^k ) ∈ ∂P _K

_li

((z ⁱ ) ^∗ ), (28) where (z ⁱ ) ^k := (y ⁱ ) ^k − (η ⁱ ) ^k .

For any k and i ∈ { 1, · · · , s } , define a ^k _i , b ^k _i , c ^k _i and (λ ⁱ _j ) ^k (j = 1, 2) by (25) and (26). When lim _k _→∞ (λ ⁱ _j ) ^k 6 = 0, since µ ^k → 0 as k → ∞ , we have ^| ^(λ _µ

ⁱ^j_k

⁾

^k

^| → ∞ . Thus from the properties (10) of function ˆ g, the following relations hold:

if lim

k→∞ (λ ⁱ _j ) ^k < 0 then lim

k→∞ g( ˆ (λ ⁱ _j ) ^k

µ ^k ) = 0, lim

k→∞ g ˆ ⁰ ( (λ ⁱ _j ) ^k µ ^k ) = 0, if lim

k →∞ (λ ⁱ _j ) ^k > 0 then lim

k →∞ g( ˆ (λ ⁱ _j ) ^k

µ ^k ) − (λ ⁱ _j ) ^k µ ^k

!

= 0, lim

k →∞ ˆ g ⁰ ( (λ ⁱ _j ) ^k µ ^k ) = 1.

(29)

On the other hand, when lim _k _→∞ (λ ⁱ _j ) ^k = 0, if lim _k _→∞ ^(λ

i j

)

^k

µ

^k

= −∞ hold, then

k lim →∞ g( ˆ (λ ⁱ _j ) ^k µ ^k ) = 0, if lim _k _→∞ ^(λ _µ

ⁱ^j_k

⁾

^k

= ∞ hold, then

k→∞ lim g( ˆ (λ ⁱ _j ) ^k

µ ^k ) − (λ ⁱ _j ) ^k µ ^k

!

= 0, and finally if lim sup _k→∞

(λ

ⁱ_j

)

^k

µ

^k

< ∞ , then by the continuity of function ˆ g, we have

lim sup

k →∞

g( ˆ (λ ⁱ _j ) ^k µ ^k )

< ∞ .

(18)

As a result, in each case we have

k→∞ lim

µ ^k g( ˆ (λ ⁱ _j ) ^k µ ^k )

= 0. (30)

Using the above relations, we will show that a limit of ∇ P _K

_li

_,µ

k

((z ⁱ ) ^k ) belongs to the set

∂P _K

_li

((z ⁱ ) ^∗ ) represented by (13)–(16) in each of the following cases:

1. (z ₁ ⁱ ) ^∗ < −k (z ₂ ⁱ ) ^∗ k , 2. (z ₁ ⁱ ) ^∗ > k (z ⁱ ₂ ) ^∗ k ,

3. −k (z ₂ ⁱ ) ^∗ k < (z ₁ ⁱ ) ^∗ < k (z ₂ ⁱ ) ^∗ k , 4. (z ₁ ⁱ ) ^∗ = k (z ⁱ ₂ ) ^∗ k 6 = 0,

5. (z ₁ ⁱ ) ^∗ = −k (z ⁱ ₂ ) ^∗ k 6 = 0, 6. (z ⁱ ) ^∗ = 0,

where (z ⁱ ) ^∗ := lim _k _→∞ (z ⁱ ) ^k . Similarly, we define a ^∗ _i := lim _k _→∞ a ^k _i , b ^∗ _i := lim _k _→∞ b ^k _i , c ^∗ _i :=

lim _k→∞ c ^k _i and (λ ⁱ _j ) ^∗ := lim _k→∞ (λ ⁱ _j ) ^k (j = 1, 2).

Case 1. (z ₁ ⁱ ) ^∗ < −k (z ⁱ ₂ ) ^∗ k

By taking an appropriate subsequence if necessary, it is sufficient to consider the following two cases: (i) k (z ⁱ ₂ ) ^k k = 0 holds for all k, (ii) k (z ₂ ⁱ ) ^k k 6 = 0 holds for all k.

First, we consider the case that k (z ⁱ ₂ ) ^k k = 0 holds for all k. Since lim _k _→∞ ^(z _µ

¹ⁱ_k

⁾

^k

= −∞ holds from (z ₁ ⁱ ) ^∗ < 0, it follows from (24) and (10) that

k lim →∞ ∇ P _K

_li

_,µ

k

((z ⁱ ) ^k ) = lim

k →∞ g ˆ ⁰ ( (z ₁ ⁱ ) ^k

µ ^k )I _l

_i

= 0.

We next consider the case that k (z ₂ ⁱ ) ^k k 6 = 0 holds for all k. It follows from the assumption (z ₁ ⁱ ) ^∗ < −k (z ⁱ ₂ ) ^∗ k along with (26) that lim _k→∞ (λ ⁱ ₁ ) ^k ≤ lim _k→∞ (λ ⁱ ₂ ) ^k < 0. Therefore from the definition (25) of b ^k _i and c ^k _i and (29), we obtain

b ^∗ _i = c ^∗ _i = 0.

Since (λ ⁱ ₁ ) ^k < (λ ⁱ ₂ ) ^k holds for all k, we have from the mean value theorem that there exist α ^k _i ∈

(λ

ⁱ₁

)

^k

µ

^k

, ^(λ _µ

ⁱ²_k

⁾

^k

for all k such that

ˆ

g ⁰ (α ^k _i ) = a ^k _i = g( ˆ ^(λ _µ

ⁱ²k

⁾

^k

) − g( ˆ ^(λ _µ

ⁱ¹k

⁾

^k

)

(λ

ⁱ₂

)

^k

µ

^k

− ^(λ _µ

ⁱ¹k

⁾

^k

.

As shown above, we have lim _k _→∞ (λ ⁱ ₁ ) ^k ≤ lim _k _→∞ (λ ⁱ ₂ ) ^k < 0, which implies lim _k _→∞ α ^k _i = −∞ . Moreover, we have

a ^∗ _i = lim

k →∞ a ^k _i = lim

k →∞ g ˆ ⁰ (a ^k _i ) = 0.

A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints