求解非負(fù)約束優(yōu)化問題的可行LS共軛梯度法

劉陶文++周蓉

摘要： 結(jié)合子空間思想和LiuStorey （LS）共軛梯度法，提出了求解大規(guī)模非負(fù)約束優(yōu)化問題的可行共軛梯度算法，并分析了算法在Armijo型線性搜索下的全局收斂性. 數(shù)值實(shí)例表明該算法是有效的.

關(guān)鍵詞：非負(fù)約束優(yōu)化； 子空間； 共軛梯度法； 全局收斂性

中圖分類號(hào)：O221.2 文獻(xiàn)標(biāo)識(shí)碼：A

非負(fù)約束優(yōu)化問題廣泛存在于許多學(xué)科及工程應(yīng)用領(lǐng)域中， 如： 非線性回歸分析、金融投資、大地測(cè)量、衛(wèi)星導(dǎo)航等， 并且有關(guān)的數(shù)據(jù)處理是非常龐大的， 呈現(xiàn)的問題通常是大規(guī)模的. 因此， 研究求解這些問題的高效算法具有重要的現(xiàn)實(shí)意義. 非負(fù)約束優(yōu)化問題的一般形式

這里l和u是Rn中的有界向量.許多研究集中于求解大規(guī)模有界約束問題（3）， 人們提出了如譜梯度投影法、有限記憶擬牛頓法和共軛梯度法等有效算法＼[1， 4， 6＼].盡管問題（1）可以看作問題（3）的特殊情形， 但不知這些方法能否經(jīng)過適當(dāng)?shù)男薷谋挥脕砬蠼夥秦?fù)約束問題.

眾所周知，共軛梯度法及其修正形式是求解大規(guī)模無約束問題min f（x）， x∈Rn的有效方法＼[2， 7-8＼].因此， 人們?cè)O(shè)想用共軛梯度法的思想求解約束問題. 文獻(xiàn)＼[6＼]研究了用共軛梯度的思想求解有界約束問題（3）， 通過求解一個(gè)約束子問題來計(jì)算搜索方向， 作者證明了在 Wolfe型線性搜索下所提出的方法是收斂的.然而已有研究表明在該研究上存在許多的困難[5].

在本文中，我們研究用共軛梯度型方法求解非負(fù)約束問題 （1）. 結(jié)合已有求解有界約束問題的子空間思想[4]和求解無約束問題的LiuStorey （LS）共軛梯度法[3]，提出了一個(gè)求解問題（1）的可行LS共軛梯度法， 與文獻(xiàn)＼[6＼]的方法比較， 本文提出的方法的優(yōu)點(diǎn)是無需求解子問題， 并且在Armijo搜索下具有全局收斂性， 節(jié)省大量計(jì)算.

湖南大學(xué)學(xué)報(bào)（自然科學(xué)版）2014年

第7期劉陶文等：求解非負(fù)約束優(yōu)化問題的可行LS共軛梯度法

證由KKT條件（2）以及（10）即可驗(yàn)證定理結(jié)論成立.

證畢

引理1和定理1表明， 當(dāng)dk=0時(shí)， xk必定是問題 （1）的一個(gè)KKT點(diǎn)， 而當(dāng)dk≠0 時(shí)，必有g(shù)Tkdk<0， 即dk≠0是f（x）在xk處的一個(gè)下降可行方向.

2算法結(jié)構(gòu)及其收斂性分析

3數(shù)值實(shí)驗(yàn)

