工程优化 第2章

1、多元函数的梯度及其Hesse矩阵 等高线 二次函数 多元函数的极值及其判别条件 凸集、凸函数、凸规划 几个重要的不等式,第2章 基础知识,多元函数的梯度及其Hesse矩阵,n元函数：,n元线性函数：,n元二次函数：,n元向量值线性函数：,其中,在点,存在,的偏导数，记为,的某邻域内极限,则称此极限为函数,设函数,在点,对第i个分量,注意:(1)式也可写为,其中,定义(偏导数),多元函数的偏导数,可表示成,其中 A , B 不依赖于 x1 , x2 , 仅与 x1 , x2 有关，,称为函数,在点 (x1, x2) 的全微分, 记作,若函数在域 D 内各点都可微,则称函数,f (x1, x2 )

2、 在点(x1,x2)可微，,则称此函数在D 内可微.,定义（可微）: 高数中二元函数的可微性定义： 如果函数 z = f(x1, x2)在定义域 D 的内点(x1,x2)处全增量,二元函数的可微性,定义中增量的表达式,等价于,记,定义(可微): 高数中二元函数的可微性定义：,二元函数的可微性,定理（可微必可导） 若函数 z = f (x1, x2) 在点(x1, x2) 可微，则 该函数在该点偏导数,必存在,即,称向量 是函数 z = f (x1, x2) 在点(x1, x2) 的梯度。,且有,二元函数的可微性,二元,多元,可微,定义（多元函数的可微性）：设 若 使 有： 则称 f(x) 在

3、处可微。,给定区域D上的 n 元实值函数,与二元函数可微的等价形式类似引入,多元函数的可微性,定理（可微必可导）: 若 在 处可微，则 在该点处关于各变量的一阶偏导数存在，且,证明：令 ，依次取,多元函数的可微性,两边除以 并取 的极限有：,在 处可微，则 (3) 对 成立，,定义（梯度）: 以 的 n 个偏导数为分量的向量称为 f(x) 在x 处的梯度。,若 f 在 处可微, 令p=x-x0, 由 得,记为,梯度也可称为函数 f(x)关于向量x 的一阶导数。,这与一元函数展开到两项的 Taylor 公式是相对应的。,多元函数的梯度,性质1: 函数在某点的梯度不为零，则必与过该点的等值面垂 直

4、。 性质2: 梯度方向是函数具有最大变化率的方向。 性质1的证明:过点 的等值面方程为：,设 f(x) 在定义域内有连续偏导数，即有连续梯度 ，则梯度有以下两个重要性质：,多元函数梯度的性质,设 是过点 同时又完全在等值面（6）上的任一条光滑曲线L的方程， 为参数，点 对应的参数就是,把此曲线方程代入(6),得到,即函数f(x) 在 处的梯度 与过该点在等值面上的任一条曲线L在此点的切线垂直。 从而与过该点的切平面垂直，性质1成立。,两边同时在 处关于 求导数，根据求导的链式法则有：,向量 恰为曲线 L 在 处的切向量，,则,定义(方向导数): 设 在点x处可微，p=te为固定向量， 其中t是

5、向量p的模，e 为向量 p的单位向量，则称极限：,注：若 则f(x) 从 出发在 附近沿p方向是下降的。,为说明性质2: 梯度方向是函数具有最大变化率的方向,多元函数梯度的性质,为函数f(x) 在点 处沿方向p的方向导数，记为，,若 则f(x) 从 出发在 附近沿p方向是上升的。,引进方向导数,当t0充分小时，有,若 则f(x) 从 出发在 附近沿p方向是下降的。,多元函数梯度的性质,若 则f(x) 从 出发在 附近沿p方向是上升的。,方向导数正负决定了函数升降; 升降速度的快慢由方向导数绝对值大小来决定，绝对值越 大升降速度越大; 因此又将方向导数 称为f(x) 在 处沿方向p的变化 率。,

