一個解非光滑方程組的Levenberg-Marquardt算法*

鄭玲愛， 凌 晨

(杭州電子科技大學 運籌與控制研究所，浙江 杭州 310018)

一個解非光滑方程組的Levenberg-Marquardt算法*

鄭玲愛， 凌 晨

(杭州電子科技大學 運籌與控制研究所，浙江 杭州 310018)

給出了一個求解非光滑約束方程組的Levenberg-Marquardt算法，每一步迭代中只需求解一個嚴格凸的二次規劃問題.首先，利用松弛變量的絕對值函數將原問題轉化成一個無約束方程組；然后，結合光滑化技術設計Levenberg-Marquardt算法.此算法具有全局收斂性，并且在弱于非奇異性的局部誤差界條件下，具有局部二次收斂性質.初步的數值試驗結果表明，此算法實際計算效果良好.

約束方程組；光滑化技術；Levenberg-Marquardt算法；強半光滑性；收斂性

0 引 言

研究如下非光滑約束方程組的數值求解問題:

式(1)中:X={x∈Rn|h(x)≤0};F:X→Rp和h:Rn→Rm均在某一包含X的開集上局部Lipschitz連續.約束方程組有廣泛應用，許多重要問題(例如非線性互補、變分不等式、半無限規劃)都可以轉化成形如式(1)的問題[1-3].傳統的Levenberg-Marquardt算法是求解光滑(即連續可微)無約束方程組的經典、有效方法之一.文獻[4-5]已經證明，在局部誤差界條件下，Levenberg-Marquardt算法具有局部二次收斂性質.求解約束方程組的一類典型方法是將問題轉化為一個約束規劃問題，并運用標準的優化算法解之[6-7].特別地，若F(5)非光滑但‖F(5)‖2光滑，且可行域X可表示為盒子約束，則已有一些行之有效的算法[8].然而，因問題(1)中X和相關效益函數都有可能為非凸，函數‖F(5)‖2和h(5)均不光滑，方程個數與未知量個數也未必相等，所以許多算法不能直接被應用.

本文給出一個求解問題(1)的光滑化Levenberg-Marquardt算法.此算法在每一步迭代中只需求解一個嚴格凸的二次規劃問題,不僅具有全局收斂性質，而且在弱于非奇異性的局部誤差界條件下具有局部二次收斂性.數值試驗結果顯示該算法效果良好.

1 光滑化函數

利用松弛變量的絕對值函數將問題(1)轉化成一個無約束方程組，即

式(2)中:y=(x,t)∈Rn×Rm;|t|=(|t1|,|t2|,…,|tm|)T.顯然，當且僅當方程(1)的解集X*≠?時，方程(2)的解集Y*≠?.進一步，若y*=(x*,t*)是方程(2)的解，則x*是方程(1)的解.為克服函數F(5),h(5)和|5|的非光滑性給算法設計帶來的困難，特引進它們的光滑化逼近函數，并討論相關的性質.

其解集記為Z*.關于問題(2)，給出如下局部誤差界條件:

針對函數H，易證以下命題成立:

命題1設條件1成立,則對任意z*∈Z*，存在常數c1>0和鄰域N(z*,δ1):={z∈R1+n+m| ‖z-z*‖≤δ1,ε≥0}，使得對任意z∈N(z*,δ1)，有

2 一個光滑化Levenberg-Marquardt算法

進一步易知，若zk不是Ψ(5)的穩定點，則相應的拉格朗日乘子αk必定唯一.

算法1：

第1步：若zk滿足終止條件，則停止.否則，由式(7)和式(8)計算βk.

第2步：解方程(9)，得dk=(dkε,dkx,dkt)T.

第3步：若‖H(zk+dk)‖≤γ‖H(zk)‖，則令zk+1:=zk+dk；否則，記mk為滿足

的最小非負整數，令zk+1:=zk+ρmkdk.

第4步：令μk+1=‖H(zk+1)‖τ和k:=k+1，并轉至第1步.

關于算法1，有如下命題:

證明 由命題2和3即可證得.證畢.

3 收斂性分析

為確保算法1具有全局收斂性，給出如下條件：

條件2方程組(1)的解集X*非空有界.

注2由h(5)的連續性易知，在條件2下，Z*為非空有界.

條件3由算法1產生的序列{zk=(εk,xk,tk)}滿足

∞.

定理2設{zk}是算法1產生的無窮序列.若條件3成立，則{zk}的任意聚點都是Ψ(z)的穩定點.

現在研究由算法1所產生點列{zk}的局部收斂性質.進一步給出如下條件:

條件4對任意實數α>0，Ψ(5)的水平集La:={z∈R1+n+m|Ψ(z)≤a}有界.

易見，若條件4成立，則條件2成立.

4 數值試驗

應用算法1求解如下帶“約束”的非線性互補問題.

例1求x*∈X={x∈R4|h(x)≤0}，使得x*≥0，P(x*)≥0,(x*)TP(x*)=0,其中

.

例2求x*∈X={x∈R4|h(x)≤0}，使得x*≥0，P(x*)≥0,(x*)TP(x*)=0,其中

.

例3求x*∈X={x∈R4|h(x)≤0}，使得x*≥0，P(x*)≥0,(x*)TP(x*)=0,其中

.

例4求x*∈X={x∈R5|h(x)≤0}，使得x*≥0，P(x*)≥0,(x*)TP(x*)=0,其中

表1 例1～例4的數值試驗結果

表2 例1～例4最后3步迭代的相關數據

[1]Chen Chunhui,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:1-124.

[3]Ling Chen,Ni Qin,Qi Liqun,et al.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(suppl):239-249.

[5]Dan H,Yamashita N,Fukushima M.Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions[J].Optimization Methods and Software,2002,17(4):605-626.

[6]Tong X J,Qi L.On the convergence of a trust region method for solving constrained nonlinear equations with degenerate solution[J].Journal of Optimization and Theory Applications,2004,123(1):187-211.

[7]Wang Tao,Monteiro R D C,Pang Jongshi.An interior point potential reduction method for constrained equations[J].Mathematical Programming,1996,74(2):159-195.

[8]Sun Defeng,Womersley R S,Qi Houdou.A feasible semismooth asymptotically Newton method for mixed complementarity problems[J].Mathematical Programming,2002,94(2):167-187.

[9]Clarke F H.Optimization and nonsmooth analysis[M].New York:John Wiley and Sons,1983:69-75.

(責任編輯 陶立方)

ALevenberg-Marquardtalgorithmforsolvingnonsmoothequations

ZHENG Ling′ai， LING Chen

(InstituteofOperationalResearchandCybernetics,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

A new smoothing Levenberg-Marquardt algorithm was presented for solving nonsmooth constrained system of equations, which only needed to solve one strictly convex quadratic programming at each iteration. First, the original problem was converted into an unconstrained system of equations by using the absolute value function of the slack variables, then a Levenberg-Marquardt algorithm was designed by combining the smoothing technique. The presented algorithm converged globally, and converged locally quadratically under an error bound assumption which was much weaker than the standard nonsingularity condition. Some numerical results for the presented method indicated that the algorithm performed quite well in practice.

constrained equations; smoothing technique; Levenberg-Marquardt algorithm; strong semi-smoothness; convergence

O241;O221

A

1001-5051(2013)04-0417-05

2013-06-16

國家自然科學基金資助項目(10871168;11171083)；浙江省自然科學基金資助項目(Y6100366)

鄭玲愛(1989-)，女，浙江衢州人，碩士研究生.研究方向：非線性規劃.