# A Comparison of Normal Cone Conditions for Homotopy Methods for Solving Inequality Constrained Nonlinear Programming Problems

Authors: Zhengyong Zhou; Ting Zhang
Journal: Advances in Mathematical Physics
 (2020)

---

## Abstract

Homotopy methods are powerful tools for solving nonlinear programming. Their global convergence can be generally established under conditions of the nonemptiness and boundness of the interior of the feasible set, the Positive Linear Independent Constraint Qualification (PLICQ), which is equivalent to the Mangasarian-Fromovitz Constraint Qualification (MFCQ), and the normal cone condition. This paper provides a comparison of the existing normal cone conditions used in homotopy methods for solving inequality constrained nonlinear programming.


---

## Body

## 1. Introduction

In this paper, we consider the following inequality constrained nonlinear programming (ICNLP) problem:(1)minfx,s.t.gix≤0,i=1,⋯,m,where x∈Rn is the variable, f:Rn⟶R and gi:Rn⟶R, i=1,⋯,m, are three times continuously differentiable.Over the past few decades, the theory, algorithms, and applications of nonlinear programming have been rapidly developed, and many numerical methods have been proposed, such as augmented Lagrangian methods, sequential quadratic programming methods, reduced gradient methods, interior point methods, and homotopy methods. Homotopy methods are powerful numerical methods for solving many nonlinear problems. The primary advantage of homotopy methods is that their global convergence can be established under fairly weak assumptions, and the starting points can be chosen rather freely. A comprehensive introduction of the homotopy methods can be found in, e.g., the books [1, 2]. The first homotopy method for solving nonlinear programming was proposed for general convex programming in [3]. Among these available homotopy methods for solving nonlinear programming, most of them are designed for solving nonconvex ICNLP problems.In 1995, the combined homotopy interior point (CHIP) method was proposed for solving nonconvex ICNLP problems in [4, 5]. Hereafter, many modified CHIP methods have been proposed for nonconvex ICNLP problems. The global convergence of these homotopy methods can be generally established under three conditions on the original problem: the nonemptiness and boundedness of the interior of the feasible set; the Positive Linear Independent Constraint Qualification (PLICQ), which is equivalent to the Mangasarian-Fromovitz Constraint Qualification (MFCQ) (see [6]); and one type of normal cone conditions, which guarantees the boundedness of the homotopy path near the starting hyperplane. It is well known that the first two conditions are generally used in numerical methods for solving nonlinear programming. The normal cone conditions are generalization of the convexity of the feasible set and extend these homotopy methods from convex programming to nonconvex programming. In addition, a probability-one homotopy method was also proposed for solving nonconvex ICNLP problems in [7]; its global convergence was established under the nonemptiness and boundedness of a parametrized feasible set, Arrow-Hurwicz-Uzawa constraint qualification, and that the homotopy path does not go to infinity near the starting hyperplane. In recent years, these homotopy methods have been extended to fixed point problems, variational inequalities, semidefinite programming, multiobjective programming, constrained sequential minimax problems, and so on.In this paper, we present the typical normal cone conditions for homotopy methods for solving ICNLP problems, along with the corresponding homotopy maps and global convergence. We give a comparison of four normal cone conditions, including the normal cone condition, the quasinormal cone condition, the pseudocone condition, and the weak normal cone condition. Their relations are discussed in detail for the first time. Some typical nonconvex sets are presented. The comparison can help us to identify features of these normal cone conditions and the corresponding homotopy methods and may motivate us to give some improved homotopy methods for specialized nonconvex programming.To obtain our results, we conclude this section with some notations. Throughout this paper,Ω=x∈Rn∣gix≤0,i=1,⋯,m represents the feasible set of the ICNLP problem (1); Ω0=x∈Rngix<0,i=1,⋯,m denotes the interior of Ω; ∂Ω=ΩΩ0 means the boundary of Ω. Ix=i∈1,⋯,m∣gix=0 represents the active index set of inequality constraints at x. R+m and R++m denote the nonnegative and positive quadrant of Rm, respectively. I indicates the identity matrix. · denotes the Euclidean norm. For a function F:Rn⟶Rm, F−1C=x∈Rn∣Fx∈C is the inverse of the set C∈Rm; the n×m matrix ∇Fx, whose i,jth element is ∂Fjx/∂xi, is the transpose of the Jacobian of F.Assumption 1.
Ω0 is nonempty and bounded.Assumption 2.
The Positive Linear Independent Constraint Qualification holds: for anyx∈∂Ω, yi≥0, i∈Ix,
(2)∑i∈Ixyi∇gix=0,yi≥0,i∈Ix,implyyi=0,i∈Ix.


