投影梯度算法的数值行为研究 - 图文(4)

投影梯度算法的数值行为研究

第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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库投影梯度算法的数值行为研究 - 图文(4)在线全文阅读。