# Notes on Convergence Properties for a Smoothing-Regularization Approach to Mathematical Programs with Vanishing Constraints

Authors: Qingjie Hu; Yu Chen; Zhibin Zhu; Bishan Zhang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We give some improved convergence results about the smoothing-regularization approach to mathematical programs with vanishing constraints (MPVC for short), which is proposed in Achtziger et al. (2013). We show that the Mangasarian-Fromovitz constraints qualification for the smoothing-regularization problem still holds under the VC-MFCQ (see Definition 5) which is weaker than the VC-LICQ (see Definition 7) and the condition of asymptotic nondegeneracy. We also analyze the convergence behavior of the smoothing-regularization method and prove that any accumulation point of a sequence of stationary points for the smoothing-regularization problem is still strongly-stationary under the VC-MFCQ and the condition of asymptotic nondegeneracy.


---

## Body

## 1. Introduction

We consider the following mathematical program with vanishing constraints:(1)min⁡f(z)s.t.gi(z)≤0,i=1,2,…,m;hj(z)=0,j=1,2,…,p;Hi(z)≥0,i=1,2,…,l;Gi(z)Hi(z)≤0,i=1,2,…,l,
where f:Rn→R,g:Rn→Rm,h:Rn→Rp and G,H:Rn→Rl are all continuously differentiable functions.The MPVC was firstly introduced to the mathematical community in [1]. It plays an important role in some fields such as optimization topology design problems in mechanical structures [1] and robot path-finding problems with logic communication constraints in robot motion planning [2]. The major difficulty in solving problem (1) is that it does not satisfy some standard constraint qualifications at the feasible points so that the standard optimization methods are likely to fail for this problem. The MPVC has attracted much attention in the recent years. Several theoretical properties and different numerical approaches for MPVC can be found in [1–12]. Very recently, in [3], the authors have proposed a smoothing-regularization approach to mathematical programs with vanishing constraints. Their basic idea is to reformulate the characteristic constraints of the MPVC via a nonsmooth function and to eventually smooth it and regularize the feasible set with the aid of a certain smoothing and regularization parameter ɛ>0 such that the resulting problem is more tractable and coincides with the original program for ɛ=0. Under the VC-LICQ and the condition of asymptotic nondegeneracy, the convergence behaviors of a sequence of stationary points of the smoothing-regularized problems have been investigated.In this note, we give some improved convergence results about the smoothing-regularization approach to mathematical programs with vanishing constraints in [3]. We show that these properties still hold under the weaker VC-MFCQ and the condition of asymptotic nondegeneracy. The smoothing-regularization problems satisfy the standard MFCQ, which guarantees the existence of Lagrange multipliers at local minima; the sequence of multipliers is bounded, and the limit point is still strongly-stationary.The rest of the note is organized as follows. In Section2, we review some concepts of the nonlinear programming and the MPVC and present the smoothing-regularization method for (1), which is proposed in [3]. In Section 3, we give the improved convergent properties. We close with some final remarks in Section 4.For convenience of discussion, some notations to be used in this paper are given. Theith component of G will be denoted by Gi; X denotes the feasible set of problem (1). For a function g:Rn→Rm and a given vector α∈Rn, we use Ig(z)={i:gi(z)=0} and supp⁡(α)={i:αi≠0} to denote the active index set of g at z and the support of α, respectively.


## 2. Preliminaries

