第一章最优化问题与数学预备知识中学教育中考_中学教育-中考.pdf

《第一章最优化问题与数学预备知识中学教育中考_中学教育-中考.pdf》由会员分享，可在线阅读，更多相关《第一章最优化问题与数学预备知识中学教育中考_中学教育-中考.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备 欢迎下载 第一章 最优化问题与数学预备知识 1.最优化问题的一般形式 给定目标函数，满足不等式约束及等式约束，记为：)(minxfX，其中Tnxxxx,.,21)(,.2,10)(,.,2,10)(.nlljxhmixstsji 满足所有约束的向量X称为容许解或容许点，容许点集合称为容许集。从最优化问题的一般形式可以看出，最优化要解决的问题就是在容许集中找一点*x，使目标函数)(xf，在该点取极小。这样*x称为问题的最优点，而相应的目标函数值)(*xf称为最优值。2.最优化问题分类 最优化问题可分为静态问题和动态问题两大类，本书只讨论静态问题。静态最优化问题又可分为无约束问题和约束问

2、题两类。例：求 Rosenbrock 函数大极小点，即212212)1()(100minxxx。这是一个无约束二维问题。例：求优化问题 3214minxxx 422.321xxxts 0,0,0321xxx 的最优解。这是一个约束最优化问题。无约束问题又可分为一维问题及 n 维问题，求解一维问题的方法称为一维学习必备 欢迎下载 搜索或直线搜索，在最优化方法中起着十分重要的作用，故单独列出。约束问题又分为线性规划和非线性规划。3.二次函数 1)二次函数的一般形 ninjniiijiijncxbxxqxxxfxf1112121),.,()(它的矩阵形式是cxbQxxxfTT21)(其中.21222

3、2111211nnnnnnqqqqqqqqqQ,nbbbb.21 这里Q是对称矩阵。我们称特殊的二次函数QxxxfT21)(为二次型。（无一次项和常数项）2)正定矩阵 设Q是nn阶对称矩阵。若nRx且0 x时都有0QxxT，则称矩阵Q是正定的；若nRx都有0QxxT，则称矩阵Q是半正定的；若nRx且0 x时都有0QxxT，则称矩阵Q是负定的。若nRx都有0QxxT，则称矩阵Q是半负定的。一个对称矩阵是不是正定的，可用 sylvester定理判定，该定理内容是。一个nn阶对称矩阵Q是正定矩阵的充分必要条件是，矩阵Q的各阶主子式都是正的。3)二次函数的最优解析解 如矩阵Q是正定矩阵cxbQxxxf

