基于凸组合的列文伯格 － 马夸尔特算法

摘要 要: 在列文伯格 - 马夸尔特算法( L - M) 在求解带非光滑约束方程组过程中，为了避免该算法受初始点和单一形式的步长影响的问题，本文采取凸组合技术( convex combination skill) ，将 L1 范数

　　要: 在列文伯格 - 马夸尔特算法( L - M) 在求解带非光滑约束方程组过程中，为了避免该算法受初始点和单一形式的步长影响的问题，本文采取凸组合技术( convex combination skill) ，将 L1 范数和 L2 范数并联使用，同时为了进一步改善 L - M 算法的性能，对已有的步长做出改进，提出一种新的 CMLM 算法，该算法每步迭代中，可以根据实际情况调整步长，并只需求解一个线性方程组. 该算法全局收敛，并在局部误差界条件下，局部二次收敛. 数据实验结果表明，该算法具有良好的计算效果.

　　关键词: 凸组合; 光滑技术; 列文伯格 - 马夸尔特算法; 收敛性分析

　　0 引 言

　　非光滑约束方程组问题在实际经济、工程领域中有着广泛的应用. 如在经济学中供应链问题、工程中最优控制及交通平衡等非线性互补问题均可以通过一定的方法转化非光滑约束方程组问题. 非精确列文伯格 - 马夸尔特算法是一种有效的求解非光滑( 连续可微) 约束方程组的算法. 在局部误差界条件下，文献[1 - 4]证明了非精确列文伯格 - 马夸尔特算法超线性收敛. 针对非光滑约束方程组的求解问题，文献[5]给出一种精确光滑化列文伯格 - 马夸尔特算法，该算法具有较好的计算效果. 但是，由于该算法在求解约束方程组受初始点和单一形式的步长影响的问题，本文采取凸组合技术( convex combination skill) ，将 L1 范数和 L2 范数并联使用，同时为了进一步改善 L - M 算法的性能，对已有的步长做出改进，提出一种新的 CMLM 算法，该算法每步迭代中，可以根据实际情况调整步长，并只需求解一个线性方程组. 该算法全局收敛，并在局部误差界条件下，局部二次收敛. 实验数据表明，该算法具有良好的计算效果.

　　1 模型和光滑化函数

