求解约束最优化问题KKT系统的BFGS方法

求解约束最优化问题KKT系统的BFGS方法（精选3篇）

求解约束最优化问题KKT系统的BFGS方法 篇1

求解约束最优化问题KKT系统的BFGS方法

利用Fischer-Burmeister函数,将约束最优化问题KKT系统转化为等价的`非光滑方程组,利用广义导数,给出一个求解该非光滑方程组的BFGS方法.其子问题是一个系数阵为正定对称阵的线性方程组.为保证全局收敛性,我们引进了一个适当的线性搜索,它使得效益函数近似下降.在适当的条件下,我们证明了算法是适定的,并具有全局收敛性和超线性收敛性.

作 者：张继伟 王仙桃 作者单位：湖南大学,数学与计量经济学院,湖南,长沙,410082刊 名：湖南大学学报(自然科学版) ISTIC EI PKU英文刊名：JOURNAL OF HUNAN UNIVERSITY(NATURAL SCIENCES)年，卷(期)：30(3)分类号：O221.1关键词：KKT系统 BFGS方法 全局收敛 超线性收敛 广义导数 半光滑

求解约束最优化问题KKT系统的BFGS方法 篇2

全局优化问题在科学计算、工程技术、经济管理等领域得到越来越广泛的关注和应用, 近些年来, 人们相继提出一些求解全局优化问题的算法, 填充函数法属于其中的确定型算法, 最早由Ge[1]提出, 用来求解无约束多极值函数的全局极小点。这种算法的关键是构造一个称为填充函数的辅助函数, 其基本思想是借助辅助函数, 从目标函数的当前局部极小点找到另一个目标函数值更小的局部极小点, 直至找到全局最小点为止。

Ge之后, 不少学者相继提出了不少性质良好的填充函数, 但基本上都是针对无约束优化问题的, 对于求解约束优化问题的填充函数虽有讨论, 如文献[2,3,4,5,6,7], 但都有各自不同程度的缺陷。本文在无强制性条件下给出了一类性质良好的求解带一般约束优化问题的单参数填充函数, 并讨论了其填充性质。

1 基本概念

考虑带约束全局优化问题 (P) : min f (x) , s.t.x∈S={x∈Rn|gi (x) ≤0, i∈Γ}, 其中f (x) , gi (x) , i∈Γ:Rn→R是连续可微函数, Γ={1, 2, …, m}是下标集。对上述问题假设如下。

假设1 问题 (P) 的不同局部极小点的个数可以是无限的, 但不同局部极小值个数是有限的。

假设2 用L (p) 表示问题 (P) 的局部极小点集合, 若x*是问题 (P) 的局部极小点, 则Lx*={x∈L (p) |f (x) =f (x*) }是一个有界闭集, 且问题 (P) 存在全局极小点。

注:在很多全局优化的实际问题中, f (x) 的强制性条件不一定满足, 因此这里对问题 (P) 的假设中没有考虑到目标函数f (x) 的强制性条件。下面针对问题 (P) 给出有约束优化问题的填充函数定义。

定义1[4] 函数p (x, x*, a) 称为f (x) 在局部极小点x*处的填充函数, 如果它满足:

(1) 在Rn空间中, x*是p (x, x*, a) 的严格局部极大点;

(2) 对x∈S1∩S且x≠x*或x∈Rn＼S有∇p (x, x*, a) ≠0, 这里S1={x∈Rn|f (x) ≥f (x*) };

(3) 如果x*不是全局极小点, 那么p (x, x*, a) 一定在S2={x∈S|f (x) <f (x*) }上有局部极小点。

以上定义的填充函数的意义为:对于有约束最优化问题, 首先要考虑的就是求出来的点是否可行。由条件 (2) 知, 要找的点一定在可行域内;其次, 对于全局最优化问题的填充函数法, 关心的是比当前局部极小点更好的那些点, 由条件 (2) 知, 要找的点一定不会再比当前局部极小点差的水平集上达到。若x*是局部极小点但不是全局极小点, 由定义中的条件 (1) 和条件 (3) , 则可以从x*的邻域中的任意一点出发, 用求无约束最优化问题的极小化方法极小化填充函数, 总能找到填充函数的局部极小点x*0, 由条件 (3) 知, f (x*0) <f (x*) , 再由条件 (2) , 对x∈S1∩S且x≠x*或x∈Rn＼S有∇p (x, x*, a) ≠0, 得知x*0∈S。

2 填充函数及其性质

针对问题 (P) , 设x*是当前局部极小点, 构造单参数填充函数如下。

1) p (x, x*, a) =-φ (1+‖x-x*‖3) +amin [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]。

其中a>0是参数, 函数φ (t) 满足:1) φ (0) =0, 2) φ′ (t) >0, 这样的函数有$1-\text{e}{}^{-t},\arctan t,\frac{t}{1+t}$等。

当参数a>0充分大时, 下面的几个定理表明p (x, x*, a) 是满足定义1的一类填充函数。

定理1 对任意a>0, x*是p (x, x*, a) 的严格局部极大点。

证明 因为x*是f (x) 的局部极小点, 则存在它的一个邻域N (x*, δ) (δ>0) , 使得∀x∈N (x*, δ) ∩S, 有f (x) ≥f (x*) , gi (x) ≤0, i∈Γ。

下面分两种情况来证明对∀x∈N (x*, δ) , p (x, x*, a) <p (x*, x*, a) 成立。

(1) 当x∈N (x*, δ) ∩S, x≠x*时, 由于f (x) ≥f (x*) , 则有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0于是p (x, x*, a) =-φ (1+‖x-x*‖3) <-φ (1) =p (x*, x*, a) 。

(2) 当x∈N (x*, δ) ∩ (Rn＼S) 时, 则至少存在一个指标i0∈Γ, 使得gi0 (x) >0, 故min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0, 于是同 (1) 有结论成立。

综上, p (x, x*, a) <p (x*, x*, a) 对于∀x∈N (x*, δ) 都成立。因此, x*是p (x, x*, a) 的严格局部极大点。

定理2 若x*是f (x) 的局部极小点, 则p (x, x*, a) 在 (S∩S1) ＼{x*}或Rn＼S上有∇p (x, x*, a) ≠0成立。

证明 易得对∀x∈S∩S1或Rn＼S都有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0, 此时, p (x, x*, a) =-φ (1+‖x-x*‖3) , 显然∇p (x, x*, a) ≠0。

定理3 若x*是f (x) 的局部极小点, 但不是f (x) 的全局极小点, 且cl (int S) =cl (S) , 则当a>0充分大时, 一定存在x*0∈S2, 使得x*0是p (x, x*, a) 的局部极小点。

证明 因为x*是f (x) 的局部极小点但非全局极小点, 则存在f (x) 的另一个局部极小点x*1, 使得f (x*1) <f (x*) , gi (x*1) ≤0, i∈Γ。

由于f (x) , gi (x) , i∈Γ是连续函数, 且cl (int S) =cl (S) , 则一定存在x*2∈Rn, 使得f (x*2) <f (x*) , gi (x*2) <0, 故有

p (x*2, x*, a) =-φ (1+‖x*2-x*‖3) +amax {f (x*2) -f (x*) , gi (x*2) , i∈Γ}。

显然Lx*1⊂S, x*2∈int S∩S2。

另一方面, 对∀x∈∂S, 至少存在一个指标i1∈Γ, 使得gi1 (x) =0, 于是当x∈∂S时有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ]=0, 从而p (x, x*, a) =-φ (1+‖x-x*‖3) 。

所以, 当a>0充分大时, 对∀x∈∂S, 有p (x*2, x*, a) <p (x, x*, a) 。显然, S＼∂S是开集, 于是当a>0充分大时存在一点x*0∈S＼∂S使得

$\begin{array}{l}\underset{x\in S}{{\displaystyle \min }}p(x‚x{}^{*}‚a)=\underset{x\in S\partial S}{{\displaystyle \min }}p(x‚x{}^{*}‚a)=\\ p(x{}_0^{*}‚x{}^{*}‚a)\le p(x{}_2^{*}‚x{}^{*}‚a)‚\end{array}$

故x*0∈int S, 且f (x*0) <f (x*) 。

定理4 若x*是f (x) 的全局极小点, 则对∀x∈S, x≠x*都有p (x, x*, a) <0。

证明 由于x*是f (x) 的全局极小点, 则对所有的x∈S都有f (x) ≥f (x*) 成立。因此, 由定理1, 对∀x∈S, x≠x*有p (x, x*, a) <0成立。

定理5 任给x1, x2∈Rn, 若f (x1) ≥f (x*) , f (x2) ≥f (x*) , 则‖x2-x*‖>‖x1-x*‖当且仅当p (x2, x*, a) <p (x1, x*, a) 。

证明 若f (x1) ≥f (x*) , f (x2) ≥f (x*) , 则min [0, max (f (xj) -f (x*) , gi (x) , i=∈Γ) ]=0, j=1, 2, 此时有p (xj, x*, a) =-φ (1+‖xj-x*‖3) , 显然有p (x2, x*, a) <p (x1, x*, a) , 反之亦然。

定理6 如果x1, x2∈Rn并且满足f (x1) ≥f (x*) ≥f (x2) 和‖x2-x*‖>‖x1-x*‖, 则p (x2, x*, a) <p (x1, x*, a) 。

证明 由条件, p (x2, x*, a) =-φ (1+‖x2-x*‖3) +amax [f (x2) -f (x*) , gi (x2) , i∈Γ]。

且p (x1, x*, a) =-φ (1+‖x1-x*‖3) , 显然结论是成立的。

注:定理4-定理6说明目标函数当前的极小点x*被淘汰, 而新的填充函数的极小点将会被找到, 并且目标函数在这个点的函数值不比当前极小点处的函数值大。这也正是本文的填充函数所具有的良好性质之一。

3 算法和数值实验

3.1 算法

根据上述理论, 参考文献[7]给出下述算法。

(0) 初始步:选取初始点xk∈S;选取A>0作为可接受的终止参数;令a=1, k=1;

(1) 以xk为初始点, 应用局部下降算法求得问题 (P) 的一个局部极小点, 记作x*k;

(2) 选取初始点列{x${}_{k+1}^i$:i∈Γ}, 使得对于某个δk>0有x${}_{k+1}^i$∈S＼N (x*k, δk) ;

(3) 令i=1;

(4) 若i≤m, 令x=x${}_{k+1}^i$, 转步 (5) ;否则, 转步 (7) ;

(5) 若f (x) <f (x*k) , 且x∈S, 则以x为初始点, 应用已有局部下降算法求问题 (P) 的局部极小点x*k+1, 使得f (x*k+1) <f (x*k) , 令x*k=x*k+1, k=k+1, 转步 (2) ;否则, 转步 (6) ;

(6) 沿方向D1=-∇p (x, x*k, a) 或者$D{}_2=-\frac{\nabla f(x)}{\parallel \nabla f(x)\parallel }-\frac{\nabla p(x,x{}_k^{*},a)}{\parallel \nabla p(x,x{}_k^{*},a)\parallel }$, 找到一个新的点x, 使得p (x, x*, a) 能下降到一定程度。若在极小化过程中, x超出S的边界, 则令i=i+1, 转步 (4) , 否则, 转步 (5) ;

(7) 令a=2a。若a≤A, 转步 (3) ;否则, 算法终止, 视x*k为问题 (P) 的全局极小点。

注:下降方向D1、D2的合理性及优越性在文献[7]中有详细的说明, 不再赘述。

3.2 实验

通过两个算例的数值实验验证算法的可行性与有效性。算例都是在Matlab7.1.0运行环境中实现的。

算例1

$\min f(x)=4x{}_1^2-4x{}_2^2+4x{}_2^4-2.1x{}_1^4+\frac{1}{3}x{}_1^6-x{}_{1}x{}_2$

$\text{s}.\text{t}.x\in \{(x{}_1‚x{}_2)|-3\le x{}_1‚x{}_2\le 3\}$全局极小点x*= (0.090 1, 0.712 2) T, 全局极小值f (x*) =-1.133 1。

算例2

min f (x) = (x${}_1^6$-16x${}_1^5$+86x${}_1^4$-176x${}_1^3$+105x${}_1^2$) /100+x${}_2^2$ (x${}_2^2$-6x2+8) (x${}_2^2$-14x2+48) /100。

$\text{s}.\text{t}.x\in \{(x{}_1‚x{}_2)|x{}_1+x{}_2\le 10‚x{}_1‚x{}_2\ge 0‚0\le x{}_1‚x{}_2\le 8\}$。

全局极小点x*= (2.174 0, 7.341 9) T, 全局极小值f (x*) =-9.123 1。

用k表示迭代次数, xk1表示第k次迭代初始点, x*k表示第k次迭代的局部最优解。迭代过程见表1。

参考文献

[1] Ge R P, Qin Y F. A class of filled functions for finding a global minimizer of a function of several variables.Journal of Optimization Theory and Applications, 1987;54 (2) :241—252

[2]Yang Yongjian, Shang Youlin.A filled function method for uncon-strained global optimization.Shanghai:Science College, Shanghai Univevs:ty, 2006;503—504

[3] Zhang L S, Kong Chi, Duan N G, et al.A new filled function method for global optimization.Global Optim, 2004;28:17—43

[4] Wang Weixiang, Shang Youlin, Zhang Liansheng. A filled function method with one parameter for box constrained global optimization.Applied Mathematics and Computation, 2007;194:54—66

[5] Wang Changyu, Li Duan. Unified theory of augmented Lagrangian methods for constrain-ed global optimization.J Glob Optim, 2009;44:433—458

[6] Wang Weixiang, Shang Youlin, Zhang Liansheng. A filled function method with one parameter for constrained global optim-ization.Journal of Engineering Mathemati-cs, 2008;25 (5) :795—803

求解约束最优化问题KKT系统的BFGS方法 篇3

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