求解非負約束優化問題的可行LS共軛梯度法

劉陶文++周蓉

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

關鍵詞：非負約束優化； 子空間； 共軛梯度法； 全局收斂性

中圖分類號：O221.2 文獻標識碼：A

非負約束優化問題廣泛存在于許多學科及工程應用領域中， 如： 非線性回歸分析、金融投資、大地測量、衛星導航等， 并且有關的數據處理是非常龐大的， 呈現的問題通常是大規模的. 因此， 研究求解這些問題的高效算法具有重要的現實意義. 非負約束優化問題的一般形式

這里l和u是Rn中的有界向量.許多研究集中于求解大規模有界約束問題（3）， 人們提出了如譜梯度投影法、有限記憶擬牛頓法和共軛梯度法等有效算法＼[1， 4， 6＼].盡管問題（1）可以看作問題（3）的特殊情形， 但不知這些方法能否經過適當的修改被用來求解非負約束問題.

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

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

湖南大學學報（自然科學版）2014年

第7期劉陶文等：求解非負約束優化問題的可行LS共軛梯度法

證由KKT條件（2）以及（10）即可驗證定理結論成立.

證畢

引理1和定理1表明， 當dk=0時， xk必定是問題 （1）的一個KKT點， 而當dk≠0 時，必有gTkdk<0， 即dk≠0是f（x）在xk處的一個下降可行方向.

2算法結構及其收斂性分析

3數值實驗

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

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

其中V為觀察噪聲向量. 設A，B，C 3個邊觀測的一次觀測值分別為500.04， 502.52， 714.13. 試估計P點的位移（x， y， -z）.

當P點有位移（x， y， -z）時， 觀測向量L的誤差方程為：

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

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

參考文獻

[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＼]宋迎春， 朱建軍， 羅德仁，等. 附非負約束平差模型的最小二乘估計 ＼[J＼]. 武漢大學學報： 信息科學版， 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）

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

關鍵詞：非負約束優化； 子空間； 共軛梯度法； 全局收斂性

中圖分類號：O221.2 文獻標識碼：A

非負約束優化問題廣泛存在于許多學科及工程應用領域中， 如： 非線性回歸分析、金融投資、大地測量、衛星導航等， 并且有關的數據處理是非常龐大的， 呈現的問題通常是大規模的. 因此， 研究求解這些問題的高效算法具有重要的現實意義. 非負約束優化問題的一般形式

這里l和u是Rn中的有界向量.許多研究集中于求解大規模有界約束問題（3）， 人們提出了如譜梯度投影法、有限記憶擬牛頓法和共軛梯度法等有效算法＼[1， 4， 6＼].盡管問題（1）可以看作問題（3）的特殊情形， 但不知這些方法能否經過適當的修改被用來求解非負約束問題.

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

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

湖南大學學報（自然科學版）2014年

第7期劉陶文等：求解非負約束優化問題的可行LS共軛梯度法

證由KKT條件（2）以及（10）即可驗證定理結論成立.

證畢

引理1和定理1表明， 當dk=0時， xk必定是問題 （1）的一個KKT點， 而當dk≠0 時，必有gTkdk<0， 即dk≠0是f（x）在xk處的一個下降可行方向.

2算法結構及其收斂性分析

3數值實驗

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

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

其中V為觀察噪聲向量. 設A，B，C 3個邊觀測的一次觀測值分別為500.04， 502.52， 714.13. 試估計P點的位移（x， y， -z）.

當P點有位移（x， y， -z）時， 觀測向量L的誤差方程為：

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

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

參考文獻

[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＼]宋迎春， 朱建軍， 羅德仁，等. 附非負約束平差模型的最小二乘估計 ＼[J＼]. 武漢大學學報： 信息科學版， 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）

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

關鍵詞：非負約束優化； 子空間； 共軛梯度法； 全局收斂性

中圖分類號：O221.2 文獻標識碼：A

非負約束優化問題廣泛存在于許多學科及工程應用領域中， 如： 非線性回歸分析、金融投資、大地測量、衛星導航等， 并且有關的數據處理是非常龐大的， 呈現的問題通常是大規模的. 因此， 研究求解這些問題的高效算法具有重要的現實意義. 非負約束優化問題的一般形式

這里l和u是Rn中的有界向量.許多研究集中于求解大規模有界約束問題（3）， 人們提出了如譜梯度投影法、有限記憶擬牛頓法和共軛梯度法等有效算法＼[1， 4， 6＼].盡管問題（1）可以看作問題（3）的特殊情形， 但不知這些方法能否經過適當的修改被用來求解非負約束問題.

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

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

湖南大學學報（自然科學版）2014年

第7期劉陶文等：求解非負約束優化問題的可行LS共軛梯度法

證由KKT條件（2）以及（10）即可驗證定理結論成立.

證畢

引理1和定理1表明， 當dk=0時， xk必定是問題 （1）的一個KKT點， 而當dk≠0 時，必有gTkdk<0， 即dk≠0是f（x）在xk處的一個下降可行方向.

2算法結構及其收斂性分析

3數值實驗

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

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

其中V為觀察噪聲向量. 設A，B，C 3個邊觀測的一次觀測值分別為500.04， 502.52， 714.13. 試估計P點的位移（x， y， -z）.

當P點有位移（x， y， -z）時， 觀測向量L的誤差方程為：

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

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

參考文獻

[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＼]宋迎春， 朱建軍， 羅德仁，等. 附非負約束平差模型的最小二乘估計 ＼[J＼]. 武漢大學學報： 信息科學版， 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）