在這一節(jié)，將所提出的算法應(yīng)用于大地測(cè)量中數(shù)據(jù)處理問題[9]. 對(duì)一理想邊坡因地質(zhì)斷層構(gòu)成一可能的滑體， 按地質(zhì)學(xué)知識(shí)， 滑體只能沿底盤向東北方向偏下移動(dòng). 選定三個(gè)基點(diǎn)， 其坐標(biāo)分別為A（500.00， 0， 100.00）， B（0.00， -500.00， 150.00）， C（500.00， 500.00， 200.00）. 在滑體上， 取監(jiān)測(cè)點(diǎn)P （0， 0， 100.00）， 分別在基點(diǎn)A，B，C處用邊前方交會(huì)監(jiān)測(cè)P點(diǎn)的位移（x，y，-z）， AP，BP和CP為3個(gè)觀測(cè)邊， 且有先驗(yàn)信息x，y，z>0. 設(shè)觀測(cè)向量為L∈R3， 則有相應(yīng)的誤差方程：

L+V=（|AP|， |BP|， |CP|）T，

其中V為觀察噪聲向量. 設(shè)A，B，C 3個(gè)邊觀測(cè)的一次觀測(cè)值分別為500.04， 502.52， 714.13. 試估計(jì)P點(diǎn)的位移（x， y， -z）.

當(dāng)P點(diǎn)有位移（x， y， -z）時(shí)， 觀測(cè)向量L的誤差方程為：

L+V=|AP||BP||CP|=

現(xiàn)在用可行LS共軛梯度法來求解問題（16）. 在算法1中， 取初始點(diǎn)（x0， y0， z0）=（1， 1， 1）以及常數(shù)ρ=0.5， σ=0.001， ε=0.01. 算法1在7次迭代后求得P點(diǎn)位移估計(jì)（，，）=（0.022 0，0，-0.053 1）， 顯然這一估計(jì)比文獻(xiàn)＼[9＼]中的線性最小二乘估計(jì)（0.024 6，0，-0.064 0）更接近于實(shí)際的位移（0.004，0.02，-0.005）， 而且可以依據(jù)需要增加迭代次數(shù)提高精度.

參考文獻(xiàn)

[1]BIRGIN E G， MARTINEZ J M， RAYDAN M. Nonmonotone spectral projection gradient methods on convex sets ＼[J＼]. SIAM Journal on Optimization， 2000， 10（1）： 1196-1211.

＼[2＼]DAI Y， YUAN Y. Nonlinear conjugate gradient methods ＼[M＼]. Shanghai： Shanghai Science and Technology Publisher， 2000.

＼[3＼]LIU Y， STOREY C. Efficient generated conjugate gradient algorithms Part 1： Theory ＼[J＼]. Journal of Optimization Theory and Applications， 1991， 69（1）： 129-137.

＼[4＼]NI Q， YUAN Y. A subspace limited memory quasiNewton algorithm for largescale nonlinear bound constrained optimization ＼[J＼]. Mathematics of Computation， 1997， 66（220）： 1509-1520.

＼[5＼]NOCEDAL J. Conjugate gradient methods and nonlinear optimization， In： Linear and nonlinear conjugate gradientRelated method ＼[M＼]. Philadelphia， SIAM Press， 1996， 9-23.

＼[6＼]PYTLAK R. An efficient algorithmfor largescale nonlinear programming problems with simple bounds on the variables ＼[J＼]. SIAM Journal on Optimization， 1998， 8（2）： 532-560.

＼[7＼]ZHANG L， ZHOU W J， LI D H. A descent modified PolakRebièrePolyak conjugate gradient method and its global convergence ＼[J＼]. IMA Journal of Numerical Analysis， 2006， 26（4）： 629-640.

＼[8＼]ZHANG L， JIAN S Y. Further studies on the WeiYaoLiu nonlinear conjugate gradient method ＼[J＼]. Applied Mathematics and Computation， 2013， 219 （14）： 7616-7621.

＼[9＼]宋迎春， 朱建軍， 羅德仁，等. 附非負(fù)約束平差模型的最小二乘估計(jì) ＼[J＼]. 武漢大學(xué)學(xué)報(bào)： 信息科學(xué)版， 2008， 33（9）： 907-909.

SONG Yingcun， ZHU Jianjun， LUO Deren，et al. Leastsquares estimation of nonnegative constrained adjustment model ＼[J＼]. Geomatics and Information Science of Wuhan University：Information and Science， 2008， 33（9）： 907-909 .（In Chinese）

