摘要： 结合子空间思想和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.
