边界约束优化问题一个新的投影梯度方法 A New Projected Gradient Method for Bound Constrained Optimization

doi:10.12677/pm.2011.11010

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Pure Mathematics 理论数学, 2011, 1, 46-50

http://dx.doi.org/10.12677/pm.2011.11010 Published Online April 2011 (http://www.hanspub.org/journal/pm/)

A New Projected Gradient Method for Bound

Constrained Optimization

Shanzhou Niu, Yi Wang, Dandan Cui

School of Mathematics and Computer Science, Gannan Normal University, Ganzhou

Email: maszniu@163.com

Received: Mar. 14th, 2011; revised: Mar. 28th, 2011; accepted: Apr. 1st, 2011.

Abstract: The projected gradient method is very suitable to solve large-scale nonlinear programming due to

the simplicity of its iteration and implement. In this paper, based on the quasi-Cauchy equation and diagonal

updating, a new projected gradient method is proposed for bound constrained optimization. On the basis of

nonmonotone line search, global convergence is established. The numerical results show that the new algo-

rithm is promising.

Keywords: Bound Constrained Optimization; Projected Gradient Method; Nonmonotone Line Search;

Global Convergence

边界约束优化问题一个新的投影梯度方法

牛善洲，王义，崔丹丹

赣南师范学院数学与计算机科学学院，赣州

Email: maszniu@163.com

收稿日期：2011年3月14日；修回日期：2011年3月28日；录用日期：2011 年4月1日

摘要：投影梯度法因其算法简单、易于实现，非常适合求解大规模优化问题。本文基于拟柯西方程和

对角变换，构造了一个新的投影梯度算法。在非单调线搜索条件下，证明该方法具有全局收敛性。最后

数值实验表明新方法是有效的。

关键词：边界约束优化；投影梯度方法；非单调线搜索；全局收敛性

1. 引言

设:n

RR是一个连续可微的函数。考虑如下

的边界约束优化问题：



min( )

.. |

txxR lx u 

(1)

其中，，，

。将 f在点 x处的梯度记

为



,, ,

lll l

,1,2,,i n 

 

,,,



,,, T

uuu u





lu 

 

xgxgx gx。

定义 1.1 设点x，如果

满足

ii i

iii i

ii i

xl g

lxu g

xu g











(2)

则称点

为问题(1)的一个稳定点。

问题(1)是一类十分重要的约束优化问题，许多实

际的优化问题都可以转化为问题(1)的形式。此外，问

题(1)常常是求解一般约束优化问题的增广Lagrange

和罚函数方法的一个子问题。因此，近年来许多学者

对问题(1)做了大量的研究，提出了许多求解该问题的

数值算法[1-4]。

投影梯度方法具有易于实现，以及适合求解大规

模优化问题的优点。另一方面，为了保证迭代点的有

效性，计算迭代点的投影一般都是十分费时的。此外，

即使投影的计算十分简便，投影梯度算法也会跟无约

束优化问题的梯度方法一样具有很慢的收敛速度。为

了提高投影梯度方法的收敛速度，文献[5]提出了求解

问题(1)的一个谱投影梯度方法，此方法是无约束优化

问题的谱梯度方法的推广。谱梯度方法最初是在文献

牛善洲等边界约束优化问题一个新的投影梯度方法47

[6]中提出的，此方法提高了梯度方法的收敛速度并且

大大减少了计算量。因此，谱梯度方法被广泛应用于

求解无约束和约束优化问题[7-9]。

文献[10]基于拟柯西方程与对角变换提出了求解

无约束优化问题的一个单调的梯度方法，此方法的主

要思想是：如果对角变换得到的新的对角矩阵非正定

时，将前一步的正定对角矩阵作为新的正定对角矩阵。

文献[11]提出了无约束优化问题的一个多元谱梯度方

法，并且具有二次终止性。此外，该方法引入非单调

线搜索后具有全局收敛性。基于多元谱梯度方法，文

献[4]提出了边界约束优化问题的一个多元谱投影梯

度方法。基于拟柯西方程与对角变换，本文提出了一

个新的投影梯度方法，并且采用文献[12]中的非单调

线搜索技术和一些限制保证算法的全局收敛性。

2. 新的投影梯度方法

首先，考虑无约束优化问题的谱梯度方法。设 gk

为函数 f在点xk处的梯度，谱梯度方法的迭代格式为



 g

. (3)

其中， k



由下述方式决定：





. (4)

其中， 111

kkkk kk1

xxy gg



 



。步长 k



的

选取可以减少计算量并且在很大程度上提高了梯度方

法的收敛速度。此外，k



还被赋予了拟牛顿性质。事

实上，由(4)式给出的 k



可以由下式得到：

min kk

Is y





,

其中， k



近似代替函数f在点 xk处的Hessian 矩

阵。

我们在对角变换的基础上构造了一个新的梯度方

法，其迭代格式如下：

kkkk

xHg



 . (5)

其中，矩阵Hk为对角矩阵。我们的目标是通过对

角变换构造对角矩阵 Hk，使得矩阵Hk是Hessian 矩阵