6、定理2：若 在点 处可微， 则 其 中e 为p方向上的单位向量。,证明：f在 可微，则根据可微定义，,容易看到：当 时 ，有 由前 面证明即知 p 为下降方向。,利用方向导数定义并将上式中的 p 换成 te 有：,多元函数梯度的性质,由于 ,为方向 p 与 的夹角。,从而梯度方向是函数具有最大变化率的方向，性质2成立。,推论：若 ，则 p 是函数 f (x) 在 处的下降方向。 若 ，则 p 是函数 f(x) 在 处的上升方向。,多元函数梯度的性质,当夹角为0 (=0o) ，即沿梯度方向( )时， 方向导数取得最大值 ；,当夹角为180o (=180o) ，即沿负梯度方向( )时， 方向导数取

7、得最小值 。,可见梯度方向即为函数的最速上升方向； 负梯度方向即为函数的最速下降方向。,上升方向,变化率为0方向,下降方向,我们有结论： 函数在与其梯度 正交的方向上变化率为 0 ； 成锐角的方向上是上升的 ； 成钝角的方向上是下降的。,多元函数梯度的性质,解：由于 则函数在 处的 最速下降方向是,此方向上的单位向量是：,新点是,例1：试求目标函数 在点 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。,几个常用的梯度公式：,多元函数的一阶导数即梯度 ，二阶导数即Hesse阵,多元函数的Hesse矩阵,下面几个梯度和Hesse阵公式是今后常用到的：,多元函数的Taylor展

8、开公式,设 二阶可导。在x* 的邻域内,Lagrange余项：对x, , 记xx*+ (x-x*),一阶Taylor展开式,二阶Taylor展开式：,一阶中值公式：对x, , 使,P38 2.9-2.14,作业,等高线,例1. 求解 这是定义在 平面 上的无约束极小化问题，其目标函数 在 三维空间中代表一个曲面 。,二元函数最优化问题，具有明显的几何特征，从几何图形上，可以直观了解函数的变化，我们把这种几何解释推广到n维空间中，对后面优化方法的研究是有益处的。,0 s s L 在 平面上任给一点 ，就对应有一个目标函数值 是过 点作 平面的垂线与S曲面交点的纵坐标。 反之，任给一个值f0 ,使

9、目标函数f(z)取值为f0的点z的个数就 不相同了。可能没有，可能只有一个，可能有多个。 这一事实的几何意义是：过 f 轴上坐标为f0的点作 坐标 平面的平行平面L，可能与曲面S无交点(f0 0).,等高线,我们感兴趣的是至少有一个交点（ ）的情形。 定义（等值线）：平面L截曲面S得到一个圆，将它投影到 平面上，仍为同样大小的圆。在这个圆上每一点的目标 函数值均为f0, 若一条曲线上任何一点的目标函数值等于同一常数，则称此曲线为目标函数的等值线。 变动 f 的值，得到不同等值线，这是一组同心圆： 对应f0=0的等值线缩为一点G， 对应f00的等值线为空集。 随着 f 值变小，等值线圆半径变小，

10、最后缩为一点，即为问题的最小值点 G，即,等高线,例2 用图解法求解,解：先画出目标函数等值线，再画出约束曲线。,对应的最优值为,由图易见约束直线与等值线的切 点是最优点， 利用解析几何的方法得 该切点为,本处约束曲线是一条直线， 这条直线就是可行域； 而最优点就是可行域上 使等值线具有最小值的点.,等高线,定义（等值面）：在三维和三维以上的空间中，使目标函 数取同一常数值的面 x| f(x)=r, r是常数 称为目标函数的等 值面。 等值面的性质： (1) 不同值的等值面之间不相交，因为目标函数是单值函数。 (2) 除了极值点所在的等值面外，不会在区域内部中断，因为目 标函数是连续的。 (3

11、) 等值面稠的地方，目标函数值变化得较快，而稀疏的地方变 化得比较慢。 (4) 一般地，在极值点附近，等值面（线）近似地呈现为同心椭 球面族（椭圆族）。 (5)二次函数的等值面是同心椭球面族，极值点是这个椭球面族的共同中心。,在n元函数中，除了线性函数： 或,二次函数,最简单最重要的一类就是二次函数。,定义（二次型）：代数学中将特殊的二次函数 称为二次型。,二次函数的一般形式为,其中 均为常数，,其向量矩阵表示形式是：,其中,Q 为对称矩阵,二次函数,定义： 设Q为nn对称矩阵, 若 ，均有 ，则称矩阵Q是正定的。 若 ，均有 ，则称矩阵Q是半正定的。 若-Q是正定的，则称Q是负定的。 若-Q

