工程优化演示文稿

工程优化演示文稿目前一页\总数八十九页\编于五点多元函数的梯度及其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方向是上升的。引进方向导数当t＞0充分小时，有目前十二页\总数八十九页\编于五点

若则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),可能与S有一个交点(f0=0),可能与S交成一条曲线(f0>0).等高线目前二十四页\总数八十九页\编于五点我们感兴趣的是至少有一个交点（）的情形。定义（等值线）：平面L截曲面S得到一个圆，将它投影到平面上，仍为同样大小的圆。在这个圆上每一点的目标函数值均为f0,若一条曲线上任何一点的目标函数值等于同一常数，则称此曲线为目标函数的等值线。变动f的值，得到不同等值线，这是一组同心圆：对应f0=0的等值线缩为一点G，对应f0<0的等值线为空集。随着f值变小，等值线圆半径变小，最后缩为一点，即为问题的最小值点G，即等高线目前二十五页\总数八十九页\编于五点例2用图解法求解解：先画出目标函数等值线，再画出约束曲线。对应的最优值为由图易见约束直线与等值线的切点是最优点，利用解析几何的方法得该切点为本处约束曲线是一条直线，这条直线就是可行域；而最优点就是可行域上使等值线具有最小值的点.等高线目前二十六页\总数八十九页\编于五点

定义（等值面）：在三维和三维以上的空间中，使目标函数取同一常数值的面{x|f(x)=r,r是常数}称为目标函数的等值面。

等值面的性质：(1)不同值的等值面之间不相交，因为目标函数是单值函数。(2)除了极值点所在的等值面外，不会在区域内部中断，因为目标函数是连续的。(3)等值面稠的地方，目标函数值变化得较快，而稀疏的地方变化得比较慢。(4)一般地，在极值点附近，等值面（线）近似地呈现为同心椭球面族（椭圆族）。(5)二次函数的等值面是同心椭球面族，极值点是这个椭球面族的共同中心。

目前二十七页\总数八十九页\编于五点

在n元函数中，除了线性函数：

或二次函数最简单最重要的一类就是二次函数。目前二十八页\总数八十九页\编于五点定义（二次型）：代数学中将特殊的二次函数称为二次型。二次函数的一般形式为

其中均为常数，其向量矩阵表示形式是：其中Q为对称矩阵二次函数目前二十九页\总数八十九页\编于五点定义：设Q为n×n对称矩阵,若，均有，则称矩阵Q是正定的。若，均有，则称矩阵Q是半正定的。若-Q是正定的，则称Q是负定的。若-Q是半正定的，则称Q是半负定的。对于二次函数，我们更关心的是Q为正定矩阵的情形。正定二次函数目前三十页\总数八十九页\编于五点A是正定矩阵的充要条件有以下4条：存在非奇异矩阵G,使得A=GTG;

A的所有特征根大于零;有满秩矩阵G，使A=GTG;

A的所有顺序主子式都大于零.怎么判定一个对称矩阵Q是不是正定的？Sylvester（西尔维斯特

）定理：一个n×n对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶顺序主子式都是正的。二次函数----正定矩阵目前三十一页\总数八十九页\编于五点解：对称矩阵Q的三个顺序主子式依次为：例：判定矩阵是否正定:二次函数----正定矩阵矩阵Q是正定的。目前三十二页\总数八十九页\编于五点证明：作变换,代入二次函数式中：

根据解析几何知识，Q为正定矩阵的二次型的等值面是以坐标原点为中心的同心椭球面族。由于上式中的是常数，所以的等值面也是以为中心的同心椭球面族，回到原坐标系中去，原二次函数就是以为中心的同心椭球面族。这族椭球面的中心恰是二次目标函数的唯一极小点。定理：若二次函数中Q正定，则它的等值面是同心椭球面族，且中心为.椭球面y12+3y22+4y32=6正定二次函数的极小点目前三十三页\总数八十九页\编于五点

前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次函数有效的求极小点的算法，当用于一般函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。特别地，若算法对于Q为正定的二次函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。正定二次函数判断算法好坏目前三十四页\总数八十九页\编于五点解：展开例：把二次函数化为矩阵向量形式并检验Q是否正定，如正定，试用公式求这个函数的极小点。与题中函数比较各项系数为：正定二次函数的极小点----算例目前三十五页\总数八十九页\编于五点由前例知正定,极小点是目前三十六页\总数八十九页\编于五点对于一个极小化问题，我们希望知道的是全局极小点，而到目前为止的一些最优化算法却基本上是求局部极小值点的。因此一般要先求出所有局部极小值点，再从中找出全局极小点。

为了求出函数的局部极小值点，考察函数f在局部极小点处满足什么条件？反过来，满足什么条件的点是局部极小点？这就是我们要下来要考虑的多元函数的极值条件。首先回顾二元函数的极值条件。多元函数的极值目前三十七页\总数八十九页\编于五点二元函数的极值判别条件定理1(必要条件)（可微的极值点一定是驻点）：

设(1)为D的一个内点;可微;(2)在处,则在的极值点;(3)为目前三十八页\总数八十九页\编于五点二元函数的极值判别条件定理2(充分条件)

设(1)为D的一个内点;二次连续可微;(2)在的驻点，即(3)为(i)若且为则的严格局部极小点；目前三十九页\总数八十九页\编于五点(ii)

若,且为则的严格局部极大点；(iii)若则不是的极值点,此时称的鞍点.为目前四十页\总数八十九页\编于五点多元函数的极值判别条件定理3(必要条件)