摘要： 結(jié)合子空間思想和LiuStorey （LS）共軛梯度法，提出了求解大規(guī)模非負(fù)約束優(yōu)化問題的可行共軛梯度算法，并分析了算法在Armijo型線性搜索下的全局收斂性. 數(shù)值實(shí)例表明該算法是有效的.

關(guān)鍵詞：非負(fù)約束優(yōu)化； 子空間； 共軛梯度法； 全局收斂性

中圖分類號(hào)：O221.2 文獻(xiàn)標(biāo)識(shí)碼：A

非負(fù)約束優(yōu)化問題廣泛存在于許多學(xué)科及工程應(yīng)用領(lǐng)域中， 如： 非線性回歸分析、金融投資、大地測(cè)量、衛(wèi)星導(dǎo)航等， 并且有關(guān)的數(shù)據(jù)處理是非常龐大的， 呈現(xiàn)的問題通常是大規(guī)模的. 因此， 研究求解這些問題的高效算法具有重要的現(xiàn)實(shí)意義. 非負(fù)約束優(yōu)化問題的一般形式

這里l和u是Rn中的有界向量.許多研究集中于求解大規(guī)模有界約束問題（3）， 人們提出了如譜梯度投影法、有限記憶擬牛頓法和共軛梯度法等有效算法＼[1， 4， 6＼].盡管問題（1）可以看作問題（3）的特殊情形， 但不知這些方法能否經(jīng)過適當(dāng)?shù)男薷谋挥脕砬蠼夥秦?fù)約束問題.

眾所周知，共軛梯度法及其修正形式是求解大規(guī)模無約束問題min f（x）， x∈Rn的有效方法＼[2， 7-8＼].因此， 人們?cè)O(shè)想用共軛梯度法的思想求解約束問題. 文獻(xiàn)＼[6＼]研究了用共軛梯度的思想求解有界約束問題（3）， 通過求解一個(gè)約束子問題來計(jì)算搜索方向， 作者證明了在 Wolfe型線性搜索下所提出的方法是收斂的.然而已有研究表明在該研究上存在許多的困難[5].

在本文中，我們研究用共軛梯度型方法求解非負(fù)約束問題 （1）. 結(jié)合已有求解有界約束問題的子空間思想[4]和求解無約束問題的LiuStorey （LS）共軛梯度法[3]，提出了一個(gè)求解問題（1）的可行LS共軛梯度法， 與文獻(xiàn)＼[6＼]的方法比較， 本文提出的方法的優(yōu)點(diǎn)是無需求解子問題， 并且在Armijo搜索下具有全局收斂性， 節(jié)省大量計(jì)算.

湖南大學(xué)學(xué)報(bào)（自然科學(xué)版）2014年

第7期劉陶文等：求解非負(fù)約束優(yōu)化問題的可行LS共軛梯度法

證由KKT條件（2）以及（10）即可驗(yàn)證定理結(jié)論成立.

證畢

引理1和定理1表明， 當(dāng)dk=0時(shí)， xk必定是問題 （1）的一個(gè)KKT點(diǎn)， 而當(dāng)dk≠0 時(shí)，必有g(shù)Tkdk<0， 即dk≠0是f（x）在xk處的一個(gè)下降可行方向.

2算法結(jié)構(gòu)及其收斂性分析

3數(shù)值實(shí)驗(yàn)

在這一節(jié)，將所提出的算法應(yīng)用于大地測(cè)量中數(shù)據(jù)處理問題[9]. 對(duì)一理想邊坡因地質(zhì)斷層構(gòu)成一可能的滑體， 按地質(zhì)學(xué)知識(shí)， 滑體只能沿底盤向東北方向偏下移動(dòng). 選定三個(gè)基點(diǎn)， 其坐標(biāo)分別為A（500.00， 0， 100.00）， B（0.00， -500.00， 150.00）， C（500.00， 500.00， 200.00）. 在滑體上， 取監(jiān)測(cè)點(diǎn)P （0， 0， 100.00）， 分別在基點(diǎn)A，B，C處用邊前方交會(huì)監(jiān)測(cè)P點(diǎn)的位移（x，y，-z）， AP，BP和CP為3個(gè)觀測(cè)邊， 且有先驗(yàn)信息x，y，z>0. 設(shè)觀測(cè)向量為L∈R3， 則有相應(yīng)的誤差方程：