12、是半正定的，则称Q是半负定的。,对于二次函数，我们更关心的是Q为正定矩阵的情形。,正定二次函数,A是正定矩阵的充要条件有以下4条： 存在非奇异矩阵G, 使得 A=GTG; A的所有特征根大于零; 有满秩矩阵G，使A=GTG ; A的所有顺序主子式都大于零.,怎么判定一个对称矩阵Q是不是正定的？,Sylvester（西尔维斯特 ）定理： 一个nn对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶顺序主子式都是正的。,二次函数-正定矩阵,解：对称矩阵Q的三个顺序主子式依次为：,例：判定矩阵是否正定:,二次函数-正定矩阵,矩阵Q是正定的。,证明：作变换 ,代入二次函数式中： 根据解析几何知识，Q为正定矩阵

13、的二次型 的 等值面是以坐标原点 为中心的同心椭球面族。由于上 式中的 是常数，所以 的等值面也是以 为中 心的同心椭球面族，回到原坐标系中去，原二次函数就是以 为中心的同心椭球面族。 这族椭球面的中心 恰是二次目标函数的唯一极小点。,定理： 若二次函数 中Q正定，则它的 等值面是同心椭球面族，且中心为 .,椭球面 y12+ 3y22+4y32=6,正定二次函数的极小点,前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。 由此可见对于二次函数有效的求极小点的算法，当用于一般函数时，至少在极小点附近同样有效。 因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的

14、二次函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。 特别地，若算法对于Q为正定的二次函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。,正定二次函数判断算法好坏,解：展开,例：把二次函数 化为矩阵向量形式并检验Q是否正定，如正定，试用公式 求这个函数的极小点。,与题中函数比较各项系数为：,正定二次函数的极小点-算例,由前例知 正定,极小点是,对于一个极小化问题，我们希望知道的是全局极小 点，而到目前为止的一些最优化算法却基本上是求局部极 小值点的。因此一般要先求出所有局部极小值点，再从中 找出全局极小点。,为了求出函数的局部极小值点，考察函数 f 在局部极

15、小点处满足什么条件？反过来，满足什么条件的点是局部极小点？,这就是我们要下来要考虑的多元函数的极值条件。首先回顾二元函数的极值条件。,多元函数的极值,二元函数的极值判别条件,定理1 (必要条件)（可微的极值点一定是驻点）：,设,(1) 为D的一个内点;,二元函数的极值判别条件,定理2 (充分条件),设,(1) 为D的一个内点;,(iii) 若,多元函数的极值判别条件,定理3 (必要条件),设,(1) x*为D的一个内点;,则,设 为任意单位向量, 因为 是 的局部极小点。 由定义知： 当 , 即 时，总有：,令 （一元辅助函数） 则上式即为： 而 是D的内点。从而与之对应的t=0是 的局部极小

16、点。 根据一元函数极小点必要性条件知： , 而由前述性质知： 则 , 由单位向量任意性，即知 。 （否则 ， 取 ， 则 ，矛盾。）,证明:,多元函数的极值判别条件,注意：定理中条件仅为必要的，而不是充分的。,例： 在 处梯度为 ， 但 只是双曲抛物面的鞍点，而不是极小点。,（可微的极值点一定是驻点）,定义：设 是 D 的内点，若 , 则称 为f 的驻点。,f,定理3 (必要条件),设,(1) x*为D的一个内点;,则,多元函数的极值判别条件,定理4 (充分条件),设,(1) x*为D的一个内点;,(3),证明：因 正定，则 使对 ，均有：,（x 充分接近 时）。,将 f 在 处按Taylor

17、公式展开,上式左端的符号取决于右端的,一项（为正）。,故,推论1: 对于对称正定矩阵 的二次函数： 是它的唯一极小点。,证明: 求此二次函数的驻点, 由 , 知有唯 一驻点 , 而这点处的Hesse阵 正定, 故由定理可知： 是其唯一极小点。,多元函数的极值判别条件,证明：设 是多元函数 f 的极小点。并设 是充分靠近极小点 的一个等值面，即 充分小。将 在 点展开 因 为极小值点 , 则 这是等值面 的一个近似曲面。 由于假设 正定，则 是以 为中心的椭球面方程。,推论2: 若多元函数在其极小点处的 Hesse 阵正定，则它在这个极小点附近的等值面近似地呈现为同心椭球面族。,又 是高阶无穷小