## 2. Normal Cone Conditions and Homotopy Methods for ICNLP Problems

There exist four typical normal cone conditions in homotopy methods for solving ICNLP problems in literatures; related results will be introduced in this section.For the nonconvex ICNLP problem (1), the first homotopy method, called the combined homotopy interior point (CHIP) method, was proposed in [4, 5]. The combined homotopy map is constructed as
(3)Hx,y,t=1−t∇fx+∇gxy+tx−x0Ygx−tY0gx0,where x,y,t∈Ω×R+m×0,1, x0,y0∈Ω0×R++m, Y and Y0 are diagonal matrices with the ith diagonal elements yi and yi0 for i=1,⋯,m, respectively. Under Assumption 1, the assumption that ∇gix∣i∈Ix has a full column rank for any x∈∂Ω, which can be replaced by Assumption 2, and the assumption that Ω satisfies the normal cone condition (see Definition 3), for almost all x0,y0∈Ω0×R++m, the zero point set of (3) defines a smooth homotopy path Γx0,y0⊂Ω0×R++m×0,1, which starts from x0,y0,1 and approaches to the hyperplane t=0. For any limit point x∗,y∗,0 of Γx0,y0, x∗ is a KKT point of the problem (1), y∗ is the corresponding Lagrange multiplier.Definition 3. (normal cone condition (NCC), see [4, 5]).
For anyx∈∂Ω, if
(4)x+∑i∈Ixyi∇gix∣yi≥0,i∈Ix⋂Ω0=∅,then, Ω is said to satisfy the NCC.According to Definition3, the NCC means that, for any x∈∂Ω, the set x0−x∣x0∈Ω0 does not intersect with the cone ∑i∈Ixyi∇gix∣yi≥0,i∈Ix. Moreover, if gi:Rn⟶R, i=1,⋯,m, are convex, then Ω satisfies the normal cone condition; however, the reciprocal implication is not true, a typical counterexample is Ω=x∈R2∣−x1−42−x22+8≤0,−2x1+x22≤0,x1−3≤0 (see Figure 1). In [8], a modified CHIP method was presented. The homotopy map is defined as
(5)Hx,y,t=1−t∇fx+∇gxy+tηxy2+tx−x0Ygx−tY0gx0,where x,y,t∈Ω×R+m×0,1, x0,y0∈Ω0×R++m, and ηx is a positive independent map with respect to ∇gx (see Definition 4). Under Assumption 1, the assumption that ∇gix∣i∈Ix are linear independent for any x∈∂Ω, which can be also replaced by Assumption 2, and the assumption that Ω satisfies the quasinormal cone condition related to the positive independent map ηx (see Definition 5), for almost all x0,y0∈Ω0×R++m, the global convergence of a smooth homotopy path Γx0,y0⊂Ω0×R++m×0,1 starting from x0,y0,1 and approaching to the hyperplane t=0 can be established; then, a KKT point x∗ with the corresponding Lagrange multiplier y∗ can be obtained.Definition 4 (positive independent map, see [8]).
If there exist smooth mapsηix:Rn⟶Rnfori=1,⋯,m, such that, for any x∈∂Ω,
(6)∑i∈Ixyi∇gix+αiηix=0,yi≥0,αi≥0,i∈Ix,implyyi=0,αi=0,i∈Ix,then, ηx=η1x,⋯,ηmx is said to be a positive independent map with respect to ∇gx.Definition 5 (quasinormal cone condition (QNCC) [8]).
If there exists a smooth positive independent mapηx=η1x,⋯,ηmx with respect to ∇gx such that, for any x∈∂Ω,
(7)x+∑i∈Ixαiηix∣αi≥0,i∈Ix⋂Ω0=∅,then, Ω is said to satisfy the QNCC related to ηx.
According to Definition5, the QNCC means that, for any x∈∂Ω, the set x0−x∣x0∈Ω0 does not intersect with the cone ∑i∈Ixαiηix∣αi≥0,i∈Ix.
In [9], another modified CHIP method was proposed with the homotopy map
(8)Hx,y,t=1−t∇fx+∇gxy+∑i=1mηix,1−tyi2+tx−x0Ygx−tY0gx0,where x,y,t∈Ω×R+m×0,1, x0,y0∈Ω0×R++m, and ηx,1−ty2=η1x,1−ty12,⋯,ηmx,1−tym2 is a consistent hair map (see Definition 7). Similarly to the homotopy methods in [1, 6], under Assumption 1, the assumption that ∇gix∣i∈Ix has a full column rank for any x∈∂Ω, and the assumption that Ω satisfies the pseudocone condition with respect to the consistent hair map ηx,z (see Definition 8), the global convergence can be established.Definition 6 (hair map, see [9]).
Fori=1,⋯,m, the map ηix,zi:Rn×R+⟶Rn is said to be a hair map of Ωi=x∈Rn∣gix≤0, if
(1)
ηix,0=0 and for any x∈∂Ωi=∂Ω∩Ωi(9)ηix,zi=0⇔zi=0,(2)
For anyx∈∂Ωi, limzi→∞ηix,zi=∞Definition 7 (consistent hair map, see [9]).
The mapηx,z=η1x,z1,⋯,ηmx,zm is said to be a consistent hair map of Ω, if for any x∈∂Ω,
(1)
ηix,zi is a hair map of Ωi for i=1,⋯,m(2)
∑i∈Ixyi∇gix+ηix,zi=0,yi≥0,zi≥0 imply yi=0,zi=0,i∈Ix;(3)
y,z⟶∞ implies ∑i∈Ixyi∇gix+ηix,zi⟶∞Definition 8 (pseudocone condition (PCC), see [9]).
If there exists a consistent hair mapηx,z of Ω, such that for any x∈∂Ω,
(10)x+∑i∈Ixηix,zi∣zi≥0,i∈Ix⋂Ω0=∅,then, Ω is said to satisfy the PCC with respect to ηx,z.
According to Definition8, the PCC means that, for any x∈∂Ω, the set x0−x∣x0∈Ω0 does not intersect with the set ∑i∈Ixηix,zi∣zi≥0,i∈Ix.
In [10], using the following aggregate function introduced in [11, 12],
(11)g^θx,t=θtln∑i=1mexpgix/θt,where t>0 is the smoothing parameter, the parameter θ∈0,1, an aggregate constraint homotopy interior point method was proposed. The aggregate constraint homotopy map is defined as
(12)Hx,y,t=1−t∇fx+y∇xg^θx,t+tx−x0yg^θx,t−ty0g^θx0,1,where x,y,t∈Ω×R+×0,1, x0,y0∈Ω^×R++, and Ω^ is an opened subset of Ω0. Under Assumption 1, the assumption that ∇gix∣i∈Ix has a full column rank for any x∈∂Ω, and the assumption that Ω satisfies the weak normal cone condition with respect to Ω^ (see Definition 9), then, there exists a θ¯∈0,1 such that for any θ∈0,θ¯, Ω^⊂Ωθt0=x∈Rn∣g^θx,t<0⊂Ω0 for t∈0,1, for almost all x0,y0∈Ω^×R++, the zero point set of (12) defines a smooth homotopy path Γx0,y0, which starts from x0,y0,1 and approaches to the hyperplane t=0. Moreover, let (x∗,y∗,0) be any limit point of Γx0,y0, and λi∗=y∗yix∗,0 (where yix∗,0 is a limit point of yix,t=expgix/θt/∑j=1mexpgjx/θt) for i=1,⋯,m, then y∗ is finite, x∗ is a KKT point of (1), and λ1∗,⋯,λm∗ is the corresponding Lagrangian multiplier.Definition 9 (weak normal cone condition (WNCC) [10]).
If there exists an open subsetΩ^⊂Ω0 such that, for any x∈∂Ω,
(13)x+∑i∈Ixyi∇gix∣yi≥0,i∈Ix⋂Ω^=∅,then, Ω is said to satisfy the WNCC with respect to Ω^.
According to Definition9, the WNCC means that there exists an open subset Ω^⊂Ω0 such that for any x∈∂Ω, the set x0−x∣x0∈Ω^ does not intersect with the cone ∑i∈Ixyi∇gix∣yi≥0,i∈Ix.Figure 1
The setΩ=x∈R2∣−x1−42−x22+8≤0,−2x1+x22≤0,x1−3≤0.