L+V=（|AP|， |BP|， |CP|）T，

其中V為觀察噪聲向量. 設(shè)A，B，C 3個(gè)邊觀測(cè)的一次觀測(cè)值分別為500.04， 502.52， 714.13. 試估計(jì)P點(diǎn)的位移（x， y， -z）.

當(dāng)P點(diǎn)有位移（x， y， -z）時(shí)， 觀測(cè)向量L的誤差方程為：

L+V=|AP||BP||CP|=

現(xiàn)在用可行LS共軛梯度法來求解問題（16）. 在算法1中， 取初始點(diǎn)（x0， y0， z0）=（1， 1， 1）以及常數(shù)ρ=0.5， σ=0.001， ε=0.01. 算法1在7次迭代后求得P點(diǎn)位移估計(jì)（，，）=（0.022 0，0，-0.053 1）， 顯然這一估計(jì)比文獻(xiàn)＼[9＼]中的線性最小二乘估計(jì)（0.024 6，0，-0.064 0）更接近于實(shí)際的位移（0.004，0.02，-0.005）， 而且可以依據(jù)需要增加迭代次數(shù)提高精度.

參考文獻(xiàn)

[1]BIRGIN E G， MARTINEZ J M， RAYDAN M. Nonmonotone spectral projection gradient methods on convex sets ＼[J＼]. SIAM Journal on Optimization， 2000， 10（1）： 1196-1211.

＼[2＼]DAI Y， YUAN Y. Nonlinear conjugate gradient methods ＼[M＼]. Shanghai： Shanghai Science and Technology Publisher， 2000.

＼[3＼]LIU Y， STOREY C. Efficient generated conjugate gradient algorithms Part 1： Theory ＼[J＼]. Journal of Optimization Theory and Applications， 1991， 69（1）： 129-137.

＼[4＼]NI Q， YUAN Y. A subspace limited memory quasiNewton algorithm for largescale nonlinear bound constrained optimization ＼[J＼]. Mathematics of Computation， 1997， 66（220）： 1509-1520.

＼[5＼]NOCEDAL J. Conjugate gradient methods and nonlinear optimization， In： Linear and nonlinear conjugate gradientRelated method ＼[M＼]. Philadelphia， SIAM Press， 1996， 9-23.

＼[6＼]PYTLAK R. An efficient algorithmfor largescale nonlinear programming problems with simple bounds on the variables ＼[J＼]. SIAM Journal on Optimization， 1998， 8（2）： 532-560.

＼[7＼]ZHANG L， ZHOU W J， LI D H. A descent modified PolakRebièrePolyak conjugate gradient method and its global convergence ＼[J＼]. IMA Journal of Numerical Analysis， 2006， 26（4）： 629-640.

＼[8＼]ZHANG L， JIAN S Y. Further studies on the WeiYaoLiu nonlinear conjugate gradient method ＼[J＼]. Applied Mathematics and Computation， 2013， 219 （14）： 7616-7621.

＼[9＼]宋迎春， 朱建軍， 羅德仁，等. 附非負(fù)約束平差模型的最小二乘估計(jì) ＼[J＼]. 武漢大學(xué)學(xué)報(bào)： 信息科學(xué)版， 2008， 33（9）： 907-909.

SONG Yingcun， ZHU Jianjun， LUO Deren，et al. Leastsquares estimation of nonnegative constrained adjustment model ＼[J＼]. Geomatics and Information Science of Wuhan University：Information and Science， 2008， 33（9）： 907-909 .（In Chinese）