18、量,定义（可行方向）：设 ，若 对 以点 为始点的向量 均位于D 的内部，则称 为点 的一个可行方向。,注： (1) 如果 为D 的内点，则任何方向 都是可行方向；若 为D 的边界点，则只有一部分为可行方向; (2) 如果 为 的极小点, 则 在 处沿任何可行方向 ，函数值均不减少，即,定理5：设 ,如果 二阶可微，且对于在点 的任何可行方向 ，都有 ，并有 正定，则 是严格局部极小值点。,凸集、凸函数和凸规划,问题（极小值点和最小值点之间的关系）： 设f(x)定义在D内，f(x*)为极小值，这是一局部概念，即在x*的邻域内，f(x*)最小。若x*为f(x)的最小值点，则x*为f(x)的极小值

19、点。反过来不一定成立。,一元函数有结论： 若f(x)在区间a,b上是凸的，则x*是f(x)的极小值点等价于x* 是f(x)的最小值。 且由微分学知：若 ，则f(x)是凸的。,为研究多元函数的极值与最值的关系，下面介绍多元函数凸性。,规定：空集和单元素集也是凸集。 三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸的。,等价定义（凸集）：设,凸集与性质,定义（凸集）：若集合 中任意两点的连线都属于 ，则称 为凸集。,因为两点 连线上任一点可以表示为,凸集的几何特征,凸集的代数特征,称集合 为凸集 。,恒有,凸集：在点集中任取两点，则其连线仍在其中。,即没有凹入的部分；没有空洞。,A,B,

20、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).

21、 注：由性质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 上的凸函数。 若进一步有上面不等式以严格

22、不等式成立，则称 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：

23、 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在

24、 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上是严格凸函数。,凸函数的判定定理,由

25、于,故,证明,为凸函数。,也是凸函数。根据性质2，,为凸函数。,看下述各式是否成立：,证明：首先用定义证明 是凸函数，即对任意,和,例: 试证明,为凹函数。,或,即,显然，不管 和 取什么值，总有,从而,用同样的方法可以证明,用一阶条件证明,只需证,任意选取两点,或,或,或,不管a1、a2、b1、b2取什么值，上式均成立，从而得证。,例: 试证明,为凹函数。,其海赛矩阵处处负定，故,为(严格)凹函数。,下面用二阶条件证明:,由于,例: 试证明,为凹函数。,定义（凸规划）: 考虑如下非线性规划,当 都是凸函数时,称规划 为凸规划,凸规划,性质1: 设(1)为凸规划，则 i) (1)的可行集R是凸

26、集； 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）,凸规划的性质,多胞形：有限个点的凸包,闭

27、半空间是凸的,多面体、极点、极方向,闭半空间：,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 ),

28、定理（极方向特征） 设 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)T S中必存在有限多个极方向。( (n-m)Cnm ),多面体 S = xRnAx = b , x0 的极点和极方向,定理（表示定理）考虑上述多面体S， 设A满秩， 为所有极点， 为 所有极方向。那么，对于 xS， 且,多面体 S = xRnAx = b , x0 的极点和极方向,使,一个凸集有非空

29、的相对内部； 一个凸集是连通的并且在任意点具有可行方向； 一个多面体的凸集可以由一个有限的极点和极方向的集 合来刻画； 凸集上凸函数的全局极小值的存在可以非常方便的按照 收缩方向来描述；,为什么凸在最优化中如此特殊,一个凸函数的局部极小点都是全局极小点； 一个非凸函数可以被“凸化的”同时保持了全局极小值的 最优性； 一个凸函数是连续的并且具有良好的可微性； 闭凸锥关于极是自对偶的； 凸且下半连续的函数关于共轭是自对偶的；,为什么凸在最优化中如此特殊,向量运算：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正定）椭球范数,范数,范