# A New Smoothing Method for Mathematical Programs with Complementarity Constraints Based on Logarithm-Exponential Function

Authors: Yu Chen; Zhong Wan
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We present a new smoothing method based on a logarithm-exponential function for mathematical program with complementarity constraints (MPCC). Different from the existing smoothing methods available in the literature, we construct an approximate smooth problem of MPCC by partly smoothing the complementarity constraints. With this new method, it is proved that the Mangasarian-Fromovitz constraint qualification holds for the approximate smooth problem. Convergence of the approximate solution sequence, generated by solving a series of smooth perturbed subproblems, is investigated. Under the weaker constraint qualification MPCC-Cone-Continuity Property, it is proved that any accumulation point of the approximate solution sequence is a M-stationary point of the original MPCC. Preliminary numerical results indicate that the developed algorithm based on the partly smoothing method is efficient, particularly in comparison with the other similar ones.


---

## Body

## 1. Introduction

Consider the following mathematical program with complementarity constraints (MPCC):(1)minfxs.t.gx≤0,hx=0,Gx≥0,Hx≥0,GxTHx=0,where f:Rn→R, g:Rn→Rm, h:Rn→Rp, and G, H:Rn→Rl are all continuously differentiable functions. MPCC (1) stems from many fields, such as shape design, economic equilibrium, and multilevel game (see [1, 2]). In the past two decades, it has attracted great interest of research from applied mathematicians and engineers. One of the main challenges in studying such a problem is that the constraints in (1) may fail to satisfy some standard constraint qualification at a feasible point. Thus, many fundamental theoretical results and powerful algorithms for an ordinary smooth optimization problem cannot be directly employed to solve (1). Actually, some specific approaches have been proposed for solving MPCC (1), such as the sequential quadratic programming approach in [3–8], the interior point methods in [9, 10], the penalty approach in [11–13], the lifting method in [14], the relaxation approach in [15–22], and the smoothing methods in [23–30].Among them, the smoothing method is one of the most popular approaches, which uses a smoothing function to approximate the complementarity constraints in (1). As a result, the original MPCC is reformulated into a standard smooth optimization model. Then, an approximate solution of MPCC is obtained by solving a series of smooth perturbed subproblems. Therefore, it is often necessary to prove theoretically that the sequence of approximate solutions converges to a stationary point (or an optimal solution) of the original MPCC.Very recently, in [31], a partially smoothing Jacobian method is proposed for solving nonlinear complementarity problems with P0 function. Numerical experiments have shown that this smoothing method outperforms the existent ones, particularly in comparison with the state-of-the-art methods derived from the classical Fischer Burmeister smoothing function and aggregation function.Inspired by the idea of partly smoothing in [31], we intend to construct an approximate problem of (1) by partly smoothing the complementarity constraints in (1) such that the degree of approximation is improved between MPCC (1) and the constructed smooth problem. Specifically, in the existing results (see, for example, [23–30]), the complementarity constraints G(x)≥0, H(x)≥0, G(x)TH(x)=0 are often wholly approximated by a system of smooth equations with a perturbation parameter. In contrast, we construct an approximate problem of (1) only by replacing G(x)TH(x)=0 with a system of inequalities such that (1) is transformed into a standard smooth optimization problem. Consequently, under a weaker constraint qualification, called the MPCC-Cone-Continuity Property (MPCC-CCP), we can prove theoretically that any accumulation point of the approximate solution sequence is M-stationary to the original MPCC. Numerical experiments will be employed to show the efficiency of the proposed smoothing method, particularly in comparison with the other similar methods available in the literature.The rest of the paper is organized as follows. In next section, we first review some concepts of nonlinear programming and MPCC; then we present a new smoothing method of Problem (1). Section 3 is devoted to establishment of convergence theory. In Section 4, numerical performance of the new method is reported. Final remarks are made in the last section.Throughout this paper,Gi represents the i-th component of a vector G and similar notations are used for vector-valued functions. ϝ denotes the feasible region of Problem (1). For a function g:Rn→Rm and a given vector x∈Rn, Ig(x) stands for the active index set of g at x, i.e., i:gix=0 for all i∈Ig(x). For a given vector α, supp(α)≜i:αi≠0 denotes the support set of α.


## 2. Preliminaries and New Smoothing Approach