Firstly, we will introduce some definitions about the following optimization problem:(2)min⁡f(z)s.t.g(z)≤0,h(z)=0,
where f:Rn→R,g:Rn→Rm,h:Rn→Rp are all continuously differentiable functions. F denotes the feasible set of problem (2).Definition 1.
A pointz¯∈F is called a stationary point if there are multipliers λ,μ such that (z¯,λ,μ) is a KKT point of (2); that is, the multipliers satisfy λ∈R+m and μ∈Rp with λigi(z¯)=0 for all i=1,2,…,m, and
(3)∇f(z¯)+∑i=1m‍λi∇gi(z¯)+∑i=1p‍μi∇hi(z¯)=0.Definition 2.
A feasible pointz¯ of (2) is said to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ for short) if the gradients {∇hi(z¯)∣i=1,2,…,p} are linearly independent and there is a d∈Rn such that
(4)∇gi(z¯)Td<0(i∈Ig(z¯)),∇hi(z¯)Td=0(i=1,2,…,p).Definition 3 (see [13]).
A finite set of vectors{ai∣i∈I1}∪{bi∣i∈I2} is said to be positive-linearly dependent if there exists (α,β)≠0 such that
(5)∑i∈I1‍αiai+∑i∈I2‍βibi=0,αi≥0,∀i∈I1.
If the above system only has a solution(α,β)=0, we say that these vectors are positive-linearly independent.By using Motzkin’s theorem of the alternatives in [14], we can obtain the following property.Lemma 4.
A pointz¯∈F satisfies the MFCQ if and only if the gradients
(6){∇gi(z¯)∣i∈Ig(z¯)}∪{∇hi(z¯)∣i=1,2,…,p}
are positive-linearly independent.Now, we borrow notations from mathematical programs with complementarity constraints to define the following sets of active constraints in an arbitraryz¯∈X as follows:
(7)I+(z¯)={i∣Hi(z¯)>0},I0(z¯)={i∣Hi(z¯)=0},I+0(z¯)={i∣Hi(z¯)>0,Gi(z¯)=0},I+-(z¯)={i∣Hi(z¯)>0,Gi(z¯)<0},I0+(z¯)={i∣Hi(z¯)=0,Gi(z¯)>0},I00(z¯)={i∣Hi(z¯)=0,Gi(z¯)=0},I0-(z¯)={i∣Hi(z¯)=0,Gi(z¯)<0}.Definition 5 (see [1]).
A feasible pointz¯ for (1) satisfies the vanishing constraints Mangasarian-Fromovitz constraints qualification (VC-MFCQ for short) if
(8)∇hi(z¯)(i=1,2,…,p),∇Hi(z¯)(i∈I0+(z¯)∪I00(z¯))
are linearly independent and there exists a vector d∈Rn such that
(9)∇hi(z¯)Td=0(i=1,2,…,p),∇Hi(z¯)Td=0(i∈I0+(z¯)∪I00(z¯)),∇gi(z¯)Td<0(i∈Ig(z¯)),∇Hi(z¯)Td>0(i∈I0-(z¯)),∇Gi(z¯)Td<0(i∈I+0(z¯)).Similar to Lemma4, we can also deduce the following result.Lemma 6.
A pointz¯∈X satisfies the VC-MFCQ if and only if the gradients
(10){∇gi(z¯)∣i∈Ig(z¯)}∪{∇hi(z¯)∣i=1,2,…,p}∪{-∇Hi(z¯)∣i∈I0-(z¯)}∪{∇Gi(z¯)∣i∈I+0(z¯)}∪{∇Hi(z¯)∣i∈I00(z¯)∪I0+(z¯)}
are positive-linearly independent. In other words, the MPVC at z¯ satisfies the VC-MFCQ if and only if there does not exist a vector (λIg(z¯),μ,αI0-(z¯),αI00(z¯)∪I0+(z¯),βI+0(z¯))≠0 with λi≥0 for all i∈Ig(z¯), αi≥0 for all i∈I0-(z¯), and βi≥0 for all i∈I+0(z¯) such that
(11)∑i∈Ig(z¯)‍λi∇gi(z¯)+∑i=1l‍μi∇hi(z¯)-∑i∈I0-(z¯)‍αi∇Hi(z¯)+∑i∈I00(z¯)∪I0+(z¯)‍αi∇Hi(z¯)+∑i∈I+0(z¯)‍βi∇Gi(z¯)=0
holds true.Definition 7 (see [1]).
A feasible pointz¯ for (1) satisfies the vanishing linear independence constraints qualification (VC-LICQ for short) if and only if
(12)∇hi(z¯)(i=1,2,…,p),∇gi(z¯)(i∈Ig(z¯)),∇Gi(z¯)(i∈I+0(z¯)),∇Hi(z¯)(i∈I0(z¯))
are linearly independent.Remark 8.
It is easy to see that the VC-LICQ implies the VC-MFCQ. Moreover, the VC-LICQ (VC-MFCQ) is weaker than the MPVC-LICQ (MPVC-MFCQ) (See [7]).Definition 9.
Letz¯ be a feasible point for the problem (1), then(a)
z¯ is said to be weak-stationary if there exist multiplier vectors λ¯∈Rm,μ¯∈Rp, and u¯,v¯∈Rl such that
(13)∇f(z¯)+∇g(z¯)Tλ¯+∇h(z¯)Tμ¯-∇H(z¯)Tv¯+∇G(z¯)Tu¯=0,λ¯≥0,z¯∈X,λ¯Tg(z¯)=0,v¯i=0(i∈I+(z¯)),v¯i≥0(i∈I0-(z¯)),v¯ifree(i∈I0+(z¯)∪I00(z¯)),u¯i=0(i∈I+-(z¯)∪I0-(z¯)∪I0+(z¯)),u¯i≥0(i∈I+0(z¯)∪I00(z¯)).(b)
z¯ is said to be strongly-stationary, if it is weak-stationary and
(14)u¯i=0,v¯i≥0,i∈I00(z¯).Finally, we give the smoothing-regularization method of Problem (1), which is proposed in [3]. According to [3], with the help of a positive parameter, the MPVC (1) is approximated by the following smoothing-regularization problem:
(15)min⁡f(z)s.t.g(z)≤0,h(z)=0,rɛ(z)≤ɛ,
where
(16)rɛ(z)=(rɛ,1(z)⋮rɛ,l(z)),rɛ,i(z)=12((Hi(z))2+ɛ2Gi(z)Hi(z)+(Gi(z)Hi(z))2+ɛ2+(Hi(z))2+ɛ2-Hi(z)).
In order to give our improved convergence analysis, the following concept of asymptotic nondegeneracy is necessary.Definition 10 (see [3]).
Letz¯ be feasible for the MPVC (1). Then a sequence {zk} of feasible points for (15) converging to z¯ as εk↓0 is called asymptotically nondegenerate, if any accumulation point of {∇rεk,i(zk)} is different from 0 for each i∈I+0(z¯)∪I0(z¯).