4、TT21)(，)(xf的等值面是同心椭球面族。约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时

5、都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备 欢迎下载 其中心是bQx1*，还可证明bQx1*恰是二次目标函数的唯一极小点。综上所述，对于二次目标函数有有效的求极小点的算法。该算法也可用于一般目标函数小范围内的最优解搜寻，即当搜索区域位于最优点附近时，该方法是一种有效算法。最优化理论中判定一个算法的好坏标准之一，就是把该算法用于Q为正定的二次目标函数，如果能迅速地找到极小点，那就是好的算法；否则就是不好的或不太好的算法。特别地，当把一个算法应用于Q为正定的二次目标函数时，如果在有限步内就能求出极小点来，那么这种算法称为二次收敛算法，或具有二次收敛性。4.梯度与 Hessian

6、矩阵 1)多元函数的可微性与梯度 定义 1:对于函数)(xf，如果存在 n 维向量l，对于任意 n 维向量p,有：0)()(lim000pplxfpxfTp，则称)(xf在0 x处可微。显而易见，如)(xf在0 x处可微，则有：)()()(00pOplxfpxfT 实际上l就是)(xf的偏导数向量Tnxxfxxfxxfl)(.)(,)(02010 证明如下：令nllll.,21；取iiepp，其中ip是无穷小变量，ie是第i个坐标轴上的单位向量，即：Tiie0.,0,1,0.,0 约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问

7、题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备 欢迎下载 iiiixiiipiipxxflxxfxxfpxfepxfpxfepxfii)()()(

8、)()()()(0000000000limlimlim 定义 2:以)(xf的 n 个偏导数为分量的向量称为)(xf在x处的梯度，记为 Tnxxfxxfxxfxf)(.,)(,)()(21 因此)()()()(000pOpxfxfpxfT，这个公式与一元函数的 Taylor 展开式是相对应的。2)方向导数 定义:设f是定义在nR中区域上的实值函数，f在点0 x处可微，p是固定不变的常量，e是方向p上的单位向量，则称极限txftexfpxft)()(lim)(0000为函数)(xf在点0 x处沿p方向的方向导数。若0)(0pxf，则)(xf从0 x出发在其附近沿p方向是下降的。若0)(0pxf，

9、则)(xf从0 x出发在其附近沿p方向是上升。事实上，若0)(0pxf，则当0t且充分小时，必有0)()(00txftexf，即)()(0 xfxf，即)(xf是下降的。同理可说明，若0)(0pxf，)(xf是上升的。定理：设f是定义在nR中区域上的实值函数，f在点0 x处可微，则exfpxfT)()(00，其中e是p方向的单位向量。证明：因为)()()()(000pOpxfxfpxfT 约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束

10、问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备 欢迎下载 exfttoexfttxftexfpxfTTtt)()()(lim)()(lim)(0000000 推论：若0)(0pxfT，则p方向是函数)(xf在点0 x处的下降方向；若0)(0

11、pxfT，则p方向是函数)(xf在点0 x处的上升方向；方向导数的正负决定了函数的升降，其绝对值的大小决定函数值升降的快慢。绝对值越大，升降的速度就越快。3)最速下降方向 cos)()()(000 xfexfpxfT 其中是梯度与p方向的夹角。因此，函数负梯度方向就是函数的最速下降方向。4)梯度的性质 函数在某点的梯度若不为零，则必与过该点的等值面垂直。梯度方向是函数具有最大变化率的方向。若Cxf)(，则0)(xf，即0 C bxbT)(xxxT2)(QxQxxT2)(5)Hessian 矩阵(1)向量值函数的导数 设g是 定 义 在nR中 区 域 上 的 向 量 值 函 数,如 果)(xg的

12、 所 有 分 量)(),.(),(21xgxgxgm在0 x点都可微，那么向量值函数)(xg在点0 x处称为可微。若)(xg在点0 x处可微，则对于任意的 n 维向量p都有 约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对

13、称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备 欢迎下载 0)()()(lim0000ppxgxgpxgTiiip 因为向量的极限是通过它所有分量的极限来定义的，所以上式等价于 0)()()(lim0000ppxgxgpxgp 其中)(0 xg称为函数)(xg在点0 x处的导数。也称函数)(xg在点0 x处的 Jacobi矩阵。nmmmnnmxxgxxgxxgxxgxxgxxgxxgxxgxxggggxg)(.)()(.)(.)()()(.)()(.)(

14、020100220210012011012102 设nm，并且)()(xfxg，其中)(xf是 n 元函数，假定它具有二阶连续偏导数。则：22221222222212121222122)(.)()(.)(.)()()(.)()()()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxfxf 在 微 积 分 中 已 经 证 明 过，当)(xf的 所 有 二 阶 偏 导 数 连 续 时，有ijjixxxfxxxf)()(22，在这种情况下，Hessen矩阵是对称的。(2)几个特殊向量的导数 Oc,其中c是分量全为常数的n维向量，O是nn阶零矩阵。Ix，约束记为其中满足

15、所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备

16、欢迎下载 QQx)(3)()(0tpxft的一二阶导数 设)0()0(2)0(10.,nxxxx ).,()()0(2)0(21)0(1nntpxtpxtpxft ptpxfpxtpxftTinii)()()(010 ptpxfpppxxtpxfpxtpxfdtdtTnininjijijii)()()()(02111020 5.多元函数的 Taylor 展开式 定理:设f是定义在nR中区域上的实值函数，具有二阶连续偏导数，则：pxfppxfxfpxfTT)(21)()()(2 其中pxx，而10 证明：设)()(tpxft，于是)()1(),()0(pxfxf 按一元函数Taylor 展开定理

17、把)(t在0t点展开，得到 2)(21)0()0()(tttt，其中10。ptpxftT)()(0，因此pxfT)()0(0 ptpxfptT)()(02，因此ppxfpT)()(02 代入上式，即得证。多元函数的 Taylor 展开式还可写为：)()(21)()()(22pOpxfppxfxfpxfTT 6.极小点及其判定条件 1)基本定义 约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无

18、约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备 欢迎下载 邻域定义：对于任意给定的实数0,满足不等式0 xx的的 x 的集合称为点0 x的邻域，记为0,:),(00 xxxxN 非严格局部极小点：设1:RRDfn，若存在点Dx*和数0，DxNx),(*都有)()(*xfxf，则称*x为

19、)(xf的非严格局部极小点。严 格 局 部 极 小 点：设1:RRDfn，若 存 在 点Dx*和 数0，DxNx),(*但*xx 都有)()(*xfxf，则称*x为)(xf的严格局部极小点。非严格全局极小点：设1:RRDfn，若存在点Dx*和数0，Dx都有)()(*xfxf，则称*x为)(xf的非严格全局极小点。严格全局极小点：设1:RRDfn，若存在点Dx*和数0，Dx都有)()(*xfxf，则称*x为)(xf的严格全局极小点。在求解最优化问题时，要求求取全局极小点，可先求出所有的局部极小点，再求全局极小点。2)局部极小点的判定条件 定理 1:设1:RRDfn具有连续的一阶偏导数。若*x是)