In this section, some basic concepts will be first stated, which are necessary to the development of a new smoothing method. Then, we will propose a new smoothing method of Problem (1).A typical mathematical model of nonlinear programming (NLP) problems is expressed as follows:(2)minfxs.t.gx≤0,hx=0,where f:Rn→R, g:Rn→Rm, h:Rn→Rp are all continuously differentiable functions.DenoteF the feasible region of Problem (2). Stationary points in F play a fundamental role in finding a minimizer of (2).Definition 1 (see [32]).
A pointx∗∈F is called a stationary point of Problem (2) if there exist λ∈R+m and μ∈Rp such that (x∗,λ,μ)∈Rn+m+p is a KKT point of (2); that is to say(3)∇fx∗+∑i=1mλi∇gix∗+∑i=1pμi∇hix∗=0,λigix∗=0,i=1,2,…,m,where λ and μ are called the vectors of multipliers.Since it is usually not possible to solve the NLPs exactly, mostly of the standard NLPs method stops when the KKT conditions are satisfied approximately. Thus, approximate KKT point is very necessary.Definition 2.
A pointx∗∈F is called an Approximate Karush-Kuhn-Tucker (AKKT) point of Problem (2) if there are sequences xk⊂Rn,xk→x∗,λk⊂R+m,μk⊂Rp, and εk⊂R+, where xk→x∗,εk→0+, such that(4)hxk≤εk,gixk≤εk,i=1,2,…,m,∇fxk+∑i=1mλi∇gixk+∑i=1pμi∇hixk≤εk,λi=0,ifgixk<-εk,i=1,2,…,m.The well-known Karush-Kuhn-Tucker theorem declares that a local minimizerx∗ of Problem (2) is a stationary point if some constraint qualification holds. Linearly independent constraint qualification (LICQ) and Mangasarian-Fromovitz constraint qualification (MFCQ) are the most popular constraint qualifications.Definition 3.
A feasible pointx∗ of (2) is said to satisfy the MFCQ if the gradients {∇hi(x∗)∣i=1,2,…,p} are linearly independent and there exists a vector d∈Rn such that(5)∇gix∗Td<0i∈Igx∗,∇hix∗Td=0,i=1,2,…,p.In [33], the above MFCQ is described by a concept of positive linearly dependent.Definition 4 (see [33]).
A finite set of vectors{ai∣i∈I1}∪{bi∣i∈I2} is said to be positive linearly dependent if there exists (α,β)∈R|I1|+|I2|≠0 such that for all i∈I1, αi≥0, and(6)∑i∈I1αiai+∑i∈I2βibi=0.
Conversely, if (6) holds if and only if (α,β)=0, then the group of vectors is called to be positive linearly independent.The following result has been proved in [33].Lemma 5 (see [33]).
A pointx∗∈F satisfies the MFCQ if and only if the gradients(7)∇gix∗∣i∈Igx∗∪∇hix∗∣i=1,2,…,pare positive-linearly independent.Recently Andreani et al. [34] introduced a new CQ called Cone-Continuity Property (CCP) intimately related to the AKKT condition.Definition 6 (see [34]).
A feasible pointx∗ of (2) is said to satisfy the CCP if the set-valued mapping x⇉K(x) such that(8)Kx≔∑i∈Igx∗λi∇gix+∑i=1pμi∇hix:λi∈R+,μi∈Ris outer semicontinuous (Definition 5.4 [35] )at x∗; that is,(9)limsupx→x∗Kx⊂Kx∗It has been shown that CCP is strictly stronger than ACQ and weaker than CRSC in [34].Next, we will extend the above concepts and results from NLP to MPCC. For an arbitrary feasible pointx of (1), we first define the following index sets.(10)I00x=i∣Gix=0,Hix=0,I0+x=i∣Gix=0,Hix>0,I+0x=i∣Gix>0,Hix=0.Similar to Definitions1 and 2, we give definitions of different stationary points for the MPCC.Definition 7 (see [19]).
Letx∗ be a feasible point of Problem (1). Then,
(a)x∗ is said to be W-stationary if there exist multiplier vectors λ∈Rm and α,β∈Rl such that(11)∇fx∗+∇gx∗Tλ+∇hx∗Tμ-∇Gx∗Tα-∇Hx∗Tβ=0,(12)λ≥0,x∗∈ϝ,λTgx∗=0,(13)αi=0,i∈I+0x∗,(14)βi=0,i∈I0+x∗.(b) x∗ is said to be M-stationary, if it is W-stationary and(15)αi>0,βi>0,orαiβi=0,i∈I00x∗.Definition 8 (see [21]).
Letx∗ be a feasible point of Problem (1); x∗ is called a MPCC-AKKT point if there are sequences xk→x∗ such that(16)∇fxk+∑i∈Igx∗λik∇gixk+∑i=1pμik∇hixk-∑i∈I0+x∗∪I00x∗αik∇Gixk-∑i∈I+0x∗∪I00x∗βik∇Hixk→0,where supp(λk)⊂Ig(x∗),supp(αk)⊂I0+(x∗)∪I00(x∗),supp(βk)⊂I+0(x∗)∪I00(x∗), either αikβik=0, or αik>0,  βik>0,i∈I00(x∗).A definition of MFCQ for MPCC is presented similar to Definition3.Definition 9 (see [19]).
A feasible pointx∗ of (1) is said to satisfy MPCC-MFCQ if and only if the vectors(17)∇hix∗,i=1,2,…,p,∇Gix∗,i∈I0+x∗∪I00x∗,∇Hix∗,i∈I+0x∗∪I00x∗,are linearly independent and there exists a vector d∈Rn such that(18)∇gix∗Td<0,i∈Igx∗,∇hix∗Td=0,i=1,2,…,p,∇Gix∗Td=0,i∈I0+x∗∪I00x∗,∇Hix∗Td=0,i∈I+0x∗∪I00x∗.The following result holds which is similar to Lemma5.Lemma 10 (see [19]).
A feasible pointx∗ of Problem (1) satisfies MPCC-MFCQ if and only if the gradients(19)∇gix∗∣i∈Igx∗∪∇hix∗∣i=1,2,…,p∪∇Gix∗∣i∈I00x∗∪I0+x∗∪∇Hix∗∣i∈I00x∗∪I+0x∗are positive-linearly independent.Andreani [21] extended the definition of CCP from nonlinear programming to MPCC.Definition 11 (see [21]).
A feasible pointx∗ of (1) is said to satisfy MPCC-Cone-Continuity Property (MPCC-CCP) if and only if the set-valued mapping x⇉KMPCC(x) such that(20)KMPCCx≔∑i∈Igx∗λik∇gix+∑i=1pμik∇hix-∑i∈I0+x∗∪I00x∗αik∇Gix-∑i∈I+0x∗∪I00x∗βik∇Hix:λik∈R+is outer semicontinuous (Definition 5.4 [35] ) at x∗; that is,(21)limsupx→x∗KMPCCx⊂KMPCCx∗.In [21], it has been shown that MPCC-CCP is strictly weaker than MPCC-RCPLD and MPCC-CCP implies the MPCC-Abadie CQ under certain assumption. Furthermore, MPCC-CCP is also independent of MPCC-quasinormality and MPCC-pseudonormality. The following lemma shows the relationship between MPCC-CCP and MPCC-AKKT.Lemma 12 (see [21]).
MPCC-CCP holds atx∗ if and only if MPCC-AKKT point x∗ is an M-stationary point.In the end of this section, we come to propose a new smoothing method of Problem (1).We first note that(22)a≥0,b≥0,ab=0can be written as(23)a≥0,b≥0,ab≤0.Clearly, (23) is equivalent to(24)a≥0,b≥0,a+b≤a-b.Since(25)a+b≤a-b+a+b2=max⁡a,b,we obtain an equivalent form of (22):(26)a≥0,b≥0,a+b≤max⁡a,b.More generally, we set(27)wx≜maxi=1,2,…,mwix,where wi:R→R is continuously differentiable. Then, w can be approximated by a logarithm-exponential function [36]:(28)wx,ε=εln⁡∑i=1mexp⁡wixεε>0.The following result presents some nice properties of the logarithm-exponential function.Lemma 13 (see [36]).
Letw(x,ε) be defined by (28). Suppose that wi, i=1,2,…,m, are continuously differentiable. Then,
(a)w(x,ε) is increasing with respect to ε, and w(x)≤w(x,ε)≤w(x)+εln⁡m.
(b) For anyx∈Rn and ε>0, it holds that(29)0≤wε′x,ε≤ln⁡m.On the basis of Lemma13, we approximate max⁡{a,b} by the following logarithm-exponential function:(30)εln⁡exp⁡aε+exp⁡bε,ε>0.Then, it is natural that for the following complementarity constraints:(31)Gx≥0,Hx≥0,GxTHx=0,we can approximate G(x)TH(x)=0 in (31) by the following system of inequalities:(32)Φεx≤0,where Φε:Rn→Rn is given by(33)Φεx=ϕε,1x⋮ϕε,lx,ϕε,ix=Gix+Hix-εln⁡exp⁡Gixε+exp⁡Hixε.Consequently, the original MPCC (1) is approximated by the following new smooth optimization problem:(34)minfxs.t.gx≤0,hx=0,Gx≥0,Hx≥0,Φεx≤0.We denote the feasible region of Problem (34) by ϝε. The Lagrange function of Problem (34) is as follows:(35)Lx,μ,λ,α,β,γ=fx+gxTμ+hxTλ+GxTα+HxTβ+ΦεxTγ,where μ∈Rm,λ∈Rp,α∈Rl,β∈Rl,γ∈Rl.Since Problem (34) is a standard smooth optimization problem, many powerful optimization techniques can be directly applied to solve it (see [37–40]).Remark 14.
Unlike the existing smoothing methods, it is noted that (34) is obtained only by partly smoothing the complementarity constraints (31).
As an approximate problem of the MPCC (1) with a perturbation parameter ε, a critical issue should be addressed that concerns what is the relation between the optimal solutions of (34) and (1). Therefore, our next focus in this paper is to prove theoretically that the solution of the perturbed problem (34) tends to an optimal solution of (1) as ε↓0.


