第二章 最优化问题数学基础

第二章最优化问题数学基础为了便于学习最优化方法，本章将对与优化方法密切有关的数学知识作一简要介绍而有些数学知识将在讲解各种算法时，随之介绍．§1.1二次型与正定矩阵一、二次型与实对称矩阵二次型理论在最优化设计中应用十分广泛．应用矩阵的乘法运算，二次型与实对称矩阵紧密地联系在一起了，从而二次型的基本问题又可转化成实对称矩阵问题．二次型理论问题起源于化二次曲线和二次曲面的方程为标准形式的问题．推广到n维空间中，二次超曲面的一般方程为，，，，ninjjiijnnnnnnnnnnnnxxaxaxxaxxaxxaxaxxaxxaxxaxaxxxf11222112222221221112112211121)(用矩阵表示为其中，矩阵A的元素正是二次型的项的系数的一半，是二次型的项的系数．因此，二次型和它的矩阵A是相互唯一决定的，且．，，，，，，，AXXxxxAxxxxxaxxxfTninjnnjiijn11212121][)()(jiaajiijjixxiia2ixTAA•二、正定矩阵•定义2.1如果二次型•对于任何一组不全为零的数恒有•则称正定，且二次型矩阵A也称为正定．•简言之，一个对称矩阵A如果是正定的，则二次型•对于所有非零向量X其值总为正．类似可以给出定义，若二次型•则A为半正定矩阵；若，则A为半负定矩阵；若二次型既不是半正定又不是半负定，就称矩阵A为不定的．ninjTjiijnAXXxxaxxxf1121)(，，，nxxx，，，210)(21AXXxxxfTn，，，)(21nxxxf，，，)(21nxxxf，，，AXXT0)(21AXXxxxfTn，，，0AXXT矩阵A为正定的充要条件是它的行列式的顺序主子式全部大于零，即•由此可见，正定矩阵必然是非奇异的．•例2.1判断矩阵是否正定．•解∵，•∴A是正定的．1112121222111211212212000nnnnnnaaaaaaaaaaaaaa，，，201032124A42142408023013023102，，•一、方向导数•所谓方向导数的概念是作为偏导数的一个推广而引入，它主要研究函数沿任一给定方向的变化率．•定义2.2设在点处可微，P是固定不变的非零向量，是方向P上的单位向量，则称极限•(2.1)•为函数在点处沿P方向的方向导数，式中是它的记号．§2.2方向导数与梯度1:RRfn0XetXfteXfPXft)()(lim)(0000)(Xf0XPXf)(0•定义2.3设是连续函数，，且，若存在，当时都有，•则称P为在点处的下降方•向．若，则称P为在点处的上升方向．•由以上两个定义可立刻得到如下的结论：•若，则从出发在附近沿P方向是下降；若，则从出发在附近沿P方向是上升．1:RRfn0X0P0),0(t)()(00XftPXf)()(00XftPXf0)(0PXf)(Xf0X0X0)(0PXf•二、梯度•定义2.4以的n个偏导数为分量的向量称为在X处的梯度，记为•．•梯度也可以称为函数关于向量的一阶导数．•以下几个特殊类型函数的梯度公式是常用的：•（1）若（常数），则，即；•（2）．•证设，则•于是的第个分量是•．•所以•（3）．•（4）若Q是对称矩阵，则)(Xf)(Xf12()()()()TnfXfXfXfXxxx，，，)(XfXcXf)(0)(Xf0cbXbT)(1212[][]TTnnbbbbXxxx，，，，，，，niiiTxbXb1)(XbTj1()()12nTiijijjbXbxbjnxx，，，，bXbT)(XXXT2)(QXQXXT2)(•三、梯度与方向导数之间的关系•定理2.1设在点处可微，则•，•其中是方向上的单位向量.由这个定理容易得到下列结论：•(1)若，则P的方向是函数在点处的下降方向；•(2)若，则的方向是函数在点处的上升方向．•方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定．绝对值越大，升降的速度就越快，即1:RRfn0XeXfPXfT)()(00eP0)(0PXfT0)(0PXfT0X0XP=·1·•上式中的等号，当且仅当的方向与的方向相同时才成立．•由此可得如下重要结论(如图2.1所示）：•(1)梯度方向是函数值的最速上升方向；•(2)函数在与其梯度正交的方向上变化率为零；•(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；•(4)梯度反方向是函数值最速下降方向．00()()TfXfXeP0()fX00(cos((),))()fXefX·1·•对于一个最优化问题，为了尽快得到最优解，在每一步迭代过程中所选取的搜索方向总是希望它等于或者是靠近于目标函数的负梯度-----图2.1的方向，这样才能使函数值下降的最快．•例2.2试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长后新点的目标函数值．•解因为•所以最速下降方向是－==．•这个方向上的单位向量是•故新点是•对应目标函数值为112fxx222fxx0()fX12102322xxxx06000()1()fXefX10000312XXe221()0215fX§2.3海色矩阵及泰勒展式•一、海色（Hesse）矩阵•前面说过，梯度是关于的一阶导数，现在要问关于的二阶导数是什么？•定义2.5设：:，，如果在点•处对于自变量的各分量的二阶偏导数•都存在，则称函数在点处二阶可导，并且称矩阵()fX()fXX()fXXf1RRnnRX00X•是在点处的Hesse矩阵．•在数学分析中已经知道，当在点处的所有二阶偏导数为连续时有•因此，在这种情况下Hesse矩阵是对称的．222000211212220002202122222000212()()()()()()()()()()nnnnnfXfXfXxxxxxfXfXfXfXxxxxxfXfXfXxxxxxf0Xf0X2200()()12ijjifXfXijnxxxx，，，，•例2.3求目标函数的梯度和Hesse矩阵．•解因为•所以23132221233241432)(xxxxxxxxxXf232131124xxxxxf32122246xxxxf31233246xxxxxf3123321222321312464624)(xxxxxxxxxxxXf•又因为•所以22221213211213222212222331222212462fffxxxxxxxxxfffxxxxxx，，，，，，13213122122642412222212)(xxxxxxxxXf例2.4设，求线性函数在任意点X处的梯度和Hesse矩阵．解:设,则（2.2）∴由式（2.2）进而知∴（阶零矩阵）．1,,RbRXRannbXaXfT)(1212[][]TTnnaaaaXxxx，，，，，，，121()nniiifxxxaxb，，，12iifainx，，，，aaaaXfTn],,,[)(212012ijfijnxx，，，，，OXf)(2例2.5设是对称矩阵，，求二次函数在任意点处的梯度和Hesse矩阵．解设则将它对各变量求偏导数，得∴nnRa1RcRbn，()fX12TTXAXbXc1212()[][]TTijnnnnAaXxxxbbbb，，，，，，，，121111()2nnnnijijiiijifxxxaxxbxc，，，(12)ixin，，，111111111()()()nnjjjjjjnnnnjjnnjjjjnfXaxbaxxbfXfXbaxbaxxbAXXf)(在上式中显然再对它们求偏导数得∴以上例子说明，元函数求导与一元函数的求导在形式上是一致的，即线性函数的一阶导数为常向量，其二阶导数为零矩阵；而二次函数的一阶导数为线性向量函数，二阶导数为常矩阵．最后介绍在今后的计算中要用到的向量函数的导数．1()12nijjijifXaxbinx，，，，2()12ijijfXaijnxx，，，，，AaaaaaaaaaXfnnnnnn2122221112112)(•定义2.6设，记•如果在点处于自变量的各分量的偏导数都存在，则称向量函数•在点处是一阶可导的，并且称矩阵1010101220202012000012()()()()()()()()()()nnmnmmmnhXhXhXxxxhXhXhXxxxHXhXhXhXxxxnmnRXRRH0，：1()[()()]TmHXhXhX，，(12)ihim，，，0XTnxxxX],,,[210()(12)ijhXjnx，，，)(XH0X•是在点处的一阶导数或Jacobi矩阵，简记为•由于n元函数的梯度是向量函数•所以的一阶导数或Jacobi矩阵为00()()mnHXHX1RRfn：1()()()TnfXfXfXxx，，)(Xf112111222212()()()()()()()()()()nnnnnnnnfXfXfXxxxxxxfXfXfXfXxxxxxxfXfXfXxxxxxx22221121222222122222212()()()()()()()()()()nnnnnfXfXfXxxxxxfXfXfXfXxxxxxfXfXfXxxxxx，•得到112111222212()()()()()()()()()()nnnnnnnnfXfXfXxxxxxxfXfXfXfXxxxxxxfXfXfXxxxxxx22221121222222122222212()()()()()()()()()()nnnnnfXfXfXxxxxxfXfXfXfXxxxxxfXfXfXxxxxx，)()(2XfXfnn•据此，从上式得知，函数梯度的Jacobi矩阵即为此函数的Hesse矩阵．•下面给出今后要用到的几个公式：•（1），其中是分量全为常数的维向量，是•阶零矩阵．•（2），其中是维向量，是阶单位矩阵．•（3），其中是阶矩阵．•（4）设，其中，则OccnOnnIXXInn()AXAAnm