# Strong Convergence on the Aggregate Constraint-Shifting Homotopy Method for Solving General Nonconvex Programming

Authors: Zhichuan Zhu; Yeong-Cheng Liou
Journal: Journal of Mathematics
 (2020)

---

## Abstract

In the paper, the aggregate constraint-shifting homotopy method for solving general nonconvex nonlinear programming is considered. The aggregation is only about inequality constraint functions. Without any cone condition for the constraint functions, the existence and convergence of the globally convergent solution to the K-K-T system are obtained for both feasible and infeasible starting points under much weaker conditions.


---

## Body

## 1. Introduction

Throughout, letRn, R+n, and R++n denote the n-dimensional Euclidean space, nonnegative orthant, and positive orthant of Rn, respectively. In the paper, the following general nonconvex nonlinear programming will be considered:(1)minfxs.t.gix≤0,i=1,2,…,mhjx=0,j=1,2,…,l,where x∈Rn and fx:Rn⟶R, gix:Rn⟶Rm, and hjx:Rn⟶Rl are three continuously differentiable functions. Denote Ω=x|gix≤0,i=1,2,…,m,hjx=0,j=1,2,…,l,Ω0=x|gix<0,i=1,2,…,m,hjx=0,j=1,2,…,l, and Ix=x|gix=0,i=1,2,…,m.It is well known that the solution of the optimization problem can be obtained through solving the K-K-T system of the convex nonlinear problem, but for the nonconvex nonlinear problem, we can only obtain the solution to the K-K-T system of problem (1).Homotopy method has been paid much attention as an important globally convergent computational method in finding solutions to various nonlinear problems since it was introduced and studied by Kellogg et al. [1], Smale [2], and Chow et al. [3]. However, the original homotopy is only single homotopy and needs much strong assumptions when solving nonlinear problems. In the 1990s, a combined homotopy interior point (CHIP) method was firstly proposed for solving nonconvex programming under the normal cone condition by Feng and Yu in [4]. From then on, various CHIP methods, as an efficiently implementable algorithm, were widely used and newly constructed for solving general nonconvex programming, fixed point problems, complementarity problems, variational inequality, and so on, see, e.g., [5–20].In 2001, for reducing the dimension of the systems arising in the numerically tracing process and weakening convergent conditions, Yu et al. [21] proposed an aggregate constraint homotopy method (ACH method) for nonconvex programming by using the so-called aggregate function of the constraints. In 2018, a new ACH method for nonlinear programming problems with inequality and equality constraints was presented in [22]. However, the ACH method still belongs to CHIP since it requires the initial point which was also in the original feasible set. In 2006, to avoid the disadvantage of CHIP must choose the initial point in the feasible set, a constraint-shifting combined homotopy infeasible interior-point method in which the initial point can be chosen in both feasible and infeasible sets for solving nonlinear programming with only inequality constraints was proposed by Yu and Shang in [23, 24]. In 2012, to extend the constraint-shifting combined homotopy method to solve the general nonlinear programming, another new combined homotopy infeasible interior-point method for solving nonconvex programming with both inequality and equality constraints was proposed in [25], in which only inequality constraints need to satisfy the normal cone condition. From then on, more constraint-shifting homotopy equations were constructed and extended for solving nonlinear programming, principal-agent problem, fixed point problem, and so on, see, e.g., [26–30]. However, these combined homotopy methods usually required some cone conditions for proving the strong convergence of the existence of the smooth homotopy pathway.By the enlightenment of the above references, without any cone condition, an aggregate constraint combined homotopy infeasible interior-point method for solving nonconvex nonlinear programming with both inequality and equality constraints is constructed, and the global convergence under much weaker conditions is obtained in the paper.The remainder of this paper is organized as follows. In Section2, the homotopy equation is constructed, and some lemmas from differential topology are introduced. In Section 3, the main results will be presented, and the existence and convergence of a smooth path from any given point in the infeasible set to the solution of K-K-T systems are proved. In Section 4, the numerical algorithm is presented.


## 2. Preliminaries