## 3. A Comparison of the Four Typical Normal Cone Conditions

In this section, for the first time, we study the relations of the four typical normal cone conditions introduced in Section2, and some typical nonconvex sets are introduced.Proposition 10.
If the PLICQ holds, the NCC implies the QNCC and PCC.Proof.
Suppose that the PLICQ holds, thenηx=∇g1x,⋯,∇gmx is a positive independent map with respect to ∇gx by Definition 4, and ηx,z=z1∇g1x,⋯,zm∇gmx is a consistent hair map of Ω by Definition 7. Then, Ω satisfies the QNCC with respect to ηx by Definition 5, and the PCC with respect to ηx,z by Definition 8.Counterexample 3.2.
The nonconvex set (see Figure2) Ω=x∈R2∣x16−3x14+3x12+x2−1≤0,−x2≤0.
The setΩ in Counterexample 3.2 satisfies the NCC. However, for x¯=1,0∈∂Ω, we have Ix¯=1,2, ∇g1x¯=0,1 and ∇g2x¯=0,−1, which means that the PLICQ does not hold at 1,0. Hence, there does not exist a positive independent map ηx with respect to ∇gx by Definition 4, and the consistent hair map ηx,z of Ω by the second item of Definition 7. Therefore, the PLICQ is necessary in Proposition 10.Proposition 11.
The NCC implies the WNCC.Proof.
By Definition3 and Definition 9, if Ω satisfies the NCC, Ω satisfies the WNCC with respect to any open subset Ω^⊂Ω0.Counterexample 3.4.
The nonconvex set (see Figure3) Ω=x∈R2∣gix≤0,i=1,2,3, where
(14)g1x=4−x12−x22,x1<0,4−x22,x1≥0,g2x=x12+x22−16,x1<0,x22−16,x1≥0,g3x=x1−4.
The setΩ in Counterexample 3.4 satisfies the QNCC with respect to the positive independent map ηx=4−x1,−x2,∇g2x,∇g3x, the PCC with respect to the consistent hair map ηx,z=z14−x1,−x2,z2∇g2x,z3∇g3x, and the WNCC with respect to any open subset of x∈Ω∣g1x≤0,g2x≤0,x1≤0. For x¯=0,2∈∂Ω with Ix¯=1 and ∇g1x¯=0,−4, we have x¯+y¯1∇g1x¯=0,−3∈Ω0 with y¯1=5/4, which contradicts (4). Then, we know that the NCC does not hold. Therefore, we have the following result.Remark 12.
Any of the QNCC, PCC, and WNCC does not imply the NCC.Proposition 13.
The QNCC implies the PCC.Proof.
IfΩ satisfies the QNCC with respect to the positive independent map ηx, we know that ηx,z=z1η1x,⋯,zmηmx is a consistent hair map of Ω by Definition 7. Then, Ω satisfies the PCC with respect to the consistent hair map ηx,z by Definition 8.Counterexample 3.7.
The nonconvex set (see Figure4) Ω=x∈R2∣gix≤0,i=1,⋯,10, where
(15)g1x=−x2+2,−2≤x1≤0,x2≥−5,g2x=−x1−x2+2,0≤x1≤1,x1+x2≥0,g3x=−x2+1,1≤x1≤2,x2≥−5,g4x=x1−2,1≤x2≤3,g5x=x2−3,g6x=−x1−3,g7x=−x2−6,g8x=x1−7.01,g9x=x2+5,x1≥−2,x2≤1,g10x=x1+2,x1≤2,−5≤x2≤2.Figure 2
The set in Counterexample3.2.Figure 3
The set in Counterexample3.4.Figure 4
The set in Counterexample3.7.Forx¯=0,2∈∂Ω with Ix¯=1,2, and any positive independent map ηx, there exists a z¯∈R+10 such that x¯+z¯1η1x¯+z¯2η2x¯∈Ω0. Hence, the QNCC does not hold. Define the consistent hair map ηx,z as
(16)η1x,z1=η¯1x1,z1−x,x1∈−2,0,x2=2,η¯1x1,z1=1−z1x1,2+z11,1,0≤z1≤1,z1,ψx1,z1,1<z1<2,z1,0.5,z1≥2,where ψu,v=1/u−1+1v3+5/u−1−9/2v2+8/u−1+6v−4/u−1−3/2 satisfying
(17)ψu,1=1,ψu,2=0.5,∂ψu,1∂v=1u−1,∂ψu,2∂v=0,which means that η¯1u,v is continuously differentiable in −2,0×0,∞. For any u∈−2,0, we have 1/u−1+1≥0, ∂ψu,1/∂v=1/u−1<0 and ∂ψu,2/∂v=0, and hence
(18)∂ψu,v∂v=31u−1+1v2−25u−1−92v+8u−1+6<0,v∈1,2,which means that ψu,v is monotone decreasing for v∈1,2. By using ψu,v, for any x∈∂Ω with x1∈0,1 and x2=−x1+2, we define
(19)η2x,z2=η¯2x,z2−x,η¯2x2,z2=1−z1x+z21,1,0≤z1≤1,z2,ψ0,z2,1<z1<2,z2,0.5,z1≥2,then, we know that η¯2u,v is continuously differentiable in u,v∈R2∣u∈0,1,v=−u+2×0,∞, and for any given u∈0,1, η¯2u,v is monotone decreasing for v∈0,2. For i=3,⋯,10,
(20)η3x,z3=z3,0,ηix,zi=zi∇gix,i=4,⋯,8,η9x,z9=z9,0,η10x,z10=z1010,−5−x2.Forx∈∂Ω with #Ix=1, we have that (10) holds by the definition of ηx,z. For any x=2,3,−3,3,−3,−6,7.01,−6∈∂Ω, we know that (4) holds. Hence, by Proposition 10 and the definitions of ηix,zi, i=4,⋯,8, we obtain that (10) also holds.Forx¯=0,2∈∂Ω with Ix¯=1,2, and any z1≥0, z2≥0, we know
(21)η1x¯,z1=η2x¯,z2∈u,v∈R2∣u∈0,1,v=−u⋃u,v∈R2∣u∈1,∞,v∈−32,−1.Then, we have(22)x¯+η1x¯,z1+η2x¯,z2∈u,v∈R2∣u∈0,2,v=−u+2⋃u,v∈R2∣u∈1,∞,v∈−12,1⋃u,v∈R2∣u∈2,∞,v∈−1,0,and hence, x¯+η1x¯,z1+η2x¯,z2∈Ω0. For x¯=1,1∈∂Ω with Ix¯=2,3, and any z2≥0, z3≥0, we know
(23)η2x¯,z2∈u,v∈R2∣∈0,∞,v∈−12,0,η3x¯,z3=z3,0.Then, we have(24)x¯+η2x¯,z2+η3x¯,z3∈u,v∈R2∣u∈1,∞,v∈12,1,and hence, x¯+η2x¯,z2+η3x¯,z3∈Ω0. For x¯=2,1∈∂Ω with Ix¯=3,4, and any z3≥0, z4≥0, we know
(25)η3x¯,z3=z3,0,η4x¯,z4=z4,0.Then, we have(26)x¯+η3x¯,z3+η4x¯,z4∈u,v∈R2∣u∈2,∞,v=1,and hence, x¯+η3x¯,z3+η4x¯,z4∈Ω0. For x¯=7.01,−5∈∂Ω with Ix¯=8,9, and any z8≥0, z9≥0, we know
(27)η8x¯,z8=z8,0,η9x¯,z9=z9,0.Then, we have(28)x¯+η8x¯,z8+η9x¯,z9∈u,v∈R2∣u∈7.01,∞,v=−5,and hence, x¯+η8x¯,z8+η9x¯,z9∈Ω0. For x¯=−2,−5∈∂Ω with Ix¯=9,10, and any z8≥0, z9≥0, we know
(29)η9x¯,z9=z9,0,η10x¯,z10=10z10,0.Then, we have(30)x¯+η9x¯,z9+η10x¯,z10∈u,v∈R2∣u∈−2,∞,v=−5,and hence, x¯+η9x¯,z9+η10x¯,z10∈Ω0. For x¯=−2,2∈∂Ω with Ix¯=1,10, and any z1≥0, z10≥0, we know
(31)η1x¯,z1∈u,v∈R2∣u∈0,3,v=−13u⋃u,v∈R2∣u∈3,∞,v∈−32,−1,η10x¯,z10=z1010,−7.Then, we have(32)x¯+η1x¯,z1+η10x¯,z10∈u,v∈R2∣u∈−2,∞,−710u+35≤v≤−13u+43⋃u,v∈R2∣u∈1,∞,−710u+65<v<1,and hence, x¯+η1x¯,z1+η10x¯,z10∈Ω0. Therefore, the PCC holds with respect to the consistent hair map ηx,z, and hence we have the following result.Remark 14.
The PCC does not imply the QNCC.Counterexample 3.9.
The nonconvex set (see Figure5) Ω=x∈R2∣gix≤0,i=1,⋯,5, where
(33)g1x=−x1−6,g2x=x1−6,g3x=−x2−10,g4x=x2−10,g5x=−x1225−x2281+1,x1<522,2−15x12−x2281,x1≥522.Figure 5
The set in Counterexample3.9.The setΩ in Counterexample 3.9 satisfies the QNCC with respect to the positive independent map ηx=∇g1x,⋯,∇g4x,6−x1,−x2, and the PCC with respect to the hair map ηx,z=z1∇g1x,⋯,z4∇g4x,z56−x1,−x2. For any x0∈Ω0, let k1x=∂g5x/∂x2/∂g5x/∂x1 for x∈x∈∂Ω∣∂g5x/∂x1≠0, k2x=x2−x20/x1−x10 for x∈x∈∂Ω∣x1−x10≠0. For convenience, we rewrite Ω0 as Ω0=Ω¯1⋃Ω¯2⋃Ω¯3⋃Ω¯4⋃Ω¯5⋃Ω¯6 with Ω¯1=u,v∈Ω0∣u>0,v>0, Ω¯2=0,v∈Ω0∣v>0, Ω¯3=u,v∈Ω0∣u<0,v≥0, Ω¯4=u,v∈Ω0∣u<0,v≤0, Ω¯5=0,v∈Ω0∣v<0, Ω¯6=u,v∈Ω0∣u>0,v<0.For anyx0∈Ω¯2, y¯5=9x20+9/2>0, and x¯=0,−9∈∂Ω with Ix¯=5, we have
(34)x¯+y¯5∇g5x¯=0,−9+9x20+920,29=x0.For anyx0∈Ω¯5, let y¯5=99−x20/2>0, x¯=0,9∈∂Ω with Ix¯=5, we have
(35)x¯+y¯5∇g5x¯=0,9+99−x2020,−29=x0.For anyx0∈Ω¯3 and x∈x∈∂Ω∣g5x=0,0<x1≤52/2,x2≤−92/2, k1x and k2x reduce to k¯1x1=−525−x12/9x1 and k¯2x1=−925−x12−5x20/5x1−x10, respectively. By the continuity of k¯1x1 and k¯2x1 on 0,52/2, limx1→0+k¯1x1−k¯2x1→−∞<0, k¯152/2−k¯252/2>0 coming from k¯152/2=−5/9 and k¯252/2∈−9/5−22,−9/4762−5, there exists an x¯1∈0,52/2 such that k1x¯1=k2x¯1, which means
(36)25x¯1−x102x¯1=8125−x¯12+45x20225−x¯12.Then, forx¯=x¯1,−925−x¯12/5∈∂Ω with Ix¯=5, y¯5=25x¯1−x10/2x¯1=8125−x¯12+45x20/225−x¯12>0, we have
(37)x¯+y¯5∇g5x¯=x¯1,−925−x¯125+y¯5−2x¯125,225−x¯1245=x¯1−25x¯1−x102x¯12x¯125,−925−x¯125+8125−x¯12+45x20225−x¯12225−x¯1245=x10,−925−x¯125+925−x¯12+5x205=x0Analogously, for anyx0∈Ω¯1⊂x∈R2∣−x1,x2∈Ω¯3, Ω¯4 and Ω¯6⊂x∈R2∣−x∈Ω¯3, there exist an x¯∈∂Ω with Ix¯=5 and a y¯5>0 such that
(38)x¯+y¯5∇g5x¯=x0.Therefore, the WNCC does not hold, and hence we have the following result.Remark 15.
The QNCC or PCC does not imply the WNCC.Counterexample 3.11.
The nonconvex set (see Figure6) Ω=x∈R2∣gix≤0,i=1,⋯,9, where
(39)g1x=−x1,g2x=x1−6,g3x=−x2,g4x=x2−4,g5x=−x1−x2+7,4≤x1≤6,x1+x2≥6,g6x=x1+x2−6,x1+x2≤7,4.5≤x2≤6,g7x=x1−4,x1≤4,1≤x2≤3,g8x=−x1+4.5,x1≥4,1≤x2≤1.5,g9x=x2−1,4≤x1≤4.5,x2≤2.Figure 6
The set in Counterexample3.11.The setΩ in Counterexample 3.11 satisfies the WNCC with respect to any open subset of x∈R2∣x1>0,0<x2<1,x1−x2−1<0⊂Ω0. For x¯=4.5,1.4∈∂Ω with Ix¯=8 and ∇g8x¯=−1,0, and any hair map ηx,z satisfying (10), we have x¯+η8x¯,0=x¯ and limz8→∞x¯+η8x¯,z8=∞ by Definition 6. Hence, there exists a z¯8>0 such that x¯+η8x¯,z¯8∈x∈R2∣4.6≤x1≤5.6,x2=1.4. Then, we know η8x¯,z¯8∈x∈R2∣0.1≤x1≤1.1,x2=0 and y¯8∇g8x¯+η8x¯,z¯8=0 with y¯8=η8x¯,z¯81>0, which contradicts the second item of Definition 7. Therefore, there does not exist a consistent hair map ηx,z with respect to Ω to satisfy the PCC, and the QNCC also does not hold by Proposition 13. Then, we obtain the following result.Remark 16.
The WNCC does not imply the QNCC or PCC.In conclusion, we show the relations among the four typical normal cone conditions in Figure7. It is noted that there still exist many nonconvex sets satisfying none of existing normal cone conditions, such as the nonconvex set in Counterexample 3.13.Counterexample 3.13.
The nonconvex set (see Figure8) Ω=x∈R2∣−x12−x22+2.25≤0,x12+x22−9≤0.Figure 7
Relations among the four typical normal cone conditions.Figure 8
The set in Counterexample3.13.