20、(xf的局部极小点并且是 D 的内点，则0)(*xf。证明：设e是任意单位向量。因为*x是)(xf的局部极小点，所以存在0，当t或),(*xNtex时总有)()(*xftexf 引入一元辅助函数)()(*texft 又因为*x是 D 的内点，所以与它对应的0t是)(t的局部极小点。根据一元函数极小点的必要条件，得0)0(，即0)(*exf。由单位向量的任意性，得到0)(*xf 该条件仅仅是必要的，而不是充分的。约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的

21、目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备 欢迎下载 定义:设1:RRDfn，*x是 D 的内点。若0)(*xf，则*x称为)(xf的驻点。定理 2:设1:RRDfn具有连续的二阶偏导数，*x是 D 的内点。若0)

22、(*xf并且)(*2xf是正定的，则*x是)(xf的严格局部极小点。证明：将)(xf在点*x处按 Taylor 公式展开得：)()()(21)()()(2*2*xxOxxxfxxpxfxfxfTT 由于0)(*xf，故有)()()(21)()(2*2*xxOxxxfxxxfxfT 显而易见，当x充分接近*x时，上式左端的符号取决于右端的第一项，因此有：)()(*xfxf。一般说来，这个定理仅具有理论意义。因为对于复杂的目标函数，Hesse 矩阵不易求得，它的正定性就更难判定了。论断 1:对于具有对称正定矩阵Q二次函数cxbQxxxfTT21)(，bQx1*是它唯一的极小点 证明：令0)(bQx

23、xf bQx1*在该点处Qxf)(*2正定。命题得证。7.下降迭代算法及其收敛性 迭代算法的必要性：求解)(minxfnRx的问题可转化为0)(xf，一般地，这是一个非线性方程组，与原问题同等困难，为了避开这一难题，可对原有问题直接采用迭代法。约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的

24、方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备 欢迎下载 1)下降迭代算法 首先给定目标函数)(xf的极小点一个初始估计点0 x，然后按一定的规则产生一个序列kx，这种规则通常称为迭代算法。2)降迭代算法的收敛性 如果迭代算法产生的序列的极限恰好是函数)(xf的极小点，称迭代算法产生的序列收敛于*x。3)迭代过程 选定初始点0 x，置0k。按某种规则确定搜索方向kp，使得0)(kTkp

25、xf。按某种规则确定搜索步长kt，使得)()(kkkkxfptxf 计算kkkkptxx 1 若1kx满足终止准则，停机，否则置1 kk，转。4)迭代法中直线搜索 求 一 元 函 数 极 小 点 的 迭 代 法 称 为 直 线 搜 索 或 一 维 搜 索，即)(min)(kkttpxft。记为),(pxlsz，表示从点x出发沿p方向对目标函数)(xf作直线搜索得到的极小点是z。定理：若目标函数)(xf具有连续的偏导数，并且设),(pxlsz，则0)(pzfT。这个定理表明，梯度)(zf必与搜索方向p正交。5)收敛速度 定义 1:对收敛于解*x的序列kx，若存在一个与k无关的数)1,0(，当k从

26、某个0k开始使下式成立：*1xxxxkk 则称序列kx为线性(或一阶)收敛。约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的

27、若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称学习必备 欢迎下载 定义 2:对收敛于解*x的序列kx，若存在一个与k无关的数0和1，当k从某个0k开始使下式成立：*1xxxxkk 则称序列kx收敛的阶为，或称阶收敛。当2时，称为二阶收敛。当21时，称为超线性收敛。一般说来，线性收敛是比较慢的，而二阶收敛则是很快的，超线性收敛居中，如果一个算法具有超线性以上的收敛速度，我们就认为它是一个很好的算法了。6)计算终止准则 11kkkfff&21kkkxxx&3)(kxf 习题：1.设目标函数为cxbQxxxfTT21)(其中Q为nn对称正定阵。试证：从任意点0 x

28、(但0)(0 xf)出发沿)(01xfQp的方向对)(xf作直线搜索所得的极小点Z恰是)(xf的极小点，而且最优步长因子等于 1。2.设1:RRfn在点0 x处可微，并设nppp,.,21是nR中线性无关向量组，试证：若),(00ipxlsx，ni,.,2,1 则0)(0 xf。问这是否意味着0 x是f的局部极小。约束记为其中满足所有约束的向量称为容许解或容许点容许点集合称为容许集从最优化问题的一般形式可以看出最优化要解决的问题就是在容许集中找一点使目标函数在该点取极小这样称为问题的最优点而相应的目标函数值称为最无约束问题和约束问题两类例求函数大极小点即这是一个无约束二维问题例求优化问题的最优解这是一个约束最优化问题无约束问题又可分为一维问题及维问题求解一维问题的方法称为一维学习必备欢迎下载搜索或直线搜索在最优矩阵形式是其中这里是对称矩阵我们称特殊的二次函数为二次型无一次项和常数项正定矩阵设是阶对称矩阵若且时都有则称矩阵是正定的若都有则称矩阵是半正定的若且时都有则称矩阵是负定的若都有则称矩阵是半负定的一个对称