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

鄭玲愛， 凌 晨

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

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

鄭玲愛， 凌 晨

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

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

約束方程組；光滑化技術(shù)；Levenberg-Marquardt算法；強(qiáng)半光滑性；收斂性

0 引 言

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

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

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

1 光滑化函數(shù)

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

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

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

針對函數(shù)H，易證以下命題成立:

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

2 一個(gè)光滑化Levenberg-Marquardt算法

進(jìn)一步易知，若zk不是Ψ(5)的穩(wěn)定點(diǎn)，則相應(yīng)的拉格朗日乘子αk必定唯一.

算法1：

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

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

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

的最小非負(fù)整數(shù)，令zk+1:=zk+ρmkdk.

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

關(guān)于算法1，有如下命題:

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

3 收斂性分析

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

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

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

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

∞.

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

現(xiàn)在研究由算法1所產(chǎn)生點(diǎn)列{zk}的局部收斂性質(zhì).進(jìn)一步給出如下條件:

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

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

4 數(shù)值試驗(yàn)

應(yīng)用算法1求解如下帶“約束”的非線性互補(bǔ)問題.

例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的數(shù)值試驗(yàn)結(jié)果

表2 例1～例4最后3步迭代的相關(guān)數(shù)據(jù)

[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.

(責(zé)任編輯 陶立方)

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

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

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