## 4. The Global Convergence of the Homotopy Methods for Solving ICNLP

As shown in Section2, the global convergence of these homotopy methods can be established under three conditions. In this section, we present some comments for these conditions.The boundedness ofΩ0 ensures that the variable x in the homotopy path keeps bounded. For Example 4.1, Ω0=x∈R2∣x12+x2<0 is unbounded, we have x⟶−∞,−∞ with y⟶0 and t→0 for the starting point x0=0,−1 with y0=1 in the homotopy path defined by the CHIP method. Since the real-world ICNLP problems generally have the optimal solutions at finity, the variable x in the homotopy path always keeps bounded even if Ω0 is unbounded. For Example 4.2, Ω0=x∈R2∣x12−x2<0 is unbounded, but we have x⟶−0.5,0.25 with y⟶1 and t⟶0 for the starting point x0=0,1 with y0=1 in the homotopy path defined by the CHIP method.Example 4.1.
(40)minx∈R2fx=x1+x2,s.t.gx=x12+x2≤0.Example 4.2.
(41)minx∈R2fx=x1+x2,s.t.gx=x12−x2≤0.
The PLICQ (MFCQ) is the most widely used constraint qualification for the ICNLP problems, it ensures that the variabley in the homotopy path keeps bounded. For Example 4.3, the PLICQ does not hold at 0,−1∈∂Ω, we have x⟶0,−1 that is not a KKT point, y⟶0,+∞,+∞ and t⟶0 for the starting point x0=−2,0 with y0=1,1,1, and x⟶2.8242,−1, y⟶0.1768,0,0.6464 and t⟶0 for the starting point x0=2,0 with y0=1,1,1 in the homotopy path defined by the CHIP method.Example 4.3.
(42)minx∈R2fx=−x1+x2,s.t.g1x=x12+x22−9≤0,g2x=−x12−x22+1≤0,g3x=−x2−1≤0.
The normal cone conditions and the PLICQ ensure that the variabley in the homotopy path keeps bounded when the homotopy path tends to the hyperplane x,y,1∣x,y∈Ω×R+m. Although our numerical experiences show that these homotopy methods always globally converge even if the normal cone conditions do not hold, the normal cone conditions are important to establish the global convergence of these homotopy methods in theory. For Example 4.4, the normal cone conditions do not hold for any x∈x∈R2∣x12+x22=1⊂∂Ω, but we have x⟶2,−2, y⟶0.25,0 and t⟶0 for all tested starting points x0∈Ω0 with y0=1,1 in the homotopy path defined by the CHIP method.Example 4.4.
(43)minx∈R2fx=−x1+x2,s.t.g1x=x12+x22−8≤0,g2x=−x12−x22+1≤0.


## 5. Conclusion

In this paper, we provide a comparison of four typical normal cone conditions used in homotopy methods for solving inequality constrained nonlinear programming. The NCC holds for convex sets and a class of nonconvex sets. The WNCC, QNCC, and PCC are more weak than the NCC. However, the NCC is more convenient to use than the WNCC, QNCC and PCC. For the feasible set satisfying the QNCC or PCC, some auxiliary maps should be constructed in the homotopy maps. For the feasible set satisfying the WNCC, the starting point for the homotopy methods should be chosen from a special open subset of the feasible set. On the other hand, except for few special nonconvex sets, there does not exist a general way of checking a set to satisfy the NCC or construct the open subset, the positive independent map and the consistent hair map for the WNCC, QNCC, and PCC, respectively.



---

*Source: 5483587-2020-07-04.xml*