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

第二章最优化问题数学基础为了便于学习最优化方法，本章将对与优化方法密切相关的数学知识作一简要介绍，而有些数学知识将在讲解各种算法时，随之介绍．§2.1二次型与正定矩阵一、二次型与实对称矩阵二次型理论在最优化设计中应用十分广泛．应用矩阵的乘法运算，二次型与实对称矩阵紧密地联系在一起了，从而二次型的基本问题又可转化成实对称矩阵问题．二次型理论问题起源于化二次曲线和二次曲面的方程为标准形式的问题．推广到n维空间中，二次超曲面的一般方程为，，，，ninjjiijnnnnnnnnnnnnxxaxaxxaxxaxxaxaxxaxxaxxaxaxxxf11222112222221221112112211121)(用矩阵表示可简记为，，，，，，，AXXxxxAxxxxxaxxxfTninjnnjiijn11212121][)(其中矩阵A的元素)(jiaajiij正是二次型的jixx项的系数的一半，iia是二次型的2ix项的系数．因此，二次型和它的矩阵A是相互唯一决定的，且TAA．二、正定矩阵定义2.1如果二次型ninjTjiijnAXXxxaxxxf1121)(，，，对于任何一组不全为零的数nxxx，，，21恒有0)(21AXXxxxfTn，，，，则称)(21nxxxf，，，正定，且二次型矩阵A也称为正定．简言之，一个对称矩阵A如果是正定的，则二次型)(21nxxxf，，，AXXT对于所有非零向量X其值总为正．类似可以给出定义，若二次型0)(21AXXxxxfTn，，，，则A为半正定矩阵；若0AXXT，则A为半负定矩阵；若二次型AXXT既不是半正定又不是半负定，就称矩阵A为不定的．矩阵A为正定的充要条件是它的行列式||A的顺序主子式全部大于零，即1112121222111211212212000nnnnnnaaaaaaaaaaaaaa，，，．由此可见，正定矩阵必然是非奇异的．例2.1判断矩阵201032124A是否正定．解∵01320103212408322404，，，∴A是正定的．§2.2方向导数与梯度一、方向导数所谓方向导数的概念是作为偏导数的一个推广而引入的，它主要研究函数沿任一给定方向的变化率．定义2.2设1:RRfn在点0X处可微，P是固定不变的非零向量，e是方向P上的单位向量，则称极限tXfteXfPXft)()(lim)(0000（2.1）为函数)(Xf在点0X处沿P方向的方向导数，式中PXf)(0是它的记号．定义2.3设1RRfn：是连续函数，nRX0，nRP且0P，若存在0，当),0(t时都有)()(00XftPXf，则称P为f在点0X处的下降方向．若)()(00XftPXf，则称P为f在点0X处的上升方向．由以上两个定义可立刻得到如下的结论：若0)(0PXf，则)(Xf从0X出发在0X附近沿P方向是下降；若0)(0PXf，则)(Xf从0X出发在0X附近沿P方向是上升．事实上，若0)(0PXf，则当0t充分小时，根据式（2.1）必有0)()(00tXfteXf，即)()(0XfXf，其中teXX0是从0X出发在P方向上的点，说明)(Xf是下降的．同理可以说明，若0)(0PXf，则)(Xf是上升的．二、梯度定义2.4以)(Xf的n个偏导数为分量的向量称为)(Xf在X处的梯度，记为．，，，２TnxXfxXfxXfXf)()()()(1梯度也可以称为函数)(Xf关于向量X的一阶导数．以下几个特殊类型函数的梯度公式是常用的：（1）若cXf)(（常数），则OXf)(，即Oc；（2）bXbT)(．证设TnTnxxxXbbbb][][2121，，，，，，，，则niiiTxbXb1．于是)(XbT的第j个分量是．，，，，njbxbxXbxjniiijTj21)()(1所以bXbT)(．（3）XXXT2)(．（4）若A是对称矩阵，则AXAXXT2)(．三、梯度与方向导数之间的关系定理2.1设1RRfn：在点0X处可微，则eXfPXfT)()(00，其中e是P方向上的单位向量．证明在相应的数学分析中可找到（故略去）．由这个定理容易得到下列结论：(1)若0)(0PXfT，则P的方向是函数)(Xf在点0X处的下降方向；(2)若0)(0PXfT，则P的方向是函数)(Xf在点0X处的上升方向．方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定．绝对值越大，升降的速度就越快，即00()()TfXfXeP=)()))(cos((1)(000XfeXfXf，，上式中的等号，当且仅当e的方向与)(0Xf的方向相同时才成立．由此可得如下重要结论(如图2.1所示）：(1)梯度方向是函数值的最速上升方向；(2)函数在与其梯度正交的方向上变化率为零；(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；(4)梯度反方向是函数值的最速下降方向．对于一个最优化问题，为了尽快得到最优解，在每一步迭代过程中所选取的搜索方向P总是希望它等于或者是靠近于目标函数的负梯度（即－)(Xf）的方向，这样才能使函数值下降的最快．例2.2试求目标函数1)(2221xxXf在点TX]30[0，处的最速下降方向，并求沿这个方向移动一个单位长后新点的目标函数值．解因为221122xxfxxf，，所以最速下降方向是6022)(3021021xxxxXf．这个方向上的单位向量是10)()(00XfXfe．故新点是20103001eXX，对应目标函数值为5120)(221Xf．§2.3海色矩阵及泰勒展式一、海色（Hesse）矩阵前面说过，梯度)(Xf是)(Xf关于X的一阶导数，现在要问)(Xf关于X的二阶导数是什么？定义2.5设f：1RRn，nRX0，如果f在点0X处对于自变量X的各分量的二阶偏导数20()(12)ijfXijnxx，，，，都存在，则称函数f在点0X处二阶可导，并且称矩阵202202102202220212021022102210202)()()()()()()()()()(nnnnnxXfxxXfxxXfxxXfxXfxxXfxxXfxxXfxXfXf是f在点0X处的Hesse矩阵．在数学分析中已经知道，当f在点0X处的所有二阶偏导数为连续时有．，，，，，njixxfxxfijji2122因此，在这种情况下Hesse矩阵是对称的．图2.1例2.3求目标函数23132221233241432)(xxxxxxxxxXf的梯度和Hesse矩阵．解因为，，，3123332122223213112464624xxxxxfxxxxfxxxxxf，所以3123321222321312464624)(xxxxxxxxxxxXf．又因为22221213211213222212222331222212462fffxxxxxxxxxfffxxxxxx，，，，，，所以13213122122642412222212)(xxxxxxxxXf．例2.4设1RbRXRann，，，求线性函数bXaXfT)(在任意点X处的梯度和Hesse矩阵．解设TnTnxxxXaaaa][][2121，，，，，，，，则niiinbxaxxxf121)(，，，，，，，，，niaxfii21（2.2）∴aaaaXfTn],,,[)(21．由式（2.2）进而知，，，，，，njixxfji2102∴OXf)(2（nn阶零矩阵）．例2.5设nnRA是对称矩阵，1RcRbn，，求二次函数)(XfcXbAXXTT21在任意点处的梯度和Hesse矩阵．解设nnijaA)(，TnTnxxxXbbbb][][2121，，，，，，，，则．＋＋，，，cxbxxaxxxfniiininjjiijn1112121)(将它对各变量)21(nixi，，，求偏导数，得，１１１１nnjjnjnjjjnjnjnjnjjjnbbxaxabxabxaxXfxXfXf11111)()()(∴bAXXf)(．在上式中显然，，，，　　，＝１nibxaxXfnjijiji21)(再对它们求偏导数得，，，，，，njiaxxfijji212∴AaaaaaaaaaXfnnnnnn2122221112112)(．以上例子说明，n元函数求导与一元函数的求导在形式上是一致的，即线性函数的一阶导数为常向量，其二阶导数为零矩阵；而二次函数的一阶导数为线性向量函数，二阶导数为常矩阵．最后介绍在今后的计算中要用到的向量函数的导数．定义2.6设nmnRXRRH0，：，记TmXhXhXhXH)]()()([)(21，，，，如果)21()(miXhi，，，在点0X处对于自变量TnxxxX][21，，，的各分量的偏导数)21()(0njxXhji，，，都存在，则称向量函数)(XH在点0X处是一阶可导的，并且称矩阵1010101220202012000012()()()()()()()()()()nnmnmmmnhXhXhXxxxhXhXhXxxxHXhXhXhXxxx是)(XH在点0X处的一阶导数或Jacobi矩阵，简记为)()(00XHXHnm．由于n元函数1RRfn：的梯度是向量函数，，，，２TnxXfxXfxXfXf)()()()(1所以)(Xf的一阶导数或Jacobi矩阵为112111222212()()()()()()()()()()nnnnnnnnfXfXfXxxxxxxfXfXfXfXxxxxxxfXfXfXxxxxxx22221121222222122222212()()()()()()()()()()nnnnnfXfXfXxxxxxfXfXfXfXxxxxxfXfXfXxxxxx，112111222212()()()()()()()()()()nnnnnnnnfXfXfXxxxxxxfXfXfXfXxxxxxxfXfXfXxxxxxx222211212222221222