工程优化第2章.ppt

多元函数的梯度及其Hesse矩阵等高线二次函数多元函数的极值及其判别条件凸集、凸函数、凸规划几个重要的不等式,第2章 基础知识,多元函数的梯度及其Hesse矩阵,n元函数：,n元线性函数：,n元二次函数：,n元向量值线性函数：,其中,在点,存在,的偏导数，记为,的某邻域内极限,则称此极限为函数,设函数,在点,对第i个分量,注意:(1)式也可写为,其中,定义(偏导数),多元函数的偏导数,可表示成,其中 A,B 不依赖于 x1,x2,仅与 x1,x2 有关，,称为函数,在点(x1,x2)的全微分,记作,若函数在域 D 内各点都可微,则称函数,f(x1,x2)在点(x1,x2)可微，,则称此函数在D 内可微.,定义（可微）:高数中二元函数的可微性定义：如果函数 z=f(x1,x2)在定义域 D 的内点(x1,x2)处全增量,二元函数的可微性,定义中增量的表达式,等价于,记,定义(可微):高数中二元函数的可微性定义：,二元函数的可微性,定理（可微必可导）若函数 z=f(x1,x2)在点(x1,x2)可微，则 该函数在该点偏导数,必存在,即,称向量 是函数 z=f(x1,x2)在点(x1,x2)的梯度。,且有,二元函数的可微性,二元,多元,可微,定义（多元函数的可微性）：设 若 使 有：则称 f(x)在 处可微。,给定区域D上的 n 元实值函数,与二元函数可微的等价形式类似引入,多元函数的可微性,定理（可微必可导）:若 在 处可微，则 在该点处关于各变量的一阶偏导数存在，且,证明：令，依次取,多元函数的可微性,两边除以 并取 的极限有：,在 处可微，则(3)对 成立，,定义（梯度）:以 的 n 个偏导数为分量的向量称为 f(x)在x 处的梯度。,若 f 在 处可微,令p=x-x0,由 得,记为,梯度也可称为函数 f(x)关于向量x 的一阶导数。,这与一元函数展开到两项的 Taylor 公式是相对应的。,多元函数的梯度,性质1:函数在某点的梯度不为零，则必与过该点的等值面垂 直。性质2:梯度方向是函数具有最大变化率的方向。性质1的证明:过点 的等值面方程为：,设 f(x)在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质：,多元函数梯度的性质,设 是过点 同时又完全在等值面（6）上的任一条光滑曲线L的方程，为参数，点 对应的参数就是,把此曲线方程代入(6),得到,即函数f(x)在 处的梯度 与过该点在等值面上的任一条曲线L在此点的切线垂直。从而与过该点的切平面垂直，性质1成立。,两边同时在 处关于 求导数，根据求导的链式法则有：,向量 恰为曲线 L 在 处的切向量，,则,定义(方向导数):设 在点x处可微，p=te为固定向量，其中t是向量p的模，e 为向量 p的单位向量，则称极限：,注：若 则f(x)从 出发在 附近沿p方向是下降的。,为说明性质2:梯度方向是函数具有最大变化率的方向,多元函数梯度的性质,为函数f(x)在点 处沿方向p的方向导数，记为，,若 则f(x)从 出发在 附近沿p方向是上升的。,引进方向导数,当t0充分小时，有,若 则f(x)从 出发在 附近沿p方向是下降的。,多元函数梯度的性质,若 则f(x)从 出发在 附近沿p方向是上升的。,方向导数正负决定了函数升降;升降速度的快慢由方向导数绝对值大小来决定，绝对值越大升降速度越大;因此又将方向导数 称为f(x)在 处沿方向p的变化率。,定理2：若 在点 处可微，则 其 中e 为p方向上的单位向量。,证明：f在 可微，则根据可微定义，,容易看到：当 时，有 由前面证明即知 p 为下降方向。,利用方向导数定义并将上式中的 p 换成 te 有：,多元函数梯度的性质,由于,为方向 p 与 的夹角。,从而梯度方向是函数具有最大变化率的方向，性质2成立。,推论：若，则 p 是函数 f(x)在 处的下降方向。若，则 p 是函数 f(x)在 处的上升方向。,多元函数梯度的性质,当夹角为0(=0o)，即沿梯度方向()时，方向导数取得最大值；,当夹角为180o(=180o)，即沿负梯度方向()时，方向导数取得最小值。,可见梯度方向即为函数的最速上升方向；负梯度方向即为函数的最速下降方向。,上升方向,变化率为0方向,下降方向,我们有结论：函数在与其梯度 正交的方向上变化率为 0；成锐角的方向上是上升的；成钝角的方向上是下降的。,多元函数梯度的性质,解：由于 则函数在 处的最速下降方向是,此方向上的单位向量是：,新点是,例1：试求目标函数 在点 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。,几个常用的梯度公式：,多元函数的一阶导数即梯度，二阶导数即Hesse阵,多元函数的Hesse矩阵,下面几个梯度和Hesse阵公式是今后常用到的：,多元函数的Taylor展开公式,设 二阶可导。在x*的邻域内,Lagrange余项：对x,记xx*+(x-x*),一阶Taylor展开式,二阶Taylor展开式：,一阶中值公式：对x,使,作业,等高线,例1.求解这是定义在 平面 上的无约束极小化问题，其目标函数在 三维空间中代表一个曲面。,二元函数最优化问题，具有明显的几何特征，从几何图形上，可以直观了解函数的变化，我们把这种几何解释推广到n维空间中，对后面优化方法的研究是有益处的。,0 s s L在 平面上任给一点，就对应有一个目标函数值 是过 点作 平面的垂线与S曲面交点的纵坐标。反之，任给一个值f0,使目标函数f(z)取值为f0的点z的个数就 不相同了。可能没有，可能只有一个，可能有多个。这一事实的几何意义是：过 f 轴上坐标为f0的点作 坐标 平面的平行平面L，可能与曲面S无交点(f0 0).,等高线,我们感兴趣的是至少有一个交点（）的情形。定义（等值线）：平面L截曲面S得到一个圆，将它投影到 平面上，仍为同样大小的圆。在这个圆上每一点的目标 函数值均为f0,若一条曲线上任何一点的目标函数值等于同一常数，则称此曲线为目标函数的等值线。变动 f 的值，得到不同等值线，这是一组同心圆：对应f0=0的等值线缩为一点G，对应f00的等值线为空集。随着 f 值变小，等值线圆半径变小，最后缩为一点，即为问题的最小值点 G，即,等高线,例2 用图解法求解,解：先画出目标函数等值线，再画出约束曲线。,对应的最优值为,由图易见约束直线与等值线的切 点是最优点，利用解析几何的方法得该切点为,本处约束曲线是一条直线，这条直线就是可行域；而最优点就是可行域上使等值线具有最小值的点.,等高线,定义（等值面）：在三维和三维以上的空间中，使目标函数取同一常数值的面 x|f(x)=r,r是常数 称为目标函数的等值面。等值面的性质：(1)不同值的等值面之间不相交，因为目标函数是单值函数。(2)除了极值点所在的等值面外，不会在区域内部中断，因为目 标函数是连续的。(3)等值面稠的地方，目标函数值变化得较快，而稀疏的地方变 化得比较慢。(4)一般地，在极值点附近，等值面（线）近似地呈现为同心椭 球面族（椭圆族）。(5)二次函数的等值面是同心椭球面族，极值点是这个椭球面族的共同中心。,在n元函数中，除了线性函数：或,二次函数,最简单最重要的一类就是二次函数。,定义（二次型）：代数学中将特殊的二次函数 称为二次型。,二次函数的一般形式为,其中 均为常数，,其向量矩阵表示形式是：,其中,Q 为对称矩阵,二次函数,定义：设Q为nn对称矩阵,若，均有，则称矩阵Q是正定的。若，均有，则称矩阵Q是半正定的。若-Q是正定的，则称Q是负定的。若-Q是半正定的，则称Q是半负定的。,对于二次函数，我们更关心的是Q为正定矩阵的情形。,正定二次函数,A是正定矩阵的充要条件有以下4条：存在非奇异矩阵G,使得 A=GTG;A的所有特征根大于零;有满秩矩阵G，使A=GTG;A的所有顺序主子式都大于零.,怎么判定一个对称矩阵Q是不是正定的？,Sylvester（西尔维斯特）定理：一个nn对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶顺序主子式都是正的。,二次函数-正定矩阵,解：对称矩阵Q的三个顺序主子式依次为：,例：判定矩阵是否正定:,二次函数-正定矩阵,矩阵Q是正定的。,证明：作变换,代入二次函数式中：根据解析几何知识，Q为正定矩阵的二次型 的等值面是以坐标原点 为中心的同心椭球面族。由于上式中的 是常数，所以 的等值面也是以 为中心的同心椭球面族，回到原坐标系中去，原二次函数就是以 为中心的同心椭球面族。这族椭球面的中心 恰是二次目标函数的唯一极小点。,定理：若二次函数 中Q正定，则它的 等值面是同心椭球面族，且中心为.,椭球面y12+3y22+4y32=6,正定二次函数的极小点,前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次函数有效的求极小点的算法，当用于一般函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。特别地，若算法对于Q为正定的二次函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。,正定二次函数判断算法好坏,解：展开,例：把二次函数 化为矩阵向量形式并检验Q是否正定，如正定，试用公式 求这个函数的极小点。,与题中函数比较各项系数为：,正定二次函数的极小点-算例,由前例知 正定,极小点是,对于一个极小化问题，我们希望知道的是全局极小点，而到目前为止的一些最优化算法却基本上是求局部极小值点的。因此一般要先求出所有局部极小值点，再从中找出全局极小点。,为了求出函数的局部极小值点，考察函数 f 在局部极小点处满足什么条件？反过来，满足什么条件的点是局部极小点？,这就是我们要下来要考虑的多元函数的极值条件。首先回顾二元函数的极值条件。,多元函数的极值,二元函数的极值判别条件,定理1(必要条件)（可微的极值点一定是驻点）：,设,(1)为D的一个内点;,二元函数的极值判别条件,定理2(充分条件),设,(1)为D的一个内点;,(iii)若,多元函数的极值判别条件,定理3(必要条件),设,(1)x*为D的一个内点;,则,设 为任意单位向量,因为 是 的局部极小点。由定义知：当,即 时，总有：,令（一元辅助函数）则上式即为：而 是D的内点。从而与之对应的t=0是 的局部极小点。根据一元函数极小点必要性条件知：,而由前述性质知：则,由单位向量任意性，即知。（否则，取，则，矛盾。）,证明:,多元函数的极值判别条件,注意：定理中条件仅为必要的，而不是充分的。,例：在 处梯度为，但 只是双曲抛物面的鞍点，而不是极小点。,（可微的极值点一定是驻点）,定义：设 是 D 的内点，若,则称 为f 的驻点。,f,定理3(必要条件),设,(1)x*为D的一个内点;,则,多元函数的极值判别条件,定理4(充分条件),设,(1)x*为D的一个内点;,(3),证明：因 正定，则 使对，均有：,（x 充分接近 时）。,将 f 在 处按Taylor公式展开,上式左端的符号取决于右端的,一项（为正）。,故,推论1:对于对称正定矩阵 的二次函数：是它的唯一极小点。,证明:求此二次函数的驻点,由,知有唯 一驻点,而这点处的Hesse阵 正定,故由定理可知：是其唯一极小点。,多元函数的极值判别条件,证明：设 是多元函数 f 的极小点。并设 是充分靠近极小点 的一个等值面，即 充分小。将 在 点展开因 为极小值点,则 这是等值面 的一个近似曲面。由于假设 正定，则 是以 为中心的椭球面方程。,推论2:若多元函数在其极小点处的 Hesse 阵正定，则它在这个极小点附近的等值面近似地呈现为同心椭球面族。,又 是高阶无穷小量,定义（可行方向）：设，若 对 以点 为始点的向量 均位于D 的内部，则称 为点 的一个可行方向。,注：(1)如果 为D 的内点，则任何方向 都是可行方向；若 为D 的边界点，则只有一部分为可行方向;(2)如果 为 的极小点,则 在 处沿任何可行方向，函数值均不减少，即,定理5：设,如果 二阶可微，且对于在点 的任何可行方向，都有，并有 正定，则 是严格局部极小值点。,凸集、凸函数和凸规划,问题（极小值点和最小值点之间的关系）：设f(x)定义在D内，f(x*)为极小值，这是一局部概念，即在x*的邻域内，f(x*)最小。若x*为f(x)的最小值点，则x*为f(x)的极小值点。反过来不一定成立。,一元函数有结论：若f(x)在区间a,b上是凸的，则x*是f(x)的极小值点等价于x*是f(x)的最小值。且由微分学知：若，则f(x)是凸的。,为研究多元函数的极值与最值的关系，下面介绍多元函数凸性。,规定：空集和单元素集也是凸集。三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸的。,等价定义（凸集）：设,凸集与性质,定义（凸集）：若集合 中任意两点的连线都属于，则称 为凸集。,因为两点 连线上任一点可以表示为,凸集的几何特征,凸集的代数特征,称集合 为凸集。,恒有,凸集：在点集中任取两点，则其连线仍在其中。,即没有凹入的部分；没有空洞。,A,B,C,D,凸集与性质,例1:证明集合 S=xAx=b 是凸集。其中A为 mn矩阵，b为m维向量。,凸集与性质,所以,即S是凸集。,定义：设 那么称 是 的凸组合。,性质2：S 是凸集 S 中任意有限个点的凸组合属于 S。证明：见书中定理 2.9(P23).提示：充分性显然。必要性用数学归纳法。,凸集与性质,性质1：设 是凸集，则 也是凸集。,注：不一定是凸集。,性质3：分离与支撑：凸集边界上任意点存在支撑超平面 两个互相不交的凸集之间存在分离超平面,支撑,强分离,分离,非正常分离,凸集与性质,定义（凸包）：包含集合D的所有凸集的交集称为D的凸包，记 作Co(D)或者H(D).注：由性质1可知，Co(D)是包含D的最小凸集。,凸集与性质,0,定义（凸锥）：设，如果对任意的 及所有的，都有，则称 是一个锥。一个同时是凸集的锥，称为 凸锥。,多胞形：有限个点的凸包,由一元函数的几何图形知：f(x)是凸函数，任意给定曲线上两点A，B，则弦AB在与弧AB之上，用数学式子表示：,凸函数,弦AB的方程：,令,则,上式可写为：,所以：,定义（凸函数）:设集合 D Rn 为凸集，函数 f:DR,若 x,y D,(0,1)，均有 f(x+(1-)y)f(x)+(1-)f(y)，则称 f(x)为凸集 D 上的凸函数。若进一步有上面不等式以严格不等式成立，则称 f(x)为凸集 D 上的严格凸函数。当-f(x)为凸函数(严格凸函数)时，则称 f(x)为凹函数(严格凹函数)。,严格凸函数,凸函数,严格凹函数,凸函数-推广到多元函数,例：设,1)若A半正定，则 在 上是凸函数；2)若A正定，则 在 上是严格凸函数。,证明:,凸函数-推广到多元函数,性质2：设 f1,f2 是凸集D上的凸函数，设a,b 0,则af1+bf2 是凸函数；f(x)=max f1(x),f2(x)是凸函数。思考：af1-bf2 是否是凸函数？g(x)=min f1(x),f2(x)是否是凸函数？,凸函数的性质,性质1：f(x)为凸集 S 上的凸函数 S 上任意有限点的凸组合 的函数值不大于各点函数值的凸组合。证明参见文中定理2.10的证明。,P38 2.1 2.3 2.19,作业,定理(一阶条件):设D Rn 为非空凸集，函数 f:DR 在 D 上可微，则(1)f在D上为凸函数 任意x，yD，恒有 f(y)f(x)+f T(x)(y-x)(1)(2)f在D上为严格凸函数 任意xyD，恒有 f(y)f(x)+f T(x)(y-x).(2)证明:见书中定理 2.11(P27),凸函数的判定定理,定理5（二阶条件）:设D Rn 为含有内点的非空凸集，函数 f:DR在 D 上二次可微，则 a)f在D上为凸函数 xD，2f(x)半正定；b)若 xD，2f(x)正定，则f在D上为严格凸函数。证明:见书中定理2.12（P28）由一阶条件和多元函数的泰勒展开式可证。回忆：一个矩阵半正定充要条件是所有主子式非负；一个矩阵正定充要条件是所有顺序主子式为正。,凸函数的判定定理,例：设二次函数(1)：若 为半定矩阵，在 中为凸函数；(2)：若 为正定矩阵，在 中为严格凸函数。,例：判断f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函数？的顺序主子式都是正的，所以正定，因此f(x)在凸集D上是严格凸函数。,凸函数的判定定理,由于,故,证明,为凸函数。,也是凸函数。根据性质2，,为凸函数。,看下述各式是否成立：,证明：首先用定义证明 是凸函数，即对任意,和,例:试证明,为凹函数。,或,即,显然，不管 和 取什么值，总有,从而,用同样的方法可以证明,用一阶条件证明,只需证,任意选取两点,或,或,或,不管a1、a2、b1、b2取什么值，上式均成立，从而得证。,例:试证明,为凹函数。,其海赛矩阵处处负定，故,为(严格)凹函数。,下面用二阶条件证明:,由于,例:试证明,为凹函数。,定义（凸规划）:考虑如下非线性规划,当 都是凸函数时,称规划 为凸规划,凸规划,性质1:设(1)为凸规划，则 i)(1)的可行集R是凸集；ii)(1)的最优解集是凸集；iii)(1)的任何局部极小点都是全局极小点。证明：见书中定理 2.13.,性质2:设(1)为凸规划，若f(x)在非空可行集R上是严格凸函 数，则(1)的全局极小点是唯一的。证明：见书中定理 2.14.,注:非线性规划的局部最优解不一定是 整体最优解,其可行解和最优解集也 不一定是凸集,甚至不是连通集.如 果是凸规划,就有很多好的性质。,凸规划的性质,性质3：设(1)为凸规划，则 为(1)的最优解 的充要条件为：，有,利用 f(y)f(x)+f T(x)(y-x)（证明参见文中定理2.15）,凸规划的性质,多胞形：有限个点的凸包,闭半空间是凸的,多面体、极点、极方向,闭半空间：,H+和 H-统称为闭半空间。,多面体：有限个闭半空间的交,多面体的极点（顶点）：,多面体、极点、极方向,对任意 xS，不存在 S 中的另外两个点x(1)和x(2)，及,极方向：方向 d 不能表示为两个不同方向的组合,使,方向：,xS,dRn,d 0 及,总有,时，称 d(1)和d(2)同方向。,当,定理（极点特征）设 A 满秩，x 是 S 极点的充分必要 条件是:存在分解 A=B,N，其中B为m阶非奇异矩阵，使 xT=xBT,xNT,这里xB=B-1b0,xN=0.S中必存在有限多个极点。(Cnm),定理（极方向特征）设 A=p1,p2,pn满秩，d 是 S 极方向的充分必要条 件是:存在分解 A=B,N，其中B为m阶非奇异矩阵，对 于N中的列向量 pj 使 B-1pj0,dT=dBT,dNT,dB=-B-1pj,dN=(0,.,1,0)TS中必存在有限多个极方向。(n-m)Cnm),多面体 S=xRnAx=b,x0 的极点和极方向,定理（表示定理）考虑上述多面体S，设A满秩，为所有极点，为所有极方向。那么，对于 xS，且,多面体 S=xRnAx=b,x0 的极点和极方向,使,一个凸集有非空的相对内部；一个凸集是连通的并且在任意点具有可行方向；一个多面体的凸集可以由一个有限的极点和极方向的集合来刻画；凸集上凸函数的全局极小值的存在可以非常方便的按照收缩方向来描述；,为什么凸在最优化中如此特殊,一个凸函数的局部极小点都是全局极小点；一个非凸函数可以被“凸化的”同时保持了全局极小值的最优性；一个凸函数是连续的并且具有良好的可微性；闭凸锥关于极是自对偶的；凸且下半连续的函数关于共轭是自对偶的；,为什么凸在最优化中如此特殊,向量运算：x,y Rn x,y 的内积：=xTy=xiyi=x1y1+x2y2+xnyn x,y 的距离：x-y=(x-y)T(x-y)(1/2)x 的长度：x=xTx(1/2)三角不等式：x+yx+y,定理（Cauchy-Schwarz不等式）,重要的不等式,定理1 设A为 n 阶对称正定矩阵，则，恒有 等号成立当且仅当 x 与 线性相关;,等式成立当且仅当 x 与 y 线性相关。,其中 表示向量的内积。,定理3：设A为 n 阶对称正定矩阵，m与M分别为A的最小 与最大特征值，则，恒有,定理2：设A为 n 阶对称正定矩阵，m与M分别为A的最小 与最大特征值，则，恒有,重要的不等式,1/M与 1/m分别为A-1的最小与最大特征值,范数,（A正定）椭球范数,范数,范数,范数,范数-向量范数,定义1：方阵A的范数是指与A相关联并记做 的一个非负数，它具有下列性质：对于 都有，而 时；对于任意，都有；若还进一步满足：则称之为与向量范数 相协调（相容）的方阵范数.,范数-矩阵范数,定义2:设 与 是 上的两个范数，若存在，使得，则称范数 与 是等价的。容易证明：其中 是 的最大特征值，而 是 的最小特征值。,范数-范数等价,中所有向量范数均等价。,Cauchy-Schwarz不等式 当且仅当 与 线性相关时，等式成立。,关于范数的几个重要不等式,定理（Cauchy-Schwarz不等式）,等式成立当且仅当 x 与 y 线性相关。,当且仅当 与 线性相关时，等式成立。,关于范数的几个重要不等式,定理4：设A是正定矩阵，则,当且仅当 与 线性相关时，等式成立。,Cauchy-Schwarz不等式,设A是n阶正定矩阵，则 等号成立当且仅当 与 线性相关。,关于范数的几个重要不等式,定理1 设A为 n 阶对称正定矩阵，则，恒有 等号成立当且仅当 x 与 线性相关;,定理5：,Young不等式：假定p与q都是大于1的实数，且满 足，则，有 当且仅当 时，等式成立。,关于范数的几个重要不等式,Hlder不等式 其中p与q都是大于1的实数，且满足.Minkowski不等式,关于范数的几个重要不等式,定义3（序列收敛）：设 是 中的一个向量序列，如果，存在正整数K，使得当 时，有，则称序列收敛到；或称序列 以为极限，记.按此定义，序列若存在极限，则该序列的任何子序列有相同的极限，即序列的极限是唯一的.定义4（聚点）：设 是 中的一个向量序列，如果存在 一个子序列，使得,则称 是序列 的 一个聚点.,序列的极限,由极限的性质可知，如果无穷序列有界，则这个序列必有聚点.定义5（Cauchy列）：设 是 中的一个向量序 列，如果，存在正整数K，使得当 时，有，则称序列 为 Cauchy列.定理6：设 为Cauchy序列，则 的聚点必为极 限点.,序列的极限,作业,第一章：P8:1.1 第二章：P38:2.1 2.3 2.9-2.14 2.19 2.20(1,3)2.28 2.29,课件下载邮箱,(工程优化的小写全拼+12)密码：gongcheng123,