摘要： 結(jié)合子空間思想和LiuStorey （LS）共軛梯度法，提出了求解大規(guī)模非負(fù)約束優(yōu)化問題的可行共軛梯度算法，并分析了算法在Armijo型線性搜索下的全局收斂性. 數(shù)值實(shí)例表明該算法是有效的.

關(guān)鍵詞：非負(fù)約束優(yōu)化； 子空間； 共軛梯度法； 全局收斂性

中圖分類號(hào)：O221.2 文獻(xiàn)標(biāo)識(shí)碼：A

非負(fù)約束優(yōu)化問題廣泛存在于許多學(xué)科及工程應(yīng)用領(lǐng)域中， 如： 非線性回歸分析、金融投資、大地測(cè)量、衛(wèi)星導(dǎo)航等， 并且有關(guān)的數(shù)據(jù)處理是非常龐大的， 呈現(xiàn)的問題通常是大規(guī)模的. 因此， 研究求解這些問題的高效算法具有重要的現(xiàn)實(shí)意義. 非負(fù)約束優(yōu)化問題的一般形式

這里l和u是Rn中的有界向量.許多研究集中于求解大規(guī)模有界約束問題（3）， 人們提出了如譜梯度投影法、有限記憶擬牛頓法和共軛梯度法等有效算法＼[1， 4， 6＼].盡管問題（1）可以看作問題（3）的特殊情形， 但不知這些方法能否經(jīng)過適當(dāng)?shù)男薷谋挥脕砬蠼夥秦?fù)約束問題.

眾所周知，共軛梯度法及其修正形式是求解大規(guī)模無約束問題min f（x）， x∈Rn的有效方法＼[2， 7-8＼].因此， 人們?cè)O(shè)想用共軛梯度法的思想求解約束問題. 文獻(xiàn)＼[6＼]研究了用共軛梯度的思想求解有界約束問題（3）， 通過求解一個(gè)約束子問題來計(jì)算搜索方向， 作者證明了在 Wolfe型線性搜索下所提出的方法是收斂的.然而已有研究表明在該研究上存在許多的困難[5].

在本文中，我們研究用共軛梯度型方法求解非負(fù)約束問題 （1）. 結(jié)合已有求解有界約束問題的子空間思想[4]和求解無約束問題的LiuStorey （LS）共軛梯度法[3]，提出了一個(gè)求解問題（1）的可行LS共軛梯度法， 與文獻(xiàn)＼[6＼]的方法比較， 本文提出的方法的優(yōu)點(diǎn)是無需求解子問題， 并且在Armijo搜索下具有全局收斂性， 節(jié)省大量計(jì)算.

湖南大學(xué)學(xué)報(bào)（自然科學(xué)版）2014年

第7期劉陶文等：求解非負(fù)約束優(yōu)化問題的可行LS共軛梯度法

證由KKT條件（2）以及（10）即可驗(yàn)證定理結(jié)論成立.

證畢

引理1和定理1表明， 當(dāng)dk=0時(shí)， xk必定是問題 （1）的一個(gè)KKT點(diǎn)， 而當(dāng)dk≠0 時(shí)，必有g(shù)Tkdk<0， 即dk≠0是f（x）在xk處的一個(gè)下降可行方向.

2算法結(jié)構(gòu)及其收斂性分析

3數(shù)值實(shí)驗(yàn)

在這一節(jié)，將所提出的算法應(yīng)用于大地測(cè)量中數(shù)據(jù)處理問題[9]. 對(duì)一理想邊坡因地質(zhì)斷層構(gòu)成一可能的滑體， 按地質(zhì)學(xué)知識(shí)， 滑體只能沿底盤向東北方向偏下移動(dòng). 選定三個(gè)基點(diǎn)， 其坐標(biāo)分別為A（500.00， 0， 100.00）， B（0.00， -500.00， 150.00）， C（500.00， 500.00， 200.00）. 在滑體上， 取監(jiān)測(cè)點(diǎn)P （0， 0， 100.00）， 分別在基點(diǎn)A，B，C處用邊前方交會(huì)監(jiān)測(cè)P點(diǎn)的位移（x，y，-z）， AP，BP和CP為3個(gè)觀測(cè)邊， 且有先驗(yàn)信息x，y，z>0. 設(shè)觀測(cè)向量為L∈R3， 則有相應(yīng)的誤差方程：