的一个很好的近似。Hk满足拟牛顿方程：

11kk k



.

进一步，我们可以得到拟柯西方程：

111

kkkkk

设是正定对角矩阵，Hk是由对角变换得

到的新矩阵并且使得 Hk也是正定对角矩阵。为了使得

Hk能够更好地近似 Hessian 矩阵，Hk必须满足拟柯西

方程，并且在变分原理下使得Hk和Hk − 1 的差量最小。

在计算机中对角矩阵与向量占有相同的存储空间，因

此我们可以得到一个存储空间为的算法。文献

[10]给出如下定理：

H



定理 2.1[10] 设11kkk





 ，11kkk



 ，

11kkk

ygg





。设 10

s



，Hk − 1是正定对角矩阵。

考虑如下优化问题：

111111 11

min

TTT

kkkkkk kk

tsssys Hs



 



 . (6)

其中，

表示 F范数。则(6)式的最优解为：





111 11

12,1,2,,

TT i

kk kkk k

sysHss in

tr E

 







其中，tr 表示迹算子， i



是对角矩阵的第 i个对

角元素，是 Sk的第 i个坐标元素，



 





11 1

diag,, , n

kk k

Ess s

 





。

由定理 2.1，我们得到Hk的迭代公式为：



111 111

()

,1,2,,

()

TT i

kkk kkk

sysHs s

tr E

 



n



.

(7)

其中， i

，1



分别为Hk，1k

的第 i个对角元素。

若存在某个i使得 0



，则无法保证(5)式中的搜索

方向为下降方向。为了克服上述缺点，我们使用下述

的迭代格式：

112

11 1

diag,, ,

kk n

kk k

 



















. (8)

其中， i



由下式得到：

11111

111 11

,0,1,2

,0,

iT T

kkkkkk

kkTT

kkkkk

Hsys Hsin

1,2,,

ysHs i









 















n

. (9)

由(8) 和(9)式，我们可以建立问题(1)的新的投影

梯度算法。给定 n



，定义集合上的投影





pz：



iii

iiii

iii

lifz l

pzziflzu

uifz u















(10)

Hss y





牛善洲等边界约束优化问题一个新的投影梯度方法

48 |

为了保证算法的全局收敛性，我们使用文献[12]

中的非单调线搜索技术和一些限制。下面我们给出新

的投影梯度方法。

新的投影梯度(NPG)算法

给定数据： 0

R，0R





，初始矩阵 0



，



0,1



0



，12



，0



，10



以及

整数。Set 。

1 0k

Step1：If



1kkk

px gx



, stop.

Step2：If then 0k

Set 100

(

)

px g



 ，跳转至 Step6。

If ，Set

111 11

kkk kk

sy sHs

 

 ii



，

. 1, 2,,in 

Otherwise 1

,1,2,,

sy in





.

If 1

 



  ，Set .







Step3：Set 12

11 1

diag,, ,

kk k

















。

Step4：计算；Set



kkkk

dpxg x



 



。

Step5：(非单调线搜索)











0min,1

max T

kkkj k

jkM k

xdfx gd







 



then

令 1

kkkk









，跳转至 Step6。

Else 取





new



 

，Set new



，跳转至

Step5。

Step6：Set ；跳转至 Step1。 1kk

3. 全局收敛性分析

为了讨论 NPG 算法的全局收敛性，设目标函数



x满足如下的基本假设：

假设 3.1 水平集





fx fx 是紧集。

引理 3.1 设，。则

存在常数，使得

x



kkkk

dpxg x



 

10c2

kk k

dcd 。

证明由的定义可知

dpx x











。下

面分三种情况讨论：

Case 1：







 ，有

ii i

kk k

dpx x











，则 2

()

iii i

kkk k



 。

Case 2：





，有

ii iii

kkk k

dpxxlx













，





iiii

kk k





则





()

iii iiiii

kkkkkkk

dlxdd



 。

Case 3：



，有





ii iii

kkkk

dpx xux













，





iii

kk k





则





()

iii iiiii

kkkkkk k

duxdd



 。

由于 i





，取1





，则 2

kk k

dcd ，引理

得证。

引理 3.2 设





是由 NPG 算法产生的点列。则



是问题(1)的稳定点。

证明定义





Lixl

，



kii

il x u，





u|

Uix。

设0



，如果ik



，0

dpx x





 





则











 ，

由(10)式得到





。

考虑到，则得到。 0



0

g

类似地，如果，可以得到；如果

，可以得到

iU

g

iFg



。因此， k

是问题(1)的稳定

点。

另一方面，设 k

是问题(1)的稳定点，如果 k



，

g，则





。因此，当 i，得到

L0



。

类似地，当可以得到；可以得到

iF0

dk

iU



。因此， 0



。引理得证。

由引理 3.1，引理 3.2 以及文献[5]中的定理2.2，

我们可以得到下面的收敛性定理。

定理 3.2 设





是由 NPG 算法产生的点列，则





的任一极限点都是问题(1)的稳定点。

4. 数值实验

在本节，我们对NPG算法用MATLAB 编程，并在