The following assumptions will be used:(A1)
Ω is a bounded and connected set, Ω0≠ϕ.(A2)
∀x∈Ω, matrix ∇gixi∈Ix,∇hjx is positive linearly independent at x, i.e.,(2)∑i∈Ixαi∇gix+∑j=1mβj∇hjx=0,αi∈R+,βj∈R⟹αi=βj=0.By [21], the aggregate function gx,μ=μln∑i=1mexpgix/μ, we have(3)I∇xgx,μ=∑i=1mτix,μ∇gix,τix,μ≜expgix/μ∑j=1mexpgjx/μ,IIgx≤gx,μ≤gx+μlnm.We construct the following shifted aggregate constraint function only with inequality constraint functions:(4)g˜x,μ=μϕx+θ−μgx,μ,where θ∈0,1 is a parameter and ϕx are convex and three continuously differentiable functions. Therefore, we have(5)g˜x,θ=θϕxand(6)limμ⟶0+g˜x,μ=limμ⟶0+μϕx+θ−μgx,μ=θgx,μ.Obviously,g˜x,μ are also three continuously differentiable functions; let Ωμ=x|g˜x,μ≤0, Ωμ0=x|g˜x,μ<0, ∂Ωμ=Ωμ/Ωμ0, and Ω0=Ω.Lemma 1 (see [21]).
If assumptions (A1) and (A2) hold, then there existsθ1>0, for ∀μ∈0,θ1, and(7)∇xg˜x,μ≠0,∀x∈∂Ωμ.Lemma 2 (see [27]).
If assumptions (A1) and (A2) and hold, there existsθ2>0, for ∀μ∈0,θ2, and we have Ωμ which is a bounded and connected set, and Ωμ0 is nonempty.Lemma 3.
If assumptions (A1) and (A2) hold, there existsθ3>0, for any given feasible point x, and ∀μ∈0,θ3, matrix ∇xg˜x,μ,∇hjx is positive linearly independent.Proof.
Proved by contradiction. For∀μk∈0,θ3 and any feasible point xk, there exists αk≥0 and βjk∈R belonging to real part, which are simultaneously not equal to zeros, such that(8)αk∇xg˜xk,μk+∑j=1mβjk∇hjxk=0.
Letβk=max1≤j≤lβjk and ξk=maxαk,βk; divide both sides of (8) by ξk, i.e.,(9)αkξk∇xg˜xk,μk+∑j=1mβjkξk∇hjxk=0.
Whenμk⟶0, xk⟶x∗; let αk/ξk,βjk/ξk⟶α∗,βj∗, as k⟶∞, and we have(10)limk⟶∞αkξk∇xg˜xk,μk+∑j=1mβjkξk∇hjxk=limk⟶∞αkξkμk∇ϕxk+θ−μk∇xgxk,μk+∑j=1mβjkξk∇hjxk=limk⟶∞αkξkμk∇ϕxk+θ−μk∑i=1mτixk,μk∇gixk+∑j=1mβjkξk∇hjxk=α∗θ∑i=1mτix∗,0∇gix∗+∑j=1mβj∗∇hjx∗=0.
This is a contradiction with assumption (A2), so∃θ3>0, for any μ∈0,θ3, matrix ∇xg˜ix,μi∈Iμx,∇hjx is positive linearly independent.Defineθ=minθ1,θ2,θ3. Since Ωθ0 is nonempty, for any x0∈Ωθ0, y0∈R++m, and z0∈Rl, let w0=x0,y0,z0, and we construct the homotopy equation as follows:(11)Hw,w0,μ=1−μ∇fx+∇xg˜x,μθy+∇hxz+μx−x0Yg˜x,μθ+μηhx−μz=0,where w=x,y,z∈Ωμ×R+m×Rl, η∈R++m, and Y=diagy.Whenμ=0, homotopy equation (11) turns to the K-K-T system(12)∇fx+θ∑i=1m∇gixyi+∑j=1l∇hjxzjYθgxhx=0.Whenμ=1, homotopy equation (11), Hw,w0,1=0, has a unique simple solution(13)x,y,z=x0,y0,z0=x0,−diagg˜x0,θ−1η,hx0.The following lemmas from differential topology will be used in the next section. At first, letU⊂Rn be an open set, and let ϕ:U⟶Rp be a Cαα>max0,n−p mapping; we say that y∈Rp is a regular value for ϕ if(14)Range∂ϕx∂x=Rp,∀x∈ϕ−1y.Lemma 4 (see [31]).
LetV⊂RnandU⊂Rm be open sets, and let ϕ:V×U⟶Rk be a Cα mapping, where α>max0,m−k. If 0∈Rk is a regular value of ϕ, then for almost all a∈V, 0 is a regular value of ϕa=Fa,⋅.Lemma 5 (see [31]).
Letϕ:U⊂Rn⟶Rp be Cαα>max0,n−p. If 0 is a regular value of ϕ, then ϕ−10 consists of some n−p-dimensional Cα manifolds.Lemma 6 (see [31]).
A one-dimensional smooth manifold is diffeomorphic to a unit circle or a unit interval.


