投影梯度算法的数值行为研究
第2章 基本概念
2.1 最速下降法
为了了解求解约束问题可行方向法的思想，我们先要了解一下求解无约束问题的下降算法。求解无约束问题的下降算法的过程是：在当前点x?k?处，寻找目标函数f的下降方向d?k?，然后，从x?k?出发，沿d?k?进行线性搜索产生步长?k，进而得到x?k?1??x?k???kd?k?。
解约束问题的可行方向法与解悟约束问题的下降算法类似。但对约束问题而言，我们所关心的只是的问题的可行点。可行方向法从问题的可行点出发，在该点的可行方向中，寻找时目标函数下降的方向，然后沿该方向进行线性搜索，得到一个新的可行点。如此进行下去，算法产生一个点列，该点列中的所有的点均为问题的可行点。希望该点列终止于问题的解，或其极限点是问题的解。 下面我们先给出一些基本概念
2.1.1 下降方向及下降算法
定义2.1.1 设x,d?Rn。若存在数??0，使得
f?x??d??f?x?，????0,??，
则称d是函数f在点x处的一个下降方向。若?d是函数f在x处的“下降方向”，则称d是函数f在x处的一个“上升方向”。
下降方向d从几何上可解释为：当点从x出发，沿方向d移动时，函数f的值的变化呈单调递减的趋势。若令
?????f?x??d?，
则方向d是f在x处的下降方向等价于一元函数?在原点处单调下降。
由一元函数微分学知识可知，若???0??0，则?在原点处单调下降。因此，我们有如下定理。
定理2.1.1 设f连续可微且?f?x??0。
16
投影梯度算法的数值行为研究
（1）若向量d满足?f?x?d?0，则它是f在x处的一个下降方向。
T（2）若矩阵H?Rn?n对称正定，则向量d??H?f?x?是f在x处的一个下降方向。特别，向量d???f?x?是f在x处的一个下降方向。
设f:Rn?R连续可微。考察如下无约束最优化问题：
（2.1） minf?x?，x?Rn。
求解无约束问题（2.1）的下降算法的基本思想是从某个初始点x?0?出发，按照使目标函数值下降的原则构造点列x?k?，即点列x?k?满足条件
????fx?k?1??fx?k?，?k?0,1,?。算法的最终目标是使得点列x?k?中的某个点或某个极限点是问题（2.1）的解或稳定点。
设d?k?是f在x?k?处的一个下降方向，且满足
????????从而，当??0充分小时，f?x????d????f?x???。因此，可取x??fx?k?d?k??0。
kkTkk?1??x?k???kd?k?，
其中，?k?0，使得fx?k???kd?k??fx?k?。在此基础上，我们给出求解无约束问题（2.1）下降算法的一般步骤如下：
算法2.1 （求解无约束问题的下降算法）
步1 给定初始点x?0??Rn，精度??0。令k?0。
步2 若?f?x?k????，则终止算法，得解x?k?。否则，转步3。 步3 确定下降方向d?k?，使得
?????fx?k?d?k??0。
步4 确定步长?k?0，使得
??Tfx?k???kd?k??fx?k?。
步5 令x?k?1??x?k???kd?k?，k:?k?1，转步2。
注：步2中的不等式?f?x?k????称为算法的终止准则。其中精度?根据实
17
????投影梯度算法的数值行为研究
际问题的需要确定，但在进行理论分析时，我们均设??0。步4中的数?k称为“步长”。
2.1.2 最速下降法
在上一部份里面，我们介绍了求解无约束问题（2.1）的下降算法的一般步骤，即算法2.1。在算法2.1中，确定下降方向d?k?的步骤——步3非常重要，是算法的核心。不同的算法确定d?k?的方式不同，相应算法的收敛性理论与数值效果有很大差异。现在我们将介绍求解无约束问题（2.1）的一种常用算法——最速下降法。这里我们假设f二次连续可微。
由定理2.1.1知，负梯度方向??fx?k?是函数f在x?k?处的下降方向。令
??Td?k????fx?k?。可以证明d?k?是下面问题的解：
?fx?k?minp?0p????p。
事实上，对任何p?Rn,p?1，由Cauchy-Schwarz不等式得
?fx?k???Tp???fx?k???p???fx?k?。
??当p?d?k????f?x?k???f?x?k??时，上面的不等式成立等式。由于d?k?的上述性质，我们称d?k?为函数f在x?k?处的“最速下降方向”，相应的下降算法2.1称为“最速下降算法”。利用算法2.1，可构造求解无约束问题（2.1）的最速下降算
法如下：
算法2.2 （最速下降法）
步1 给定初始点x?0??Rn，精度??0。令k?0。
步2 若?f?x?k????，则算法终止，得解x?k?。否则，计算d?k????fx?k?。转步3。
步3 由线性搜索确定步长?k。
步4 令x?k?1??x?k???kd?k?，k:?k?1，转步2。
??18
投影梯度算法的数值行为研究
2.2 约束问题的最优性条件
设函数f,gi,hj:Rn?R,i?1,?,m1,j?m1?1,?,m连续可微。考察约束最优化问题
min f?x?
s.t. gi?x??0,i?I??1,?,m1?， （2.2）
hj?x??0,j?E??m1?1,?,m?。
问题（2.2）的可行域为
D?x?Rngi?x??0,i?I,hj?x??0,j?E。
显然，可行域D为闭集。因此在本节的讨论中，我们均假设集合D为Rn中的闭集。与无约束问题不同，约束问题的最优解在可行域中。为了导出约束问题最优解的必要条件，我们先引入可行方向的概念。
2.2.1 可行方向
定义2.2.1 设x?D,d?Rn。若存在数??0，使得
x??d?D，????0,??，
??则称d是D在x处的一个“可行方向”。D在x处的全体可行方向构成的集合记为FD?x,D?。
（函数f在x处的可行的下降方向称为f在x处的“可行下降方向”，简称为f的“可行下降方向”。由定理2.1.1知，若x?D,d?FD?x,D?且?f?x?d?0，
T则d是函数f在x处的一个可行下降方向。）
定义2.2.2 设x?D,d?Rn。若存在序列d?k??Rn和正数序列??k?，使得
??x??kd?k??D，?k，
且有limd?k??d,lim?k?0，则称d是D在x处的一个“序列可行方向”。D在x
k??k??处的所有序列可行方向构成的集合记为SFD?x,D?。
19
投影梯度算法的数值行为研究
（由可行方向和序列可行方向的定义不难看出：对任给的x?D，） FD?x,D??SFD?x,D?。
可行方向与序列可行方向的区别见图2.1。
图2.1 可行方向与序列可行方向
下面的定理给出了约束问题最优解得一个必要条件。
定理2.2.1 设x*?D是问题（2.2）的一个局部最优解。则
?fx*d?0，?d?SFD?x*,D?。
??T
利用定理2.1.1，定理2.2.1可粗略地理解为：若x*是问题（2.2）的局部最优解，则该点处的任何序列可行方向都不是函数f的下降方向。特别，函数f在
x*处不存在可行的下降方向。
定理2.2.2 设x*?D且满足
?fx*d?0，?0?d?SFD?x*,D?，
??T则x*是问题（2.2）的一个严格局部最优解。
定理2.2.2说明：若在问题（2.2）的可行点x*处的所有序列可行方向都是函数f的上升方向，则x*必是问题（2.2）的严格局部最优解。
20