## 3. Convergence Analysis and Development of Algorithm

In this section, we will investigate the limiting behavior of stationary points of the perturbed subproblems.We first study the constraint qualification of (34).Lemma 15.
Letϕε,i be defined by (33). Then, (1) for all i=1,2,…,l, ϕε,i is continuously differentiable and is decreasing with respect to ε.
(2) The gradient ofϕε,i is calculated by(36)∇xϕε,ix=ηiΦε∇Gix+ζiΦε∇Hix,where(37)ηiΦε=1-exp⁡Gix/εexp⁡Gix/ε+exp⁡Hix/ε,ζiΦε=1-exp⁡Hix/εexp⁡Gix/ε+exp⁡Hix/ε.
(3)ηiΦε+ζiΦε=1.
(4) Letx∗ be feasible for Problem (1). If i∈I+0(x∗), then ηiΦε→0, ζiΦε→1 as x→x∗ and ε↓0. If i∈I0+(x∗), then, ηiΦε→1, ζiΦε→0 as x→x∗ and ε↓0.Proof.
From the definition ofϕε,i, it is easy to see that the first result holds. By direct calculation, we obtain the second result. The third is directly from the second one. It remains to prove the last result.
Asi∈I+0(x∗), we write ηiΦε and ζiΦε as(38)ηiΦε=1-11+exp⁡Hix-Gix/ε,and(39)ζiΦε=1-exp⁡Hix-Gix/ε1+exp⁡Hix-Gix/ε,respectively. Thus, it is easy to see that ηiΦε→0, ζiΦε→1 as x→x∗ and ε↓0. In a similar way, we can prove that ηiΦε→1, ζiΦε→0 (x→x∗, ε↓0) in the case that i∈I0+(x∗).In virtue of Lemmas10 and 15, we now prove that Problem (34) satisfies some constraint qualification under mild conditions.Theorem 16.
Letx∗ be a feasible point of Problem (1) such that MPCC-MFCQ is satisfied at x∗. Then, there exist a neighborhood U(x∗) of x∗ and a sufficiently small ε¯>0 such that Problem (34) satisfies the standard MFCQ at any point x∈U(x∗)∩ϝε for any ε∈(0,ε¯).Proof.
Sinceg,h,G,H are all continuous, there exist a neighborhood U1(x∗) and a positive constant ε¯1 such that for any ε∈(0,ε¯1) and any point x∈U1(x∗)∩ϝε, we have(40)Igx⊆Igx∗,IGx⊆I00x∗∪I0+x∗,Ihx⊆Ihx∗,IHx⊆I00x∗∪I+0x∗.
For convenience of discussion, we denote(41)IΦεx=i:ϕε,ix=0.We will first prove that the following equalities(42)IΦεx∩IGx=∅,IΦεx∩IHx=∅are true.
Actually, ifi∈IG(x), then Gi(x)=0 and(43)ϕε,ix=Gix+Hix-εln⁡exp⁡Gixε+exp⁡Hixε=Hix-εln⁡1+exp⁡Hixε<Hix-εln⁡exp⁡Hixε=0.Therefore, i∉IΦε(x). It says that IΦε(x)∩IG(x)=∅.
In a similar fashion, we can prove thatIΦε(x)∩IH(x)=∅.
Noting that MPCC-MFCQ is satisfied atx∗ for Problem (1), we conclude from Lemma 10 that the following gradients(44)∇gix∗∣i∈Igx∗∪∇hix∗∣i=1,2,…,p∪∇Gix∗∣i∈I00x∗∪I0+x∗∪∇Hix∗∣i∈I00x∗∪I+0x∗are positive-linearly independent.
Owing to the facts(45)IGx∪IΦεx∩I0+x∗∪IΦεx∩I00x∗⊆I00x∗∪I0+x∗,IHx∪IΦεx∩I+0x∗∪IΦεx∩I00x∗⊆I00x∗∪I+0x∗,it follows from the result (4) in Lemma 15 that ηiΦε→0, ζiΦε→1(i∈I+0(x∗)) and ηiΦε→1, ζiΦε→0(i∈I0+(x∗)) as x→x∗ and ε↓0.
Similar to the proof of Proposition 2.2 in [41], it is concluded that there are a neighborhood U2(x∗) and a ε¯2>0 sufficiently small such that for all x∈U2(x∗)∩ϝε with ε∈(0,ε¯2), the vectors(46)∇gix,i∈Igx∗,∇hix,i=1,2,…,p,∇Gix,i∈IGx,∇Hix,i∈IHx,ηiΦε∇Gix+ζiΦε∇Hix,i∈IΦεx∩I0+x∗,ηiΦε∇Gix+ζiΦε∇Hix,i∈IΦεx∩I+0x∗,∇Gix,i∈IΦεx∩I00x∗,∇Hix,i∈IΦεx∩I00x∗are positive-linearly independent.
We now claim that ifx∈U(x∗)∩ϝε, then the standard MFCQ holds for Problem (34), where U(x∗)=U1(x∗)∩U2(x∗) and ε¯=min⁡{ε¯1,ε¯2}.
Takex∈U(x∗)∩ϝε. In view of Lemma 5, we should show that(47)∑i∈Igxλi∇gix+∑i=1pμi∇hix-∑i∈IGxαi∇Gix-∑i∈IHxβi∇Hix+∑i=1lγiηiΦε∇Gix+ζiΦε∇Hix=0if and only if all the multiplier vectors, μ∈Rp, λ∈R+|Ig(x)|, α∈R+|IG(x)|, β∈R+|IH(x)| and γ∈R+l are null ones. To see this, we rewrite (47) as(48)0=∑i∈Igxλi∇gix+∑i=1pμi∇hix-∑i∈IGxαi∇Gix-∑i∈IHxβi∇Hix+∑i∈IΦεx∩I+0x∗γiηiΦε∇Gix+ζiΦε∇Hix+∑i∈IΦεx∩I0+x∗γiηiΦε∇Gix+ζiΦε∇Hix+∑i∈IΦεx∩I00x∗γiηiΦε∇Gix+∑i∈IΦεx∩I00x∗γiζiΦε∇Hix.From (46) and (48), it follows that(49)λi=0i∈Igx,μi=0i=1,2,…,p,αi=0i∈IGx,βi=0i∈IHx,γi=0i∈IΦεx∩I+0x∗∪I0+x∗,γiηiΦε=γiζiΦε=0,i∈IΦεx∩I00x∗.Taking into account ηiΦε+ζiΦε=1 for all i∈I00(x∗), it yields(50)γi=0,i∈IΦεx∩I00x∗.Since γi=0 (i∈IΦε(x)∩(I+0(x∗)∪I0+(x∗))) and γi=0 (i∈IΦε(x)∩I00(x∗)), we know γi=0  (i∈IΦε(x)). Thus, (47) holds. The proof is completed.The following result establishes the relations between the optimal solutions of the original problem and that of the perturbed subproblem under the constraint qualification of MPCC-CCP.Theorem 17.
Let{εk} be a positive sequence which is convergent to zero as k→∞. Suppose that {xk} is a sequence, generated by the stationary points of the smooth problem (34) with perturbation parameter ε=εk. If x∗ is an accumulation point of the sequence {xk} and MPCC-CCP holds at x∗ and {i:Gi(xk)>0,Hi(xk)>0}∩supp(γk)=⌀, then x∗ is an M-stationary point of the original MPCC (1).Proof.
From Lemma12, it follows that we only need to show that x∗ is an MPCC-AKKT point. From Definition 8, it will be sufficient to show that there is subsequence {xk} which is an MPCC-AKKT point subsequence. Since {xk} is a stationary point sequence generated by the smooth problem (34) with perturbation parameter ε=εk, there exist Lagrangian multiplier vectors λk, μk, and γk such that(51)∇fxk+∑i=1mλik∇gixk+∑i=1pμik∇hixk-∑i∈IGxkαik∇Gixk-∑i∈IHxkβik∇Hixk+∑i=1lγik∇ϕεk,ixk=0,and(52)suppλk⊆Igxk,λk≥0,suppαk⊆IGxk,αk≥0,suppβk⊆IHxk,βk≥0,suppγk⊆IΦεkxk,γk≥0.Clearly, (51) can be rewritten as(53)∇fxk+∑i∈suppλkλik∇gixk+∑i∈suppμkμik∇hixk-∑i∈suppαkαik∇Gixk-∑i∈suppβkβik∇Hixk+∑i∈suppγkγikηiΦεk∇Gixk+∑i∈suppγkγikζiΦεk∇Hixk=0.Since(54)suppαk∩suppγk=∅,suppβk∩suppγk=∅,we can write(55)γ¯ik=αik,i∈suppαk;-γikηiΦεk,i∈suppγk;0,otherwiseand(56)ν¯ik=βik,i∈suppβk;-γikζiΦεk,i∈suppγk;0otherwise.Then, (51) is equivalent to(57)∇fxk+∑i=1mλik∇gixk+∑i=1pμik∇hixk-∑i=1lγ¯ik∇Gixk-∑i=1lν¯ik∇Hixk=0.
First, we will show thatγ¯ik=0,i∈I+0(x∗) for enough large k. Since Gi(xk)≥0,Hi(xk)≥0, we decompose I+0(x∗) into four subsets.(58)I+01x∗≔i∈I+0x∗:Gixk>0,Hixk>0I+02x∗≔i∈I+0x∗:Gixk>0,Hixk=0I+03x∗≔i∈I+0x∗:Gixk=0,Hixk>0I+04x∗≔i∈I+0x∗:Gixk=0,Hixk=0
SinceGi(x∗)>0, we can get that I+03(x∗)=⌀ and I+04(x∗)=⌀. If i∈I+01(x∗), we can follow that i∉IG(xk). Because supp(αk)⊂IG(xk), we can conclude that i∉supp(αk). Furthermore, for the condition of Theorem 17 that {i:Gi(xk)>0,Hi(xk)>0}∩supp(γk)=⌀, we can get that γ¯ik=0,i∈I+01(x∗).
Ifi∈I+02(x∗), then i∈IH(xk) and i∉IG(xk). Since IH(xk)∩Iϕ(xk)=⌀, we can conclude that i∈Iϕ(xk) and i∉supp(γk). Since supp(αk)⊂IG(xk), then it is sure that i∉supp(αk). Thus, γ¯ik=0,i∈I+02(x∗). Therefore, we can conclude that γ¯ik=0,i∈I+0(x∗).
Following the similar arguments, we can conclude thatν¯ik=0,i∈I0+(x∗). Lastly, we will prove that either ν¯ikγ¯ik=0, or ν¯ik>0,γ¯ik>0 for i∈I00(x∗). Similarly we decompose I00(x∗) into four subsets.(59)I001x∗≔i∈I00x∗:Gixk>0,Hixk>0I002x∗≔i∈I00x∗:Gixk>0,Hixk=0I003x∗≔i∈I00x∗:Gixk=0,Hixk>0I004x∗≔i∈I00x∗:Gixk=0,Hixk=0
Ifi∈I001(x∗), we can follow that i∉IG(xk) and i∉IH(xk). Because supp(αk)⊂IG(xk) and supp(βk)⊂IH(xk), we can conclude that i∉supp(αk) and i∉supp(βk). Furthermore, the condition of Theorem 17 that {i:Gi(xk)>0,Hi(xk)>0}∩supp(γk)=⌀, we can get that γ¯ik=0,ν¯ik=0,i∈I001(x∗). Therefore, γ¯ikν¯ik=0,i∈I001(x∗).
Ifi∈I002(x∗), we can follow that i∈IH(xk) and i∉IG(xk). Since IH(xk)∩Iϕ(xk)=⌀ and supp(γk)⊂Iϕ(xk), we can conclude that i∉Iϕ(xk) and i∉supp(γk). Because supp(αk)⊂IG(xk), it is sure that i∉supp(αk). Thus, γ¯ik=0,ν¯ik=βik or 0, i∈I002(x∗). Therefore, γ¯ikν¯ik=0,i∈I002(x∗).
Ifi∈I003(x∗), we can follow that i∈IG(xk) and i∉IH(xk). Since IG(xk)∩Iϕ(xk)=⌀ and supp(γk)⊂Iϕ(xk), we can conclude that i∉Iϕ(xk) and i∉supp(γk). Because supp(βk)⊂IH(xk), it is sure that i∉supp(βk). Thus, γ¯ik=αik or 0, ν¯ik=0,i∈I003(x∗). Therefore, γ¯ikν¯ik=0,i∈I003(x∗).
Ifi∈I004(x∗), we can follow that i∈IG(xk) and i∈IH(xk). Since IG(xk)∩Iϕ(xk)=⌀ and supp(γk)⊂Iϕ(xk), we can conclude that i∉Iϕ(xk) and i∉supp(γk). Because supp(βk)⊂IH(xk) and supp(αk)⊂IG(xk), thus,γ¯ik=αik or 0, ν¯ik=βik or 0, i∈I004(x∗). Therefore, either γ¯ikν¯ik=0, or γ¯ik>0,ν¯ik>0,i∈I004(x∗).
Thus, we conclude thatx∗ is an MPCC-AKKT point. Following the condition of Theorem 17 that MPCC-CCP holds at x∗, we can get that x∗ is an M-stationary point.On the basis of Theorems16 and 17, we now develop an implementable algorithm to solve the original MPCC (1) before the end of this section.Algorithm 18.
Step  1. Given an initial point x1. Choose ε1>0, ϵstop, β∈(0,1). Set k:=1.
Step  2. Let εk be the current parameter. Solve the following problem:(60)minfxs.t.gx≤0,hx=0,Gx≥0,Hx≥0,Φεkx≤0,where(61)Φεkx=ϕεkG1x,H1x⋮ϕεkGlx,Hlx.The optimal solution is referred to as x∗.
Step  3. If maxvio⁡(x∗)<ϵstop, then the algorithm stops. Otherwise, set εk+1:=βεk, xk+1:=x∗, k:=k+1. Return to Step 2.Remark 19.
In Step 3 of Algorithm18, maxvio⁡(x∗) denotes the maximal violation of all the constraints and is defined by(62)maxvio⁡x∗=max⁡max⁡gx∗,0,hx∗,min⁡Gx∗,Hx∗.It is clear that maxvio⁡(x∗) can be used to measure the infeasibility degree at the obtained iterate point x∗. If maxvio⁡(x∗)=0, then x∗ is a feasible point of MPCC (1), as well as a stationary point of the perturbed problem. From Theorems 17, it follows that x∗ is an approximate optimal solution of MPCC (1).