## 3. Main Results

For a givenw0∈Ωθ0×R++m×Rl, rewrite Hw,w0,μ in homotopy equation (11) as(15)Hw0w,μ=Hw,w0,μ.The zero-point set ofHw0w,μ is(16)Hw0−10=w,μ∈Ωθ0×R++m×Rl×0,1:Hw0w,μ=0.Lemma 7.
If assumptions (A1) and (A2) hold, givenw0∈Ω_θ0^×R++m×Rl, and if there exists a smooth curve Γw0 starting from w0,1 in Ωμθ×R++m×Rl×0,1, then it must be bounded.Proof.
IfΓw0⊂Ωμθ×R++m×Rl×0,1 is unbounded, there exists xk,yk,zk,μk⊂Γw0, and xk,yk,zk,μk⟶∞.
From the second equation of (11), we have(17)Ykg˜xk,μkθ+μkη=0.
By equation (17), Ykg˜xk,μkθ≤0,i=1,2,…,m,xk∈Ωμkθ, and μkθ≤θ, and by Lemma 2, Ωμkθ is also bounded, so xk is a bounded sequence. Therefore, xk must exist a convergent subsequence which is also denoted as xk. Let xk⟶x^ and ‖yk,zk‖⟶∞ as k⟶∞. Denoting I∗=i∈1,2,…,myk⟶∞, by (17), I∗⊂Iμ^θx^; therefore, we obtain(18)g˜ixk,μkθ=−μkyik−1η,i∉I∗,g˜ix^,μ^θ=limk⟶∞g˜ixk,μkθ=0,i∈I∗,i.e.x^∈∂Ωμ^θ.
From the first equation of (11), we have(19)1−μk∇fxk+∑i=1myik∇xg˜ixk,μkθ+∑j=1m∇hjxkzjk+μkxk−x0=0.(i)
Whenμ^=1, from the third equation of (11), we have zk⟶hx^ as k⟶∞, which implies that zk is bounded. Hence, yk=∞ and x^∈Ωθ. If 1−μkyk<∞, without loss of generality, and suppose 1−μkyk⟶y^, then yi^=0 for i∉Iθx^ from the second equation of (11). Taking limits in (19), we have(20)x0=x^+limk⟶∞1−μk∇fxk+∑i=1m∇xg˜ixk,μkθyik+∑j=1l∇hjxkzjk=x^+limk⟶∞∑i∈Iθx^1−μkyik∇xg˜ixk,μkθ=x^+∑i∈Iθx^yi^∇xg˜ix^,θ,butg˜x,θ=θϕx is a convex function; this is impossible.If1−μkyk⟶∞, the discussion is the same as the following case (ii).(ii)
Whenμ^∈0,1, without loss of generality, suppose that 1−μkyk/1−μkyk⟶α^ with ‖α^‖=1 and αi^=0 for i∉Iμ^θx^. Through dividing both sides of equation (19) by 1−μkyk and taking limits, we have(21)∑i∈Iμ^θx^α^i∇xg˜ix^,μ^θ=0,which contradicts with Lemma3.(iii)
Whenμ^=0, without loss of generality, suppose that yk,zk/yk,zk⟶α^,β^ with α^,β^=1 and αi=0, for i∉I0x^. Through dividing both sides of equation (19) by yk,zk and taking limits, we have(22)∑i∈I0x^α^i∇xg˜ix^,0+∑j=1lβj∇hjx^=0,which contradicts with Lemma 3.
In conclusion, from the above discussion, we obtain thatΓw0 is a bounded curve in Ωμθ×R++m×Rl×0,1.Theorem 1.
Suppose assumptions (A1) and (A2) hold, for almost allw0∈Ωθ0×R++m×Rl, the zero-point set of homotopy equation (11) contains a smooth curve Γw0⊂Ωθ×R+m×Rl×0,1 starting from x0,y0,z0,1, which terminates or approaches to the hyperplane μ⟶0. If x∗,y∗,z∗,0 is a limit point of Γw0, then w∗=x∗,y∗,z∗ is a solution to the K-K-T system of problem (11).Proof.
LetH˜w,x0,μ:Ωμθ×R+m×Rl×Ωθ0×0,1⟶Ωμθ×R+m×Rl be the same map as Hw,x0,μ but taking x0 as variate. Consider the following submatrix of the Jacobian DHw,x0,μ:(23)∂H˜w,x0,μ∂y,z,x0=∗∗−μIdiagg˜x,μθ000−μI0.
For allμ∈0,1 and any x0∈Ωθ0, from w,μ∈Hw0−10 and Yg˜x,μθ+μη=0, we get that diagg˜x,μθ is nonsingular, which implies that ∂H˜w,x0,μ/∂y,z,x0 is nonsingular.
Hence, matrixDH˜w,x0,μ is full row rank. That is, 0 is a regular value of H˜w,x0,μ. By Lemma 4, we have that, for almost all x0∈Ωθ0, 0 is a regular value of Hw,x0,μ.
Note that the matrix(24)∂Hw0,w0,1∂w=I00∗diagg˜x0,θ0∗0−Iis nonsingular. From Lemma 5, if 0 is a regular value of Hw,w0,μ, ∂Hw0,w0,1/∂w is nonsingular, and the fact Hw0,w0,1=0,Hw0−10 must contain a smooth curve Γw0 starting from x0,y0,z0,1 and going to Ωμθ×R+m×Rl×0,1. Then, from Lemma 6, the curve Γw0⊂Ωμθ×R+m×Rl×0,1 must be diffeomorphic to a unit circle or a unit interval 0,1.
We have thatΓw0 is not diffeomorphic to a unit circle. That is, Γw0 is diffeomorphic to 0,1. Let x∗,y∗,z∗,μ∗ be a limit point of Γw0; only the following five cases are possible:(25)ix∗,y∗,z∗∈Ωθ×R+m×Rlμ∗=1y∗,z∗<∞,iix∗,y∗,z∗∈Ωμ∗θ×R+m×Rlμ∗∈0,1y∗,z∗=∞,iiix∗,y∗,z∗∈Ωμ∗θ×∂R+m×Rlμ∗∈0,1y∗,z∗<∞,ivx∗,y∗,z∗∈∂Ωμ∗θ×R++m×Rlμ∗∈0,1y∗,z∗<∞,vx∗,y∗,z∗∈Ω×R+m×Rlμ∗=0y∗,z∗<∞.
Sincew0,1 is only one solution of the equation Hw,w0,1=0 and ∂Hw0,w0,1/∂w is nonsingular, case (i) is impossible. From Lemma 7, case (ii) is also impossible.
Fromdiagg˜x∗,μ∗θy∗+μ∗η=0, we have that μ∗>0 and y∗∈∂R+m, i.e.,yi∗=0, for some 1≤i≤m, cannot happen simultaneously. Therefore, case (iii) is impossible. If the multipliers y∗>0 and the homotopy parameter μ∗>0, from diagg˜x∗,μ∗θy∗+μ∗η=0, we can get diagg˜x∗,μ∗θ<0, which implies that case (iv) is also impossible.
As a conclusion, case (v) is the only possible case. That is, curveΓw0 must terminate in or approach to the hyperplane at μ∗=0. And hence, w∗=x∗,y∗,z∗ is a solution to the K-K-T system of problem (1).


## 4. Numerical Algorithm

By Theorem1, homotopy equation (11) generates a smooth curve Γw0 for almost all w0,μ∈Ωθ0×R++m×Rl×0,1 as μ⟶0, and one can find a solution of homotopy equation (11). Letting s to be the arc length of Γw0, we can parameterize Γw0 with respect to s, i.e.,(26)Hws,μs=0,w0=w0,μ0=1.By differentiating (26), we can get(27)H′ws,μsw˙μ˙=0,μ0=w0,μ0=1,where H′ is the derivative of H.As how to trace the homotopy pathΓw0 numerically, we can use the standard predictor-corrector procedure; for more details, see [32, 33]. In this paper, our contribution is only the theoretical results about the proposed algorithm which only requires that any initial point can be chosen in the shifted feasible set but not necessarily in the original feasible set. The relative homotopy algorithms and numerical simulations on the performance for the proposed algorithm can be implemented as [34].



---

*Source: 8887029-2020-12-15.xml*