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

　　關鍵詞：職稱論文投稿,非負約束優化,子空間,共軛梯度法,全局收斂性

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

　　這里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.