求多变量函数极值的基本下降法VIP专享

1§3 求多变量函数极值的基本下降法 考虑无约束非线性规划问题(UNP)，即 )(minxxf (UNP) 其中函数1:RRfn →。 3 .1 最速下降法 最速下降法又称梯度法，是法国著名数学家 Cau chy 于 1947 年提出的利用负梯度方向求解无约束非线性规划问题的一个简单而基本的方法。本节先引进函数在某点的最速下降方向的概念，然后给出最速下降法的迭代步骤并证明其收敛性。 1 ．最速下降方向 考虑(UNP)，其中1:RRfn →具有连续偏导。根据微积分知识已经知道，从任一给定点nR∈x出发，函数)(xf沿着该点的负梯度方向( )f−∇x 前进时，函数值下降最快。下面我们推导更一般的结论。 设矩阵nnRH×∈是正定阵，向量nR∈s，则称THH=sss 是 s 的 H 范数。显然，H=I 时，H =ss就是欧氏范数。 设nR∈x，nR∈s是 H 范数意义下的单位向量，即1H =s，则)(xf在 x 处沿着 d 方向以步长λ 前进时，利用 Tay lor 展开式知其下降量为 ( )()( )( )Tfffoλλλ−+= − ∇+xxsxs 因此)(xf在 x 处沿着 s 方向的下降率为 0( )()lim( )Tfffλλλ→−+= −∇xxsxs 据此，为使函数下降最快即下降率最大，我们考虑优化问题 min( ).. 1THfs t∇=xss 即 min( ).. 1TTfs tH∇=xsss 利用微积分知识易推得 11( )( )HHfHf−−−∇=∇xsx 因此，在 H 范数意义下，当)(xf在 x 处沿着1( )Hf−= −∇sx 方向前进时，函数值下降最快。我们称1( )Hf−= −∇sx 是 H 范数意义下 f 在 x 处的最速下降方向。特别地，当 H=I 时，即在欧氏范数意义下，)(xf在 x 处沿着( )f= −∇sx 即负梯度方向前进时，函数值下降最快。同样，称( )f= −∇sx 是(欧氏范数意义下)f 在 x 处的最速下降方向。 注 3 .1 设nnRH×∈是正定阵，≠∇)(xf0 ，则对1( )Hf−= −∇sx 来说， 1( )( )( )TTffHf−∇= −∇∇xsxx <0 2因此根据定理补.1 知，1( )Hf−= −∇sx 是f 在x 处的下降方向。 2 ．最速下降法 最速下降法的思想是：沿着目标函数在当前迭代点处的最速下降方向即负梯度方向进行一维搜索，从而得到新的迭代点。当目标函数在迭代点处的梯度与零向量接近到一定程度时，该点可作为(UNP)的近似最优解。下面给出最速下降法的具体迭代步骤，其中( )( )()kkf= ∇gx。 算法 3 .1 ：最速下降法 1． 选定初始数据。给出初始点nR∈)0(x，精度参数ε >0。令 k=0。 2． 终止判别。求( )(...