　　考虑非光滑约束方程组 F( x) = 0 s. t. x ∈ X ， ( 1)其中 X = { x ∈ Rn | h( x) ≤ 0} ，F: X → Rp 和 h: Rn → Rm 均为局部 L—连续函数.题( 1) 可等价转化成如下无约束方程组 F( x) = 0 h( x) { + = 0， ( 2) 其中 h( x) + = ( ( h1 ( x) ) +，. . . ，( hm ( x) ) + ) T 和 ( a) + = max{ 0，a} . 根据光滑化逼近函数和强半光滑性质，我们假设函数 F 和 h 存在光滑化逼近函数，分别记为 F( t，x) 和 h( t，x) . 进一步，假设 F(·) 和 h(·) 在 R+ × Rn 上强半光滑. 记 z = ( t，x) .考虑下列方程组 H( z) = t G( t，x [ ] ) = 0， ( 3) 其中 G( t，x) = ( F( t，x) T ，H( t，x) T ) T 和 H( t，x) = 1 2 ( 珔h1 2 槡 ( t，x) + t 2 + 珔h1 ( t，x) ，…， 珔h2 m 槡 ( t，x) + t 2 + 珔hm ( t，x) ，) T .有复合函数性质知，H(·) 在 R+ × Rn 上局部 L—连续且强半光滑.命题 1 若 x* ∈X* . 存在常数 珋c > 0 和邻域 N( x* ，δ 珋) ，使得对任意 x∈ N ( x* ，δ 珋) ，有 珋c‖( F( x) ，h( x) + ) ‖≥dist( x，X* ) ，则存在 c1 > 0 和( 0，x* ) 的邻域 N( ( 0，x* ) ，b2 ) ∶ = z = ( t，x) |‖( t，x) - ( 0，x* ) ‖≤b { } 2，t≥0 ，使得对任意 z∈N( ( 0，x* ) ，b2 ) ，有 c1‖H( z) ‖≥dist( z，Z* ) .

　　2 一个光滑化的列文伯格 - 马夸尔特算法

　　我们现在给出求解( 3) 式的一个光滑化列文伯格 - 马夸尔特算法，该算法每一次迭代产生的点 ( t k ，xk ) 均满足 t k > 0 . 记效益函数为 Ψ( z) = ‖H( z) ‖2 /2 . 则 Ψ(·) 在任意点 z = ( t，x) ∈ R+ + × Rn 处连续可微. 取 珋t > 0 和 γ ∈ ( 0，1) 使得 珋tγ < 1 . 进一步，针对序列 { z k } ∞ k = 0  R+ + × Rn 和 { } αk ∞ k = 0  R+ + ，定义 β0 = β( z 0 ) ∶ = γmin 1，‖Ψ z ( ) { } 0 ‖2 ( 4) 和 βk = β( z k ) ∶ = βk-1， 如 γmin 1，αkΨ z ( )k { }2 > βk-1 γmin 1，‖αkΨ z ( ) { } k ‖ { 2 ， ( 5) 可知，数列 { βk } 单调递减，且对任意的 z 0 ∈ R+ + × Rn ，均有 珋t > β0 珋t . 为了使 tk > 0 恒成立，令 ( dk L ) t = - t k + βk 珋t . 求下列方程的解 ( G' x ( z k ) T G' x ( z k ) + μk Ι) ( dk L ) x = - G' x ( z k ) T ( G( z k ) + G't ( z k ) ( dk L ) t ) ， ( 6) 其中 μk = δ‖H( z k ) ‖ + ( 1 - δ) ‖H( z k ) ‖2 . 记( 6) 式的解为 ( dk L ) x . 可得，如果 z k 是( 3) 式的解，则 μk > 0 ，于是方程( 6) 式有唯一解 ( dk L ) x . 下面给出求解( 3) 式的一个光滑化列文伯格 - 马夸尔特算法.算法步骤 1 选择参数 η，ρ，σ ∈ ( 0，1) ，γ ∈ ( 0，1) 使得 珋tγ < 1 . 取初始点 z 0 = ( t 0 ，x 0 ) ∈ R+ + × Rn ，其中 t 0 = 珋t . 令 k ∶= 0 .步骤 2 如 ‖H( z k ) ‖ ≤ 10 -6 ，则终止程序. 否则，令 αk = min{ 1，t k / | tΨ( z k ) | } ，并由( 4) - ( 5) 计算 βk .步骤 3 令 ( dk L ) t = - t k + βk 珋t . 求( 6) 式的解 ( dk L ) x . 令 dk L = ( ( dk L ) t，( dk L ) x ) 和 dk G = - αkΨ( z k ) + βk 珋z ，其中 珋z = ( 珋t，0…， 0) T ∈ R+ + × Rn .步骤 4 如果 ‖H( z k + dk L ) ‖ ≤ η‖H( z k ) ‖ ，令 z k+1 = z k + dk L ; 否则，记 mk 为满足 Ψ( z k + ρ m dk G ) ≤ Ψ( z k ) - ρ m σαk ( 1 -珋tγ) ‖Ψ( z k ) ‖2 的最小正整数. 令 z k+1 = z k + ρ mkdk G .步骤 5 如果 ‖H( z k ) ‖2 > ‖H( z k ) ‖ ，令 δ = 0. 1 + rand* 0. 1 ; 否则，令 δ = 0. 9 + rand* 0. 1.步骤 6 令 μk = δ‖H( z k ) ‖ + ( 1 - δ) ‖H( z k ) ‖2 和 k ∶= k + 1 . 转到步骤 2.对于算法 1，有如下定理.定理 1 对任何正整数 k ≥ 0 ，若 t k ∈ R+ + 满足 t k ≥ βk 珋t 成立，则算法 1 产生的序列 { z k = ( t k ，xk ) } ，且满足 t k ∈ R+ + 和 t k ≥ βk 珋t .

　　3 收敛性结果

　　本节将对算法 1 的收敛性进行分析，设对任意正整数 k ，均有 ‖Ψ( z k ) ‖ ≠ 0 . 则算法 1 产生无穷序列 { z k } . 下面给出算法 1 的收敛性.定理 2 设 z * 是序列 { z k } 的一个子序列 { z k } k∈K 的极限点. 如果 { z k } k∈K 满足 liminf k∈K，k→∞ t k / tΨ( z k ) > 0 ，则 z * 是Ψ( z) 的一个稳定点.现在，我们对算法 1 的局部收敛性质进行研究. 设 z * ∈ Z* 是 { z k } 的一个聚点. 有以下定理: 定理 3 若对任意正实数 a ，水平集 La ∶= { z ∈ R1 +n | Ψ( z) ≤ a} 有界，则 { z k } 收敛于 z * ，且 dist( z k ，Z* ) 二次收敛于 0.

　　4 数值实验

　　我们用该算法解带约束非线性互补问题以验证算法 1 的实用性. 非线性互补问题的形式如: 求 x* ∈ X = { x ∈ Rn | h( x) ≤ 0} ，使得 x* ≥ 0，P( x* ) ≥ 0，( x* ) T P( x* ) = 0 ，其中 P( x) 和 h( x) 函数如以下各问题例题 1 P( x) = sin( x1 ) + x 2 2 x 3 2 + x1 x3 x 2 3 + x1 x2 - 200 ，h( x) = sin( x1 - x3 ) + e x1 - 3 x 2 2 - [ ] 1 例题 2 P( x) = 1 - x1 + x2 + x3 x1 - 1 x4 - 1 1 + x3 - x  4 ，h( x) = ln( x1 - x3 ) + x3 - 1 arctan( x2 - x4 ) + e x2 - [ ] 3 例题 3 P( x) = 3x 2 1 + 2x1 x2 + 2x 2 2 + x3 + 3x4 - 5 2x 2 1 + x1 + x 2 2 + 10x3 + 2x4 - 2 3x 2 1 + x1 x2 + 2x 2 2 + 2x3 + 9x4 - 9 x 2 1 + 3x 2 2 + 2x 2 3 + 3x4 - 3 ，h( x) = tan( x1 - x3 ) + x1 + e x1 - 5 sin( x2 - x4 ) + x2 + e x2 - [ ] 4 例题 4 P( x) = - x2 + x3 + x4 x1 - 4. 5x3 + 2. 7x4 x2 + 1 5 - x1 - 0. 5x3 + 0. 3x4 x3 + 1 3 - x  1 ，h( x) = ln( 5 - x1 + x3 ) + x1 - 5 x2 - x1 + e x2 + e x4 - [ ] 2 我们首先考虑利用 F - B 函数 φFB ( a，b) = a2 槡 + b 2 - a - b 转化上述例题为形式如( 1) 式的非光滑约束方程组问题，由 F - B 函数的性质可知，当且仅当 a ≥ 0，b ≥ 0，ab = 0 φFB ( a，b) = 0 . 记 F( x) ∶= ( ΨFB ( x1，P1 ( x) ) ，…，ΨFB ( xn，Pn ( x) ) ) T . 易知，F(·) 为非光滑的 L—连续函数，且上述所有例题均可以转化成形如( 1) 的非光滑约束方程组问题. 进一步，可得 F(·) 和 h(·) 的光滑化逼近函数均存在，且满足全部所需条件.我们采用 Matlab 2010b 语言编写该算法的程序，并在惠普台式电脑( pentium( r) dual - core、3. 19GHz、2G) 上运行程序. 所有的数值试验结果见表 1 和表 2. 在表 1 中，“x 0 ”表示迭代初始点，“x* ”表示例题的解. 表 2 给出了算法 1 在求解例题 1 - 4 的最后三步迭代中的相关数据，其中“‖H( z k ) ‖ ”表示 ‖H( z) ‖ 在最后三次迭代点处的值，“‖xk - x* ‖ ”表示算法最后三步产生的迭代点与原例题解的距离，表 2 中的“0”意义为算法所得到的解和原例题真解的距离低于计算机精度，从表 2 中可看出，该算法确实超线性( 局部二次) 收敛.

　　参考文献:

　　[1]Chen C，Mangasarian O L. A class of smoothing functions for nonlinear and mixed complementarity problems [J]. Computational Optimization and Applications，1996，5( 1) : 97 - 138.

　　[2]Facchinei F，Pang J S. Finite - Dimensional Variational Inequalities and Complementarity Problems I - II [M]. New York， Springer - Verlag，2003.

　　[3]Ling C，Ni Q，Qi L，Wu S Y. A new smoothing Newton - type algorithm for semi - infinite programming [J]. Journal of Global Optimization，2010，47( 1) : 133 - 159.

　　[4]Yamashita N，Fukushima M. On the rate of convergence of the Levenberg - Marquardt method[J]. Computing，2001，15: 239 - 249.

　　基于凸组合的列文伯格 - 马夸尔特算法相关论文期刊你还可以了解：《智能算法类论文如何发表》

转载请注明来自：http://www.lunwenhr.com/hrlwfw/hrsklw/11346.html