## 4. Numerical Results

In this section, we investigate the numerical behavior of Algorithm18. We compare Algorithm 18 with a similar algorithm developed by Facchinei et al. in [23] as they are used to solve the same test problems. All the test problems are from [23, 42]. The solution tolerance ϵstop is set to be 10-3 for the problems 8(f)-8(j). For the other test problems, the solution tolerance ϵstop takes 10-6.As done in [23], the initial perturbation parameter is set to be 1, and β=0.1 for reduction of the perturbation parameter. The corresponding computer procedures in MATLAB run in the following computer environment: 2.20GHz CPU, 1.75GB memory based operation system of Windows 7.Numerical efficiency of the two algorithms is reported in Tables1 and 2. For each algorithm, the optimal value of the objective function, the optimal solution, the number of iterations, and the achieved termination condition are recorded for evaluating the numerical performance. The used notations in Tables 1 and 2 are listed as follows.Table 1
Comparison between different algorithms.
Prob f F / f N x F ∗ / x N ∗ k F / k N m a x v i o F / m a x v i o N 1(a) 3.2077/3.2077 4.0604/4.0604 5/2 7.1071e-06/3.4786e-08 1(b) 3.2077/3.2077 4.0604/4.0604 5/2 7.1063e-06 /3.4786e-08 2(a) 3.4494/3.4494 5.1536/5.1536 5/2 2.0042e-08/8.3186e-08 2(b) 3.4494/3.4494 5.1536/5.1536 5/2 2.0042e-08/8.3741e-08 3(a) 4.6043/4.6043 2.3894/2.3894 5/2 3.5255e-08/5.6882e-07 3(b) 4.6043/4.6043 2.3894/2.3894 5/2 3.5255e-08/5.6882e-07 4(a) 6.5927/6.5927 1.3731/1.3731 5/3 5.2677e-08/1.1699e-14 4(b) 6.5927/6.5927 1.3731/1.3731 5/3 5.2677e-08/1.9621e-17 5 -1.0000/-1.0000 (0.50,0.50)/(0.50,0.50) 6/1 6.0954e-07/5.2779e-16 6 -3.2667e+03/-3.2667e+03 93.3333/93.3333 4/1 3.7500e-08/2.2901e-16 7 4.0753e-06/7.1054e-15 (0,30.0000)/(0,30.0000) 7/2 7.5895e-07/4.1748e-15 8(a) -343.3453/-343.3453 55.5513/55.5513 4/1 4.6387e-08/3.7728e-09 8(b) -203.1551/-203.1551 42.5382/42.5382 4/1 5.1908e-08/2.6567e-13 8(c) -68.1356/-68.1356 24.1451/24.1451 4/1 6.6333e-08/6.9827e-15 8(d) -19.1541 /-19.1541 12.3727/12.3727 4/1 8.6584e-08/4.8701e-12 8(e) -3.1612/-3.1612 4.7536/4.7536 4/1 1.3410e-07/1.1826e-11 8(f) -346.8932/-346.8932 50.0000/50.0000 5/2 4.4957e-08/6.7134e-04 8(g) -224.0372/-224.0622 39.7914/39.7003 5/2 3.6489e-08/4.2135e-04 8(h) -80.7860/-80.7861 24.2571/24.2562 5/2 1.8589e-08/2.0398e-05 8(i) -22.8371/-22.8690 13.0197/12.9023 5/2 5.4911e-08/1.2813e-04 8(j) -5.3491/ -5.3492 6.0023/6.0015 5/2 1.7337e-08/6.2099e-05 9(a) 1.4267e-12/4.7851e-06 (10.0,5.0)/(7.0226,7.9755) 5/1 1.6052e-08/1.6627e-13 9(b) 5.3783e-15/1.1248e-14 (10.0,5.0)/(5.0,9.0) 5/2 7.7636e-07/2.5611e-07 9(c) 1.2633e-14/1.8666e-10 (10.0,5.0)/(5.0,9.0) 5/3 1.6052e-08/8.6309e-17 9(d) 1.6456e-14/9.4146e-12 (10.0,5.0)/(5.0,9.0) 5/3 1.6051e-08/3.7030e-15 9(e) 1.4267e-12/9.4146e-12 (10.0,5.0)/(5.0,9.0) 5/3 1.6052e-08/3.5898e-15 10 -6.6000e+03/-6.6000e+03 (7.3019,3.4529,11.6981,17.5471) /(7.9142,4.3714,11.0858,16.6286) 4/1 2.5000e-08/2.7393e-15 11 -12.6787/-12.6787 (0.0,2.0)/(0.0,2.0) 5/3 1.4835e-08/1.08886e-15Table 2
Comparison between different algorithms (continued).
Prob fF/fN xF∗/xN∗ kF/kN maxvioF/maxvioN bard1 16.8919 /16.8919 0.9459/0.9459 4/2 4.5868e-07/1.2435e-14 bard3 -12.6787/-12.6787 0.0000/0.0000 4/2 8.3540e-07/3.7267e-07 dempe 28.2500/28.4859 0.0000/0.0009 2/1 5.1436e-11/6.6730e-15 df1 5.3751e-13/0.0000 1.0000/1.0000 7/1 7.1965e-07/0.0000 ex9.1.2 -16.0000/-16.0000 4.0000/4.0000 4/3 4.1667e-07/7.6800e-17 jr1 0.5000/0.5000 0.5000 /0.5000 5/1 2.0000e-08/0.0000 jr2 0.5000/0.5000 0.5000/0.5000 2/3 2.0000e-12/0.0000 kth1 1.8097e-06 /0.0000 8.9720e-07/8.9722e-07 7/1 0.0000/0.0000 kth2 1.0000e-06/0.0000 0.0000/0.0000 4/1 0.0000/0.0000 kth3 0.5000/0.5000 0.0000/0.0000 5/3 1.0000e-08/3.1427e-17 ralph2 -2.0003e-12/7.0641e-14 1.0070e-06/7.9080e-07 7/7 9.9300e-07/1.8633e-07 scholtes1 2.0000/ 2.0000 0.0000/0.0000 5/1 2.0000e-08/1.5489e-16 scholtes2 15.0000/15.0000 0.0000/0.0000 7/1 8.3043e-07/2.4980e-18 scholtes3 0.5000/ 0.5000 1.0000/1.0000 5/3 1.0000e-08/7.8774e-18 scholtes4 -2.0000e-06/-1.3863e-06 1.0000e-06/6.9830e-07 7/7 9.9999e-07/6.9315e-07 scholtes5 1.5000 /1.0000 1.5000/1.0000 5/1 1.3333e-08/0.0000Prob: the test problems;f F / f N: the optimal function value obtained by the algorithm in [23]/the optimal function value by Algorithm 18;x F ∗ / x N ∗: the optimal solution obtained by the algorithm in [23]/the optimal solution obtained by Algorithm 18;k F / k N: the number of iterations as the algorithm in [23] stops/the number of iterations as Algorithm 18 stops;m a x v i o F / m a x v i o N: the maximal degree of constraint violation as the algorithm in [23] stops at the optimal solutions x∗/the maximal degree of constraint violation as Algorithm 18 stops at the optimal solutions x∗.As done in [23], only the x-part of the optimal solution x∗ is shown in Table 1. In Table 2, for the optimal solutions x∗ found by the algorithm in [23] and Algorithm 18, only the first component of x∗ is shown in xF∗/xN∗.From Tables1 and 2, it is clear that (1) Algorithm 18 can obtain the same optimal function value for the other test problems as the algorithms in [23] except for the problem: Scholtes 5. For this test problem, our algorithm gets smaller (better) value of the objective function than the algorithm in [23]. (2) By the two algorithms, almost the same optimal solutions have been obtained for all the test problems. (3) As an impressive performance, Algorithm 18 costs smaller number of iterations with higher accuracy in finding out the optimal solution. Actually, for the 41 ones out of all the 44 test problems, the number of iterations is smaller than that of the algorithm in [23]. (4) With regard to the termination conditions, for the 33 ones out of the 44 test problems, Algorithm 18 has less degree of constraint violation at the optimal solution than that of the algorithm in [23].The numerical results in Tables1 and 2 demonstrate that Algorithm 18 outperforms the algorithms in [23], and the proposed partly smoothing method in this paper is promising in solving MPCC.


## 5. Final Remarks

Different from the existing smoothing methods available in the literature, we have proposed a partly smoothing method based on the logarithm-exponential function for the mathematical programs with complementarity constraints. It has been proved that Mangasarian-Fromovitz constraint qualification holds for the constructed approximate smooth problem in our method. Under the weaker constraint qualification MPCC-CCP, it has been proved that any accumulation point of the approximate solution sequence is an M-stationary point of the original MPCC. Preliminary numerical results have demonstrated that the proposed smoothing method is more efficient than the other similar ones.



---

*Source: 5056148-2018-08-12.xml*