## 3. Some Improved Convergence Properties

In this section, we will consider the improved convergence properties of a sequence of stationary points for the smoothing-regularization problem (15). Firstly, we discuss the constraint qualification of (15).For convenience of discussion, we give the following notations:(17)aɛ,i(z)=Hi(z)+Gi(z)Hi(z)2Gi(z)2Hi(z)2+ɛ2,bɛ,i(z)=Gi(z)+Gi(z)2Hi(z)Gi(z)2Hi(z)2+ɛ2+Hi(z)Hi(z)2+ɛ2-1,Irɛ(z)={i:rɛ,i(z)=ɛ}.
To show that the Mangasarian-Fromovitz constraints qualification for the problem (15) holds under some conditions, the following lemma palys a very important role.Lemma 11.
Letz¯ be feasible for (1) such that the VC-MFCQ is satisfied at z¯ and the sequence {zk} of feasible points for (15) converging to z¯ as εk↓0 is asymptotically nondegenerate. Then, for sufficiently large k, the set of vectors
(18)∇gi(zk),i∈Ig(z¯),∇hi(zk),i=1,2,…,p,-(aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk)),i∈Irεk(zk)∩I0-(z¯),aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk),i∈Irεk(zk)∩I+0(z¯),aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk),i∈Irεk(zk)∩(I0+(z¯)∪I00(z¯))
are positive-linearly independent.Proof.
Sinceg,h,G,H are all continuous, for sufficiently large k, we have
(19)Ig(zk)⊆Ig(z¯),Ih(zk)⊆Ih(z¯).
Because the VC-MFCQ holds, the gradients
(20){∇gi(z¯)∣i∈Ig(z¯)}∪{∇hi(z¯)∣i=1,2,…,p}∪{-∇Hi(z¯)∣i∈I0-(z¯)}∪{∇Gi(z¯)∣i∈I+0(z¯)}∪{∇Hi(z¯)∣i∈I00(z¯)∪I0+(z¯)}
are positive-linearly independent by Lemma 6, taking into account that
(21)(Irεk(zk)∩I0-(z¯))⊆I0-(z¯),(Irεk(zk)∩I+0(z¯))⊆I+0(z¯),(Irεk(zk)∩I0+(z¯))∪(Irεk(zk)∩I00(z¯))⊆I00(z¯)∪I0+(z¯).
In view of the condition of asymptotic nondegeneracy, we know that aεk,i(zk)≠0,bεk,i(zk)≈0 for all i∈I+0(z¯) and aεk,i(zk)≈0,bεk,i(zk)≠0 for i∈I0 for all sufficiently large k. Similar to the proof of Proposition  2.2 in [15], we know that the set of vectors
(22)∇gi(zk),i∈Ig(z¯),∇hi(zk),i=1,2,…,p,-(aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk)),i∈Irεk(zk)∩I0-(z¯),aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk),i∈Irεk(zk)∩I+0(z¯),aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk),i∈Irεk(zk)∩(I0+(z¯)∪I00(z¯))
are positive-linearly independent for all sufficiently large k. The proof is completed.Based on the above lemma, we can show the following theorem.Theorem 12.
Letz¯ be feasible for (1) such that the VC-MFCQ is satisfied at z¯ and the sequence {zk} of feasible points for (15) converging to z¯ as εk↓0 is asymptotically nondegenerate. Then, for sufficiently large k, Problem (15) satisfies the standard MFCQ at zk.Proof.
Taking Lemma11 into account, we know that the set of vectors
(23)∇gi(zk),i∈Ig(z¯),∇hi(zk),i=1,2,…,p,-(aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk)),i∈Irεk(zk)∩I0-(z¯),aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk),i∈Irεk(zk)∩I+0(z¯),aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk),i∈Irεk(zk)∩(I0+(z¯)∪I00(z¯))
are positive-linearly independent for sufficiently large k.
We now prove that the standard MFCQ holds atzk for Problem (15) for sufficiently large k. In view of Lemma 4, we have to show that
(24)0=∑i∈Ig(zk)‍λik∇gi(zk)+∑i=1p‍μik∇hi(zk)+∑i=1l‍γik(aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk))
with μk∈Rp and λk,γk≥0 holds for the zero vector. To see this, we rewrite (24) as
(25)0=∑i∈Ig(zk)‍λik∇gi(zk)+∑i=1p‍μik∇hi(zk)-∑i∈Irεk(zk)∩I0-(z¯)‍γik(-aεk,i(zk)∇Gi(zk)-bεk,i(zk)∇Hi(zk))+∑i∈Irεk(zk)∩I+0(z¯)‍γik(aεk,i(zk)∇Gi(zk)+bεk,i(zk)∇Hi(zk))+∑i∈Irεk(zk)∩(I0+(z¯)∪I00(z¯))‍γik(aεk,i(zk)∇Gi(zk)hhhh+bεk,i(zk)∇Hi(zk)).
In view of the condition of asymptotic nondegeneracy, applying the positive linear independence of vectors from (23) to (25) and (19), one gets
(26)λik=0(i∈Ig(zk)),μik=0(i=1,2,…,p),γik=0(i∈Irεk(zk)∩I0-(z¯)),γik=0(i∈Irεk(zk)∩I+0(z¯)),γik=0(i∈Irεk(zk)∩(I0+(z¯)∪I00(z¯))).
The proof is completed.Remark 13.
In Theorem12, by relaxing the condition of the VC-LICQ, we show that the VC-MFCQ and the condition of asymptotic nondegeneracy imply that the smoothing-regularization problems satisfy the standard MFCQ. Hence, Theorem 12 is an improved version of Lemma  5.6 in [3].To establish the relations between the solutions of the original problem and those of the smoothing-regularization problem under the VC-MFCQ and the condition of asymptotic nondegeneracy, we give the following key lemma.Lemma 14.
Letεk>0 be convergent to zero. Suppose that {zk} is a sequence of stationary points of Problem (15) with ɛ=εk and (λk,μk,γk) being the corresponding multiplier vectors. If z¯ is an accumulation point of the sequence {zk} such that the VC-MFCQ holds at z¯ and the condition of asymptotic nondegeneracy for {zk} is satisfied, then the sequence of multipliers {(λk,μk,γk)} is bounded.Proof.
It follows from Theorem12 that, for sufficiently large k, there exist lagrangian multiplier vectors (λk, μk, γk) such that
(27)∇f(zk)+∑i=1m‍λik∇gi(zk)+∑i=1p‍μik∇hi(zk)+∑i=1l‍γik∇rεk,i(zk)=0,(28)λk≥0,supp⁡(λk)⊆Ig(zk),γk≥0,supp⁡(γk)⊆Irεk(zk).
From (27), we have
(29)∇f(zk)+∑i∈supp⁡(λk)‍λik∇gi(zk)+∑i∈supp⁡(μk)‍μik∇hi(zk)+∑i∈supp⁡(γk)∩I0-(z¯)‍γikaεk,i(zk)∇Gi(zk)+∑i∈supp⁡(γk)∩I0-(z¯)‍γikbεk,i(zk)∇Hi(zk)+∑i∈supp⁡(γk)∩I+0(z¯)‍γikaεk,i(zk)∇Gi(zk)+∑i∈supp⁡(γk)∩I+0(z¯)‍γikbεk,i(zk)∇Hi(zk)+∑i∈supp⁡(γk)∩(I0+(z¯)∪I00(z¯))‍γikaεk,i(zk)∇Gi(zk)+∑i∈supp⁡(γk)∩(I0+(z¯)∪I00(z¯))‍γikbεk,i(zk)∇Hi(zk)=0.
We can define
(30)βik={-γikbεk,i(zk),i∈supp⁡(γk)∩I0-(z¯);0,otherwise,γ¯ik={γikaεk,i(zk),i∈supp⁡(γk)∩I+0(z¯);0,otherwise,ν¯ik={γikbεk,i(zk),i∈supp⁡(γk)∩(I0+(z¯)∪I00(z¯));0,otherwise.
Noting that with βik, γ¯ik, and ν¯ik, (27) can be rewritten as
(31)0=∇f(zk)+∑i=1m‍λik∇gi(zk)+∑i=1p‍μik∇hi(zk)+∑i=1l‍βik(-∇Hi(zk))+∑i=1l‍γ¯ik∇Gi(zk)+∑i=1l‍ν¯ik∇Hi(zk)+∑i∈supp⁡(γk)∩(I0+(z¯)∪I00(z¯))‍γikaεk,i(zk)∇Gi(zk)+∑i∈supp⁡(γk)∩I+0(z¯)‍γikbεk,i(zk)∇Hi(zk)+∑i∈supp⁡(γk)∩I0-(z¯)‍γikaεk,i(zk)∇Gi(zk).
The following objective is to prove that the sequence {(λk,μk,βk,γ¯k,ν¯k,γI+0(z¯)∪I0+(z¯)∪I00(z¯)∪I0-(z¯)k)} is bounded.
Assume that the sequence{(λk,μk,βk,γ¯k,ν¯k,γI+0(z¯)∪I0+(z¯)∪I00(z¯)∪I0-(z¯)k)} is unbounded. Then, there exists a subset K such that
(32)∥(λk,μk,βk,γ¯k,ν¯k,γI+0(z¯)∪I0+(z¯)∪I00(z¯)∪I0-(z¯)k)K∥⟶+∞(k⟶+∞).
So the corresponding normed sequence converges:
(33)(λk,μk,βk,γ¯k,ν¯k,γI+0(z¯)∪I0+(z¯)∪I00(z¯)∪I0-(z¯)k)∥(λk,μk,βk,γ¯k,ν¯k,γI+0(z¯)∪I0+(z¯)∪I00(z¯)∪I0-(z¯)k)∥→k∈K(λ,μ,β,γ¯,ν¯,γI+0(z¯)∪I0+(z¯)∪I00(z¯)∪I0-(z¯))≠0.
Combined with (31), it yields
(34)0=∑i=1m‍λi∇gi(z¯)+∑i=1p‍μi∇hi(z¯)+∑i=1l‍βi(-∇Hi(z¯))+∑i=1l‍γ¯i∇Gi(z¯)+∑i=1l‍ν¯i∇Hi(z¯),
that is,
(35)0=∑i∈supp⁡(λ)‍λi∇gi(z¯)+∑i∈supp⁡(μ)‍μi∇hi(z¯)+∑i∈supp⁡(β)‍βi(-∇Hi(z¯))+∑i∈supp⁡(γ¯)‍γ¯i∇Gi(z¯)+∑i∈supp⁡(ν¯)‍ν¯i∇Hi(z¯),
where λ≥0 and, for all k∈K   being large enough,
(36)supp⁡(λ)⊆Ig(zk)⊆Ig(z¯),supp⁡(β)⊆supp⁡(βk)⊆(supp⁡(γk)∩I0-(z¯))⊆I0-(z¯),supp⁡(γ¯)⊆supp⁡(γ¯k)⊆(supp⁡(γk)∩I+0(z¯))⊆I+0(z¯),supp⁡(ν¯)⊆supp⁡(ν¯k)⊆(supp⁡(γk)∩(I00(z¯)∪I0+(z¯)))⊆I00(z¯)∪I0+(z¯).
We can prove that (λ,μ,β,γ¯,ν¯)≠0. Actually, if (λ,μ,β,γ¯,ν¯)=0, then, for at least one i∈I+0(z¯)∪I0+(z¯)∪I00(z¯)∪I0-(z¯), γi≠0. Without loss of generality, assume that γi≠0 for an i∈I+0(z¯), then, for all k sufficiently large, γik≠0. Consequently, γ¯ik=γikaεk,i(zk) for those k. Taking into account the condition of asymptotic nondegeneracy, for i∈I+0(z¯), we have
(37)γ¯i=lim⁡k∈Kγ¯ik=lim⁡k∈Kγikaεk,i(zk)≠0,
which contradicts the assumption γ¯=0.
By Lemma6, we know that (λ,μ,β,γ¯,ν¯)≠0 contradicts the fact that the VC-MFCQ holds at z¯. Thus, the sequence {(λk,μk,βk,γ¯k,ν¯k,γI+0(z¯)∪I0+(z¯)∪I00(z¯)∪I0-(z¯)k)} is bounded.
Again, noting the condition of asymptotic nondegeneracy and the definitions ofβik,γ¯ik,ν¯ik, we can prove that the sequence of multipliers {(λk,μk,γk)} are bounded. The proof is completed.Based on Lemma14, similar to the proof of Theorem  5.3 in [3], we can obtain the following convergence result.Theorem 15.
Letεk>0 be convergent to zero. Suppose that {zk} is a sequence of stationary points of Problem (15) with ɛ=εk. If z¯ is an accumulation point of the sequence {zk} such that the VC-MFCQ holds at z¯ and the condition of asymptotic nondegeneracy for {zk} is satisfied, then z¯ is a strongly-stationary point of Problem (1).Remark 16.
In Theorem15, by replacing the condition of the VC-LICQ, we prove that any accumulation point of stationary points for the smoothing-regularization problem is still strongly-stationary under the VC-MFCQ and the condition of asymptotic nondegeneracy. Hence, Theorem 15 includes Theorem  5.3 in [3] as a special case.


## 4. Concluding Remarks

In this note, we have shown that the VC-LICQ assumption can be replaced by the weaker VC-MFCQ condition in order to get the strong stationarity for the smoothing-regularization approach to mathematical programs with vanishing constraints, which is proposed in [3]. We have also shown that the VC-MFCQ implies that the smoothing-regularization problems satisfy the standard MFCQ. While it seems possible to prove that many other VC-tailored constraint qualifications imply that the corresponding standard constraint qualification holds for the smoothing-regularization problem, it is an open question whether one can further relax the VC-MFCQ assumption to get strong stationarity in the limit.



---

*Source: 715015-2014-09-01.xml*