PC( Intel Core 2 Duo CPU 2.2GHz Memory 2GB )上进

数值实验。设置参数，，

行5M4





10.1





，

牛善洲等 | 边界约束优化问题一个新的投影梯度方法



1.()();,,,,100,100,,100,100,100,,100

nTT

fxe xxlu

nn n





 











Table 4.1.

表4.1.

n NI/NF/NG CPU(s)





kk k

px gx





100 7/7/7 0.156 2.066143E–010 100

500 7/7/7 0.063 1.828211E–009 500

1000 7/7/7 0.125 3.526545E–009 1000

10000 7/7/7 11.297 1.838901E–008 10000

 

2.()();1,1,,1,1000, 1000,, 1000,1000,1000,,1000

nTT

fxe xxlu











Table 4.2.

表4.2.

n NI/NF/NG CPU(s)





kk k

px gx





100 359/525/359 0.25 9.409498E–007 505

1000 268/339/268 4.25 9.717239E–007 50 050

 

3.();1,1, ,1,10,10,,10,10,10,,10

fxxAx Axlu

n





 





 





Table 4.3.

表4.3.

n NI/NF/NG CPU(s)





kk k

px gx





100 2/2/2 0.015 2.359224E–013 2.782969E–028

500 2/2/2 0.031 8.192363E–011 6.711481E–024

1000 2/2/2 0.094 1.025163E–009 5.254800E–022

5000 2/2/2 2.171 3.240671E–007 1.050195E–017

 

4.();1,1,,1,10, 10,, 10,10,10,,10

fxxAx Axlu

n











 





Table 4.4.

表4.4.

n NI/NF/NG CPU(s)





kk k

px gx





100 69/73/69 0.11 7.468630E–007 1.100490E–013

200 120/151/120 0.157 9.889196E–007 1.871602E–013

300 90/100/90 0.312 7.179043E–007 8.276060E–014

500 361/516/361 3.641 9.324383E–007 1.409143E–013

牛善洲等边界约束优化问题一个新的投影梯度方法

50 |

20.9



10





，，10



00 0

px gx



，





 



1if

if101

10 if10

kk k

kk kkk k

kk k

px gx

px gxpx gx

px gx







 



 



 







。

我们对下述四个测试函数进行数值实验，迭代终

止条件为：



kk k

px gx



 ，即。

110







数值结果如表4.1、表 4.2、表 4.3、表4.4 所示。

其中，n, NI, NF, NG, CPU 分别表示测试函数的维数，

算法的迭代次数，函数值的计算次数，梯度值的计算

次数，所用的cpu 时间。

5. 致谢

本文第一作者感谢赣南师范学院研究生创新基金

的资助。作者对审稿人和编辑所提出的宝贵意见表示

衷心的感谢！

参考文献 (References)

[1] R. H. Byrd, P. Lu, J. Nocedal. A limited-memory algorithm for

bound constrained optimization. SIAM J. Sci. Stat. Comput,

1995, 16(5): 1190-1208.

[2] W. W. Hager, H. Zhang. A new active set algorithm for box

constrained optimization. SIAM J. Optim, 2006, 17(2): 526-

557.

[3] J. Moré, G. Toraldo. On the solution of large scale quadratic

programming problem with bound constrains. SIAM J. Optim,

1991, 1(1): 93-113.

[4] Z. S. Yu, Sun J, Qin Y. A multivariate spectral projected gradient

method for bound constrained optimization. J. Comput. Appl.

Math, 2011, 235(8): 2263-2269.

[5] E. G. Birgin, G. M. Martinez, M. Raydan. Nonmonotone spectral

projected gradient methods on convex sets. SIAM J. Optim,

2000, 10(4): 1196-1211.

[6] J. Barzilai, J. M. Borwein. Two-point step size gradient methods.

IMA J. Numer. Anal, 1988, 8(1): 141-148.

[7] R. Andreani, E. G. Birgin, J. M. Martínez, et al. Spectral pro-

jected gradient and variable metric methods for optimization

with linear inequalities. IMA J. Numer. Anal, 2005, 25(2):

221-252.

[8] E. G. Birgin, G. M. Marttínez. Larges-scale active-set box-

constrained optimization method with spectral projected gra-

dients. Comput. Optim Appl, 2002, 23(1): 101-125.

[9] Y. Dai, R. Fletcher. Projected Barzilai-Borwein method for

large-scale box-constrained quadratic programming. Numer.

Math, 2005, 100(1): 21-47.

[10] W. J. Leong, M. A. Hassan, M. Farid. A monotone gradient

method via weak secant equation for unconstrained optimi-

zation. Taiwanese J. Math, 2010, 14(2): 413- 423.

[11] L. Han, G. Yu, L. Guan. Multivariate spectral gradient method

for unconstrained optimization. Appl Math Comput, 2008,

201(1-2): 621-630.

[12] L. Grippo, F. Lampariello, S. Licidis. A nonmonotone line search

technique for Newtons method. SIAM Journal on Numerical

Analysis, 1986, 23(4): 26-33.