黄青群

(河池学院 数学系，广西 宜州 546300)

0 引言

自从文献［1，2］中提出运用组合同伦内点法求解非凸规划问题后，近年来数值求解非线性规则问题(NLP)的工作很多，文献［3－6］都利用组合同伦内点算法求解凸非线性规划问题，并分别证明了算法的大范围线性及局部次平方收敛性和给出了算法的全局线性收敛性及多项式时间复杂性的证明。在文献［3－6］的基础上，本文利用所求非线性规划问题的KKT条件，提出一个牛顿法与同伦法相结合的算法，最后给出了该算法的全局线性收敛性的证明。

考虑非线性规划问题(NLP):

为了叙述方便，作记号如下:

问题(1)的KKT条件为:

其中y∈n为对应于不等式约束的拉格朗日乘子。

由文献［7］可知，对于无约束优化问题

其中

μ ∈ (0，1］，x0∈ Ω0，ζi＞ 0 为权系数，ζ=(ζi，…，ζm)T。其等价形式为:

其中μ∈ (0，1］，x0∈Ω0。当 ζ=e=(1，…，1)T时，式(3)’即为本文所运用的同伦方程

同伦方程H(ω，μ)=0的解形成一条曲线Γ，这条解曲线Γ称为同伦路径，且

本文在第二部分给出了β—锥邻域的定义及算法的基本框架，第三部分证明了算法的全局收敛性。其中符号‖·‖表示欧氏范数。

若满足以下三个条件，可以证明同伦路径的存在性和收敛性:

(A1)Ω0非空有界。

(A2)∀x∈∂Ω，{▽gi(x):i∈B(x)}是列满秩矩阵。

(A3)(Ω在x处的法锥条件)∀x∈∂Ω，Ω在x点的法锥与Ω仅交于点x，即∀x∈∂Ω，有

1 算法

令

称N(β，μ)为β—锥邻域，其中β＞0为邻域半径。下面的引理证明了β—锥邻域在可行域的内部。

引理1［7］: 设 y ＞ 0，β ∈ (0，1)，则有 N(β，μ)⊂ Ω0× Rm++× (0，1］。

算法:

步骤1(初始化):

令 k=0，μ0＜ 1，β0=1，β ∈ (0，β0)，(ω0，1)∈ N(β，1)，α =(0，1)，δ∈ (0，1)，ε ＞ 0。

步骤2(终止条件):

其中 Δωk=(Δxk，Δyk)T。

步骤4(线搜索):

取 λk为 1，δ，δ2，… 中的最大值，它满足

令 ωk+1= ωk+ λkΔωk，μk+1=(1 － αλk)μk，k:=k+1，返回步 1。

引理2［7］:f(x)，gi(x)，i=1，2，…，m为充分光滑函数，ω0∈Ω0×m++，则对任意的μ∈(0，1］，(ω，μ)∈ N(β，μ)，H'ω(ω，μ)是非奇异的。

注:由引理2可知方程(4)有唯一解且Δμk=－αμk。……