设(1)x*为D的一个内点;可微;(2)在则的极值点;(3)为目前四十一页\总数八十九页\编于五点设为任意单位向量,因为是的局部极小点。由定义知：当,即时，总有：令（一元辅助函数）则上式即为：而是D的内点。从而与之对应的t=0是的局部极小点。根据一元函数极小点必要性条件知：,而由前述性质知：则,由单位向量任意性，即知。（否则，取，则，矛盾。）证明:目前四十二页\总数八十九页\编于五点多元函数的极值判别条件注意：定理中条件仅为必要的，而不是充分的。例：在处梯度为，但只是双曲抛物面的鞍点，而不是极小点。（可微的极值点一定是驻点）定义：设是D的内点，若,则称为f的驻点。f定理3(必要条件)

设(1)x*为D的一个内点;可微;(2)在则的极值点;(3)为目前四十三页\总数八十九页\编于五点多元函数的极值判别条件定理4(充分条件)

设(1)x*为D的一个内点;(2)二次连续可微;在(3)则的严格局部极小点。为(4)正定；目前四十四页\总数八十九页\编于五点证明：因正定，则使对，均有：（x充分接近时）。将f在处按Taylor公式展开注意,有：当x充分接近时，上式左端的符号取决于右端的一项（为正）。故目前四十五页\总数八十九页\编于五点推论1:对于对称正定矩阵的二次函数：是它的唯一极小点。证明:求此二次函数的驻点,由,知有唯一驻点,而这点处的Hesse阵正定,故由定理可知：是其唯一极小点。

定理4(充分条件)

设(1)x*为D的一个内点;(2)二次连续可微;在(3)则的严格局部极小点。为(4)正定；多元函数的极值判别条件目前四十六页\总数八十九页\编于五点证明：设是多元函数f的极小点。并设是充分靠近极小点的一个等值面，即充分小。将在点展开因为极小值点,则

这是等值面的一个近似曲面。由于假设正定，则

是以为中心的椭球面方程。推论2:若多元函数在其极小点处的Hesse阵正定，则它在这个极小点附近的等值面近似地呈现为同心椭球面族。定理4(充分条件)

设(1)x*为D的一个内点;(2)二次连续可微;在(3)则的严格局部极小点。为(4)正定；又是高阶无穷小量,目前四十七页\总数八十九页\编于五点定义（可行方向）：设，若对以点为始点的向量均位于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)是凸的。为研究多元函数的极值与最值的关系，下面介绍多元函数凸性。目前四十九页\总数八十九页\编于五点规定：空集和单元素集也是凸集。三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸的。等价定义（凸集）：设凸集与性质

定义（凸集）：若集合中任意两点的连线都属于，则称为凸集。因为两点

连线上任一点可以表示为

凸集的几何特征凸集的代数特征称集合为凸集。恒有目前五十页\总数八十九页\编于五点凸集：在点集中任取两点，则其连线仍在其中。即没有凹入的部分；没有空洞。⑴⑵⑶⑷⑸⑹ABCD凸集与性质

目前五十一页\总数八十九页\编于五点

例1:证明集合S={x∣Ax=b}是凸集。其中A为mn矩阵，b为m维向量。凸集与性质

证明:即所以即S是凸集。例2:集合是凸集,称为超平面，c为n维向量。例3：邻域是凸集。目前五十二页\总数八十九页\编于五点定义：设那么称是

的凸组合。

性质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的方程：令则上式可写为：所以：

目前五十六页\总数八十九页\编于五点定义（凸函数）:设集合DRn为凸集，函数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的证明。目前五十九页\总数八十九页\编于五点P382.12.32.19作业目前六十页\总数八十九页\编于五点定理(一阶条件):设D

Rn为非空凸集，函数f:DR在D上可微，则(1)f在D上为凸函数任意x，yD，恒有

f(y)

≥f(x)+fT(x)(y-x)

(1)(2)f在D上为严格凸函数任意x≠yD，恒有

f(y)>f(x)+fT(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)+fT(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-1b≥0,xN=0.S中必存在有限多个极点。(≤Cnm)定理（极方向特征）设A=[p1,p2,…,pn]满秩，d是S极方向的充分必要条件是:存在分解A=[B,N]，其中B为m阶非奇异矩阵，对于N中的列向量pj使B-1pj≤0,dT=[dBT,dNT],dB=-B-1pj

,

dN=(0,...,1,…,0)TS中必存在有限多个极方向。(≤(n-m)Cnm)多面体S={xRnAx=b,x≥0}的极点和极方向目前七十二页\总数八十九页\编于五点定理（表示定理）考虑上述多面体S，设A满秩，

为所有极点，

为所有极方向。那么，对于xS，且多面体S={xRnAx=b,x≥0}的极点和极方向使目前七十三页\总数八十九页\编于五点一个凸集有非空的相对内部；一个凸集是连通的并且在任意点具有可行方向；一个多面体的凸集可以由一个有限的极点和极方向的集合来刻画；凸集上凸函数的全局极小值的存在可以非常方便的按照收缩方向来描述；为什么凸在最优化中如此特殊目前七十四页\总数八十九页\编于五点一个凸函数的局部极小点都是全局极小点；一个非凸函数可以被“凸化的”同时保持了全局极小值的最优性；一个凸函数是连续的并且具有良好的可微性；闭凸锥关于极是自对偶的；凸且下半连续的函数关于共轭是自对偶的；为什么凸在最优化中如此特殊目前七十五页\总数八十九页\编于五点向量运算：x,yRn

x,y的内积：<x,y>=xTy=xiyi=x1y1+x2y2+…+xnyn

x,y的距离：‖x-y‖=[(x-y)T(x-y)](1/2)x的长度：‖x‖=[xTx](1/2)三角不等式：‖x+y‖≤‖x‖+‖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相关联并记做的一个非负数，它具有下列性质：对于都有，而时；对于任意，都有；；；若还进一步满足：则称之为与向量范数相协调（相容）的方阵范数.

范数