L+V=（|AP|， |BP|， |CP|）T，

其中V為觀察噪聲向量. 設(shè)A，B，C 3個(gè)邊觀測(cè)的一次觀測(cè)值分別為500.04， 502.52， 714.13. 試估計(jì)P點(diǎn)的位移（x， y， -z）.

當(dāng)P點(diǎn)有位移（x， y， -z）時(shí)， 觀測(cè)向量L的誤差方程為：

L+V=|AP||BP||CP|=

現(xiàn)在用可行LS共軛梯度法來求解問題（16）. 在算法1中， 取初始點(diǎn)（x0， y0， z0）=（1， 1， 1）以及常數(shù)ρ=0.5， σ=0.001， ε=0.01. 算法1在7次迭代后求得P點(diǎn)位移估計(jì)（，，）=（0.022 0，0，-0.053 1）， 顯然這一估計(jì)比文獻(xiàn)＼[9＼]中的線性最小二乘估計(jì)（0.024 6，0，-0.064 0）更接近于實(shí)際的位移（0.004，0.02，-0.005）， 而且可以依據(jù)需要增加迭代次數(shù)提高精度.

參考文獻(xiàn)

[1]BIRGIN E G， MARTINEZ J M， RAYDAN M. Nonmonotone spectral projection gradient methods on convex sets ＼[J＼]. SIAM Journal on Optimization， 2000， 10（1）： 1196-1211.

＼[2＼]DAI Y， YUAN Y. Nonlinear conjugate gradient methods ＼[M＼]. Shanghai： Shanghai Science and Technology Publisher， 2000.

＼[3＼]LIU Y， STOREY C. Efficient generated conjugate gradient algorithms Part 1： Theory ＼[J＼]. Journal of Optimization Theory and Applications， 1991， 69（1）： 129-137.

＼[4＼]NI Q， YUAN Y. A subspace limited memory quasiNewton algorithm for largescale nonlinear bound constrained optimization ＼[J＼]. Mathematics of Computation， 1997， 66（220）： 1509-1520.

＼[5＼]NOCEDAL J. Conjugate gradient methods and nonlinear optimization， In： Linear and nonlinear conjugate gradientRelated method ＼[M＼]. Philadelphia， SIAM Press， 1996， 9-23.

＼[6＼]PYTLAK R. An efficient algorithmfor largescale nonlinear programming problems with simple bounds on the variables ＼[J＼]. SIAM Journal on Optimization， 1998， 8（2）： 532-560.

＼[7＼]ZHANG L， ZHOU W J， LI D H. A descent modified PolakRebièrePolyak conjugate gradient method and its global convergence ＼[J＼]. IMA Journal of Numerical Analysis， 2006， 26（4）： 629-640.

＼[8＼]ZHANG L， JIAN S Y. Further studies on the WeiYaoLiu nonlinear conjugate gradient method ＼[J＼]. Applied Mathematics and Computation， 2013， 219 （14）： 7616-7621.

＼[9＼]宋迎春， 朱建軍， 羅德仁，等. 附非負(fù)約束平差模型的最小二乘估計(jì) ＼[J＼]. 武漢大學(xué)學(xué)報(bào)： 信息科學(xué)版， 2008， 33（9）： 907-909.

SONG Yingcun， ZHU Jianjun， LUO Deren，et al. Leastsquares estimation of nonnegative constrained adjustment model ＼[J＼]. Geomatics and Information Science of Wuhan University：Information and Science， 2008， 33（9）： 907-909 .（In Chinese）