最优化方法第2章课件.ppt

1、第第 二二 章章基本概念基本概念 和基本理论和基本理论 2 2.1 1 等等高高线线 二二元元函函数数最最优优化化问问题题，具具有有明明显显的的几几何何特特征征，从从几几何何图图形形上上，可可以以直直观观了了解解函函数数的的变变化化，我我们们把把这这种种几几何何解解释释推推广广到到 n n 维维空空间间中中，对对后后面面优优化化方方法法的的研研究究是是有有益益处处的的.例例 1 1：求求解解 2212min21xx 这这是是定定义义在在12ox x平平面面2R上上的的无无约约束束极极小小化化问问题题，其其目目标标函函数数：221221fZxx 在在12ox x f三三维维空空间间中中代代表表一

2、一个个曲曲面面 S S.n n n0 s s Ln在在 平面上任给一点平面上任给一点 ，就对应有一个目标函数值，就对应有一个目标函数值n这个值就是过这个值就是过 点作点作 平面的垂线与平面的垂线与S曲面交点的纵坐标。曲面交点的纵坐标。n 反之，任给一个值反之，任给一个值 ,使目标函数使目标函数 取值为取值为 的点的点z的的 个数就不相同了。可能没有，可能只有一个，可能有多个。个数就不相同了。可能没有，可能只有一个，可能有多个。n 这一事实的几何意义是：过这一事实的几何意义是：过 f 轴上坐标为轴上坐标为 的点作的点作 坐标坐标 平面的平行平面平面的平行平面L，可能与曲面，可能与曲面S无交点（无

3、交点（时），可能与时），可能与S 有一个交点（有一个交点（时），可能与时），可能与S交成一条曲线（交成一条曲线（）。）。12ox x 0012,oxxP0f 22001221fxx 12ox x0f f z2x2x2x1x1x1xff0P0P9f 4f 1f 0f12ox x00f 00f 00f 我我们们感感兴兴趣趣的的是是至至少少有有一一个个交交点点（00f ）的的情情形形。定定义义:此此时时用用平平面面 L L 截截曲曲面面 S S 得得到到一一个个圆圆，将将它它投投影影到到 平平面面上上，仍仍为为同同样样大大小小的的圆圆。在在这这个个圆圆上上每每一一点点的的目目标标函函数数值值均均为为

4、0f,若若一一条条曲曲线线上上任任何何一一点点的的目目标标函函数数值值等等于于同同一一常常数数，则则称称此此曲曲线线为为目目标标函函数数的的等等值值线线。注注：变变动动f的的值值，得得到到不不同同等等值值线线，这这是是一一组组同同心心圆圆.对对应应0f 的的等等值值线线缩缩为为一一点点 G G;对对应应0f 的的等等值值线线为为空空集集.随随着着f值值变变小小，等等值值线线圆圆半半径径变变小小，最最后后缩缩为为一一点点，即即为为例例 1 1 中中的的最最小小值值点点 G G,2,1Tz .例例 2 2 用用图图解解法法求求解解 221212min21.50s txxxx 解解：先先画画出出目目

5、标标函函数数等等值值线线，再再画画出出约约束束曲曲线线.本本处处约约束束曲曲线线是是一一条条直直线线，这这条条直直线线就就是是容容许许集集；而而最最优优点点就就是是容容许许集集上上 使使等等值值线线具具有有最最小小值值的的点点.由由图图易易见见约约束束直直线线与与等等值值线线的的切切点点是是最最优优点点，利利用用解解析析几几何何的的方方法法得得 该该切切点点为为 3,2Tz ，对对应应的的最最优优值值为为 2fz 例例 2 2 用用图图解解法法求求解解 122122122122min21.5050,0 xxs txxxxxxx 解解：先先画画出出等等式式约约束束曲曲线线212250 xxx 的

6、的图图形形.这这是是一一条条抛抛物物线线，如如图图 再再画画出出不不等等式式约约束束区区域域如如图图 （怎怎样样选选定定哪哪侧侧区区域域）最最后后画画出出目目标标函函数数等等值值线线，特特别别注注意意可可行行集集边边界界点点以以及及等等值值线线与与可可行行集集的的切切点点，易易见见可可行行域域为为曲曲线线段段 A AB BC CD D。当当动动点点沿沿抛抛物物曲曲线线段段 A AB BC CD D 由由 A A 点点出出发发时时，A AB B 段段目目标标函函数数值值下下降降。过过点点 B B 后后，在在 B BC C 段段目目标标函函数数值值上上升升。过过 C C 点点后后，在在 C CD

7、D 段段目目标标函函数数值值再再次次下下降降。D D 点点是是使使目目标标函函数数值值最最小小的的可可行行点点，其其坐坐标标可可通通过过解解方方程程组组：2122125050 xxxxx 得得：4,1Tz ，对对应应的的最最优优值值为为 4fz 由由以以上上三三个个例例子子可可见见，对对二二维维最最优优化化问问题题。我我们们总总可可以以用用图图解解法法求求解解，由由二二维维观观察察三三维维的的情情形形.而而对对高高维维问问题题，已已不不便便在在平平面面上上作作图图，此此法法失失效效。在在三三维维和和三三维维以以上上的的空空间间中中，使使目目标标函函数数取取同同一一常常数数值值的的是是 Z Z|

8、f f(Z Z)=r r,r r 是是常常数数 称称为为目目标标函函数数的的等等值值面面。等等值值面面具具有有以以下下性性质质：（1 1）不不同同值值的的等等值值面面之之间间不不相相交交，因因为为目目标标函函数数是是单单值值函函数数。（2 2）除除了了极极值值点点所所在在的的等等值值面面外外，不不会会在在区区域域内内部部中中断断，因因为为目目标标函函数数是是连连续续的的。(3 3）等等值值面面稠稠的的地地方方，目目标标函函数数值值变变化化得得较较快快，而而稀稀疏疏的的地地方方变变化化得得比比较较慢慢。（4 4）一一般般地地，在在极极值值点点附附近近，等等值值面面（线线）近近似似地地呈呈现现为为

9、同同心心椭椭球球面面族族（椭椭圆圆族族）。2 2.2 2 二二次次函函数数 一一般般形形式式：121111,2nnnnijijiiijifxxxg x xb xc ijjigg，其其中中,ijigb c均均为为常常数数.矩矩阵阵形形式式：12TTfZZ QZb Zc 其其中中：111212122212nnnnnnggggggQggg （对对称称阵阵），12nbbbb 在在 代代 数数 学学 中中 将将 特特 殊殊 的的 二二 次次 函函 数数 12TfZZ QZ 称称为为二二次次型型。对对于于二二次次函函数数，我我们们更更关关心心的的是是 Q Q 为为正正定定矩矩阵阵的的情情形形。定定义义：设

10、设 Q Q 为为 n nn n 对对称称矩矩阵阵，若若,0nZRZ ，均均有有0TZ QZ ，则则称称矩矩阵阵 Q Q 正正定定.若若nZR ，均均有有0TZ QZ ，则则称称矩矩阵阵 Q Q 半半正正定定.若若,0nZRZ ，均均有有0TZ QZ ，则则称称矩矩阵阵 Q Q 负负定定.若若nZR ，均均有有0TZ QZ ，则则称称矩矩阵阵 Q Q 半半负负定定.判判定定一一个个对对称称矩矩阵阵 Q Q 是是不不是是正正定定的的，可可以以用用 S Sy yl lv ve es st te er r定定理理来来判判定定。S Sy yl lv ve es st te er r 定定理理：一一个个

11、n nn n 对对称称矩矩阵阵 Q Q 是是正正定定矩矩阵阵的的充充要要条条件件是是矩矩阵阵 Q Q 的的各各阶阶主主子子式式都都是是正正的的。A A 是是正正定定矩矩阵阵：非非奇奇异异矩矩阵阵AG G ；A A 的的所所有有特特征征根根大大于于零零；存存在在高高矩矩阵阵 G G，使使AG G ；（矩矩阵阵秩秩等等于于矩矩阵阵列列：高高矩矩阵阵）A A 的的所所有有主主子子式式0 0.例例：判判定定矩矩阵阵631320104Q 是是否否正正定定？解解：对对称称矩矩阵阵 Q Q 的的三三个个主主子子式式依依次次为为：60；633032 ；631320100104 因因此此，矩矩阵阵 Q Q 是是

12、正正定定的的.性性质质：若若二二次次函函数数 12TfZZ QZbZc 中中 Q Q 正正定定，则则它它的的等等值值面面是是同同心心椭椭球球面面族族，且且中中心心为为1ZQb .证证明明：作作变变换换1ZYQb ，代代入入二二次次函函数数式式中中：11111121122TTTTYfYQbYQbQ YQbbYQbcY QYb Qbc 根根 据据 解解 析析 几几 何何 知知 识识，Q Q 为为 正正 定定 矩矩 阵阵 的的 二二 次次 型型12TY QY 的的等等值值面面是是以以坐坐标标原原点点0Y 为为中中心心的的同同心心椭椭球球面面族族。由由于于上上式式中中的的112Tb Qb 是是常常数数

13、，所所以以 Y 的的等等值值面面也也是是以以0Y 为为中中心心的的同同心心椭椭球球面面族族，回回 到到 原原 坐坐 标标 系系 中中 去去，原原 二二 次次 函函 数数 就就 是是 以以1ZQb 为为中中心心的的同同心心椭椭球球面面族族。注注：这这族族椭椭球球面面的的中中心心1ZQb 恰恰是是二二次次目目标标函函数数的的唯唯一一极极小小点点.求求极极值值点点即即求求椭椭圆圆中中心心.一一般般目目标标函函数数的的等等值值面面在在极极小小点点附附近近近近似似地地呈呈现现为为椭椭球球面面族族。由由此此可可见见对对于于二二次次目目标标函函数数有有效效的的求求极极小小点点的的算算法法，当当用用于于一一般

14、般目目标标函函数数时时，至至少少在在极极小小点点附附近近同同样样有有效效。因因此此在在最最优优化化理理论论中中判判定定一一个个算算法法好好坏坏的的标标准准之之一一，是是把把该该算算法法用用于于 Q Q 为为正正定定的的二二次次目目标标函函数数，如如能能迅迅速速找找到到极极小小点点，就就是是好好算算法法；否否则则就就不不是是太太好好的的算算法法。若若算算法法对对于于 Q Q 为为正正定定的的二二次次目目标标函函数数能能在在有有限限步步内内找找出出极极小小点点来来，就就称称此此算算法法为为二二次次收收敛敛算算法法，或或具具有有二二次次收收敛敛性性。例例：把把下下列列二二次次函函数数：2221231

15、23121312,32345fxxxxxxx xx xxx 化化为为矩矩阵阵向向量量形形式式，并并检检验验 Q Q 是是否否正正定定，如如正正定定，试试用用公公式式 1ZQb 求求这这个个函函数数的的极极小小点点。123111213111232122232123231323333121,2TTfx x xZ QZb Zgggxxxxxgggxb bbxgggxx 解：其其中中：631320104Q ，450b 由由前前例例知知 Q Q 正正定定，1812210101012233101010233101010Q 所所以以极极小小点点为为：=12 86 70 7Qbz 2 2.3 3 方方向向导导

16、数数 一一、多多元元函函数数的的可可微微性性和和梯梯度度 定定义义 1 1：设设 f f:1nDRR,0Z D D，若若nlR ，使使npR 有有：000lim0TPfzpfzl PP (1 1)则则称称 f f(Z Z)在在0z处处可可微微。若若令令 00TfZpfZl pp 则则 f f 在在0z处处可可微微时时，有有0lim0P ，即即 是是无无穷穷小小量量。从从而而：00TfZpfZl pop (2 2)定定理理：若若 f f(Z Z)在在0z处处可可微微，f f(Z Z)在在该该点点处处关关于于各各变变量量的的一一阶阶偏偏导导数数存存在在，且且 00012,TnfZfZfZlxxx

17、.(3 3)证证明明：令令12,Tnllll 依依次次取取,1 iipp ein ，ip为为任任意意无无穷穷小小量量，ie是是第第 i i个个坐坐标标轴轴上上的的单单位位向向量量，即即：0,0,1,0,0Tiie .由由于于 f f(Z Z)在在0z处处可可微微，则则（2 2）式式对对iipp e 成成立立，即即：00iiiiifZp efZl pop ，1 in 两两边边除除以以ip，并并取取0ip 的的极极限限，有有：0000limiiiiPiifZfZp efZlxp ，1 in 定定义义：以以 f f(Z Z)的的 n n 个个偏偏导导数数为为分分量量的的向向量量称称为为 f f(Z

18、Z)在在 Z Z 处处的的梯梯度度.记记为为：12,TnfZfZfZfZxxx .梯梯度度也也可可称称为为函函数数 f f(Z Z)关关于于向向量量 Z Z 的的一一阶阶导导数数.若若 f f(Z Z)在在0z处处可可微微，将将(3 3)代代入入(2 2),得得：000TfZpfZfZpop 这这与与一一元元函函数数展展开开到到两两项项的的 T Ta ay yl lo or r 公公式式是是相相对对应应的的.二二.梯梯度度的的性性质质 设设 f f(Z Z)在在定定义义域域内内有有连连续续偏偏导导数数，即即有有连连续续梯梯度度 fZ，则则梯梯度度有有以以下下两两个个重重要要性性质质：性性质质一

19、一：函函数数在在某某点点的的梯梯度度不不为为零零，则则必必与与过过该该点点的的等等值值面面垂垂直直.性性质质二二：梯梯度度方方向向是是函函数数具具有有最最大大变变化化率率的的方方向向。性性质质一一的的证证明明：过过点点0z的的等等直直面面方方程程为为;0fZfZ 或或 12000,nfxxxr rfZ 设设 1122,nnxxxxxx 是是过过点点0z，同同时时又又完完全全在在等等值值面面上上的的任任一一条条光光滑滑曲曲线线 L L 的的方方程程，为为参参数数.点点0 x对对应应的的参参数数是是0，则则有有：120,nfxxxr 两两边边同同时时在在0 处处关关于于 求求导导，根根据据复复合合

20、函函数数微微分分法法有有：00010200120nnfZfZfZxxxxxx 向向量量 010200,ntxxx 是是曲曲线线 L L 在在0z处处的的切切向向量量.由由梯梯度度定定义义及及上上式式有有：000TfZt 即即函函数数 f f(Z Z)在在0z处处的的梯梯度度 0fZ 与与过过该该点点在在等等值值面面上上的的任任一一条条曲曲线线 L L 在在此此点点的的切切线线垂垂直直。从从而而与与过过该该点点的的切切平平面面垂垂直直，从从而而性性质质一一成成立立.为为了了说说明明性性质质二二，先先给给出出方方向向导导数数的的定定义义.定定义义：设设1:nfRR在在点点 Z Z 处处可可微微，P

21、 P 为为固固定定向向量量，e e 为为向向量量 P P 方方向向的的单单位位向向量量，则则称称极极限限：0000limtfZfZtefZpt 为为函函数数 f f(Z Z)在在点点0z处处沿沿方方向向 P P 的的方方向向导导数数，记记为为：0fZp .由由定定义义及及极极限限性性质质可可知知：若若 00fZp ，则则 f f(Z Z)从从0z出出发发在在0z附附近近沿沿 P P 方方向向是是下下降降的的.00fZp ，则则 t t0 0 充充分分小小时时，000fZtefZt 即即即：0fZfZ，0ZZte 若若 00fZp ，则则 f f(Z Z)从从0z出出发发在在0z附附近近沿沿 P

22、 P 方方向向是是上上升升的的.定定理理：若若1:nfRR在在点点0z处处可可微微，则则：00TfZfZep ，其其中中 e e 为为 P P 方方向向上上的的单单位位向向量量.证证明明：利利用用方方向向导导数数定定义义并并将将 000TfZpfZfZpop 中中的的 P P 换换成成 t te e，则则有有：0000limTTtfZtfZeo tfZept 推推论论：若若 00TfZP ，则则 P P 是是函函数数 f f(Z Z)在在0z的的下下降降方方向向.若若 00TfZP ，则则 P P 是是函函数数 f f(Z Z)在在0z的的上上升升方方向向.由由上上述述分分析析可可知知：方方向

23、向导导数数正正负负决决定定了了函函数数升升降降；升升降降速速度度的的快快慢慢由由方方向向导导数数绝绝对对值值大大小小来来决决定定，绝绝对对值值越越大大升升降降速速度度越越大大。因因此此又又将将方方向向导导数数 0fZp 称称为为 f f(Z Z)在在0Z处处沿沿方方向向 P P 的的变变化化率率。因因为为：000cosTfZfZefZp 向 量 （为为方方向向 P P 与与 0fZ 的的夹夹角角）为为使使 0fZp 取取最最小小值值，应应取取0180，即即 P P=-0fZ，则则：结结论论一一：负负梯梯度度方方向向即即为为函函数数的的最最速速下下降降方方向向；结结论论二二：梯梯度度方方向向为为

24、函函数数的的最最速速上上升升方方向向.由由此此我我们们也也就就证证明明了了性性质质二二.即即：函函数数在在与与其其梯梯度度正正交交的的方方向向上上变变化化率率为为 0 0；函函数数在在与与其其梯梯度度成成锐锐角角的的方方向向上上是是上上升升的的；函函数数在在与与其其梯梯度度成成钝钝角角的的方方向向上上是是下下降降的的.例例：试试 求求 目目 标标 函函 数数 22121122,34fxxxx xx 在在点点 00,1TZ 处处的的最最速速下下降降方方向向，并并求求沿沿这这个个方方向向移移动动一一个个单单位位长长度度后后新新点点的的目目标标函函数数值值。解解：由由于于 12121264,42fZ

25、fZxxxxxx 则则函函数数在在 00,1TZ 处处的的最最速速下下降降方方向向是是：121211200121021644422xxxxfZxxxPfZxxfZx 2.4 凸凸集集与与凸凸函函数数 问问题题：设设 f（x）定定义义在在 D 内内，fx 为为极极小小值值，这这是是一一局局部部概概念念，即即在在x 的的邻邻域域内内，fx 为为最最小小。若若x 为为 fx的的最最小小值值点点，则则x 为为 fx的的极极小小值值点点。反反过过来来不不一一定定成成立立。最最小小值值?极极小小值值 从从一一元元函函数数可可得得到到启启发发：若若 fx在在区区间间 ,a b上上为为下下凸凸：x 为为 fx

26、的的最最小小值值点点x 为为 fx的的极极小小值值点点。且且由由微微分分学学知知：若若 0fx ，fx为为下下凸凸。为为了了研研究究多多元元函函数数的的极极值值与与最最值值的的关关系系，下下面面介介绍绍多多元元函函数数凸凸性性。一一 凸凸集集与与性性质质 Def1:若若点点集集 D 中中任任意意两两点点的的连连线线都都属属于于 D，则则称称为为凸凸集集。12,xx 上上任任一一点点可可以以表表示示为为：12101xxx Def2:（等等价价）设设 12,0,1nDRxxD ，恒恒有有：121xxD ，则则称称 D 为为凸凸集集。Def3:（等等价价）设设12,nDRxxD 12120,0,1

27、，恒恒有有：1212xxD ，则则称称 D 为为凸凸集集。规规定定：空空集集，单单元元集集为为凸凸集集。凸集凸集非凸集非凸集非凸集非凸集例例：证证明明nR中中的的集集合合 ,nSx Axb xR 是是凸凸集集。其其中中，A 为为 m n矩矩阵阵，b 为为 m 维维向向量量。证证：1212,xxs Axb Axb 0,1 ，则则:1212121111AxxAxAxabbbxxS 所所以以,S 为为凸凸集集 性性质质 1：设设,nnARBRA B 均均为为凸凸集集，则则：,AB AB AB 均均为为凸凸集集.注注：AB 不不一一定定为为凸凸集集。Def:设设对对任任意意正正整整数数2,m 121,

28、0,1mmniiixxxR ，称称12121mimimixxxx 为为12,mxxx的的凸凸组组合合。性性质质 2：S 是是凸凸集集S 中中的的任任意意有有限限点点的的凸凸组组合合属属于于 S。n多胞形多胞形 H(x1,x2,xm)：由由 x1,x2,xm的所有凸组合构成。的所有凸组合构成。n单纯形：若单纯形：若多胞形多胞形 H(x1,x2,xm)满足，满足，x2-x1,x3-x1,xm-x1线性无关。线性无关。多胞形多胞形单纯形单纯形单纯形单纯形性质性质3：分离与支撑：分离与支撑：凸集边界上任意点存在支撑超平面凸集边界上任意点存在支撑超平面 两个互相不交的凸集之间存在分离超平面两个互相不交的

29、凸集之间存在分离超平面支撑支撑强分离强分离分离分离非正常非正常分离分离nDef：C Rn,若若 x C,0 有有 x C,则则称称 C 是以是以 0 为顶点的锥。如果为顶点的锥。如果 C 还是凸集，还是凸集，则称为凸锥。则称为凸锥。n集合集合 0、Rn 是凸锥。是凸锥。n命题：命题：C是凸锥是凸锥C中任意有限点的半正组合属于中任意有限点的半正组合属于S0二二凸凸函函数数 由由一一元元函函数数的的几几何何图图形形知知：fx下下凸凸，则则曲曲线线上上任任意意两两点点 A，B,弦弦 AB 为为与与弧弧 AB 之之上上，用用数数学学式式子子表表示示：弦弦 AB 的的方方程程：211121fxfxyfx

30、xxxx =211221xxfxxxfxxx 令令 221xxxx ，则则1211xxxx ，121xxx 上上式式可可写写为为：121yfxfx 所所以以：121fxyfxfx 121211fxxfxfx 推推广广到到多多元元函函数数：Def（凸凸函函数数）：设设 12,0,1nDRxxD ，恒恒有有：121211fxxfxfx 则则称称 fx为为在在 D 上上的的凸凸函函数数。等等价价定定义义：设设12,nDRxxD 12120,0,1 ，恒恒有有：12121212fxxfxfx 则则称称 fx为为在在 D 上上的的凸凸函函数数。Def（严严格格凸凸函函数数）：设设 1212,0,1nDR

31、xxD xx ，恒恒有有：121211fxxfxfx 则则称称 fx为为在在 D 上上的的严严格格凸凸函函数数。例例：设设 ,TTnfxx AXAA xR （1）若若 A 为为半半正正定定，则则 fx在在nR上上为为凸凸函函数数；（2）若若 A 为为正正定定，则则 fx在在nR上上为为严严格格凸凸函函数数。证证明明:12,0,1nxxR ,则则 121212121122221112221122111222121211111211112100TTTTTTTTTTTTfxxfxfxxxAxxxAxxAxxAxxAxxAxxAxxAxxAxxAxxAxxxA xxAA 半正正定 n定理：定理：f(x

32、)为凸集为凸集 S 上的凸函数上的凸函数 S 上上任意有限点的凸组合的函数值不大于各点任意有限点的凸组合的函数值不大于各点函数值的凸组合。函数值的凸组合。n思考：设思考：设f1,f2是凸函数，是凸函数，1)设设 1,2 0,1f1+2f2,1f1-2f2是否凸是否凸函数？函数？2)f(x)=max f1(x),f2(x),g(x)=min f1(x),f2(x)是否凸函数？是否凸函数？凸凸函函数数的的判判别别 对对一一元元函函数数，由由几几何何性性质质：曲曲线线位位于于切切线线上上方方.21121fxfxfxxx ,即即 21211fxfxxxfx 推推广广到到多多元元函函数数的的判判别别.T

33、H1(一一阶阶条条件件):若若 D 为为非非空空凸凸集集且且nDR,fx在在 D 上上可可微微,则则 fx在在 D 上上为为凸凸函函数数,x yD ,恒恒有有:Tfyfxyxfx 对对一一元元函函数数,fx凸凸 0fx,推推广广到到多多元元函函数数.TH2(二二阶阶条条件件):若若 D 为为非非空空开开凸凸集集且且nDR,fx在在 D 上上二二次次可可微微,则则:fx在在 D 上上为为凸凸函函数数 20fx n定义：定义：设集合设集合 S Rn，函数，函数 f:SR，R，称称 S =x S f(x)为为 f(x)在在 S 上上 的的 水平集水平集。n定理：定理：设集合设集合 S Rn 是凸集，

34、函数是凸集，函数 f:SR是是凸函数，则对凸函数，则对 R，S 是凸集是凸集。n注：注：1)水平集的概念相当于在地形图中，海拔高度不高于某一水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。数值的区域。2)上述定理的逆不真。上述定理的逆不真。考虑分段函数考虑分段函数f(x)=1(x0)或或0(x 0 充分小时有充分小时有 x*+d S,如果如果 lim f(x*+d)-f(x*)/存在（包括存在（包括 ）则称则称 f(x)为在点沿方向的方向导数存在，记为在点沿方向的方向导数存在，记 f(x*;d)=lim f(x*+d)-f(x*)/若若 f(x)在在 x*可导，则可导，则 f(x*

35、;d)=f(x*)Td .二、凸函数二、凸函数 2、凸函数的性质：、凸函数的性质：以下设以下设 S Rn 为非空凸集，函数为非空凸集，函数 f:SR2）若）若f 凸，则凸，则 f 在在 S 的内点集上连续；的内点集上连续；注：注：f 在在 S 上不一定连续。上不一定连续。例例:f(x)2(当当 x=1)；f(x)x2(当当 x 0,总有总有 x+d S.d(1)=d(2)(0)时，称时，称 d(1)和和d(2)同方向。同方向。4)极方向：方向极方向：方向 d 不能表示为两个不同方向不能表示为两个不同方向的组合的组合(d=d(1)+d(2).2.3 2.3 多面体、极点、极方向多面体、极点、极方

36、向多面体多面体 S=x Rn Ax=b,x0 的极点和极方向的极点和极方向定理定理1（极点特征）设（极点特征）设 A 满秩，满秩，x 是是 S 极极点的充分必要条件是点的充分必要条件是:存在分解存在分解 A=B,N，其中，其中B为为m阶非奇异矩阵，使阶非奇异矩阵，使 xT=xBT,xNT,这里这里 xB=B-1b0,xN=0.nS中必存在有限多个极点。中必存在有限多个极点。(Cnm)2.3 2.3 多面体、极点、极方向多面体、极点、极方向多面体多面体 S=x Rn Ax=b,x0 的极点和极方向的极点和极方向定理定理2（极方向特征）（极方向特征）设设 A=p1,p2,pn满秩，满秩，d 是是

37、S 极方极方向的充分必要条件是向的充分必要条件是:存在分解存在分解 A=B,N，其中，其中B为为m阶非奇异矩阵，阶非奇异矩阵，对于对于N中的列向量中的列向量 pj 使使 B-1pj0,dT=dBT,dNT,这里这里 j dB=-B-1pj,dN=(0,.,1,0)TnS中必存在有限多个极方向。中必存在有限多个极方向。(n-m)Cnm)考虑多面体考虑多面体 S=x Rn Ax=b,x0，其中，其中 3 2 1 0 0 65 A=2 1 0 1 0 b=40 0 3 0 0 1 75 即即 3 x1+2 x2+x3 =65 2 x1+x2 +x4 =40 3 x2 +x5 =75 x1,x2,x3

38、,x4,x5 0 例题例题 3 2 1 0 0A=P1,P2,P3,P4,P5 =2 1 0 1 0 0 3 0 0 1 A A矩阵包含以下10个33的子矩阵：B B1 1=p p1 1，p p2 2，p p3 3 B B2 2=p p1 1，p p2 2，p p4 4 B B3 3=p p1 1，p p2 2，p p5 5 B B4 4=p p1 1，p p3 3，p p4 4 B B5 5=p p1 1，p p3 3，p p5 5 B B6 6=p p1 1，p p4 4，p p5 5 B B7 7=p p2 2，p p3 3，p p4 4 B B8 8=p p2 2，p p3 3，p p

39、5 5 B B9 9=p p2 2，p p4 4，p p5 5 B B1010=p p3 3，p p4 4，p p5 5 例题例题 其中其中 B B4 4=0=0，因而，因而B B4 4不能构成极点和极方向。其余不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有均为非奇异方阵，因此该问题共有9 9个可构成极点、个可构成极点、极方向的子矩阵，我们称之为基。极方向的子矩阵，我们称之为基。对于基对于基B B3 3=p p1 1，p p2 2，p p5 5，令，令x x3 3 =0=0，x x4 4=0=0，在等，在等式约束中令式约束中令x x3 3=0=0，x x4 4 =0=0，解线性方程组

40、：，解线性方程组：3 3 x x1 1 +2+2 x x2 2 +0+0 x x5 5 =65=65 2 2 x x1 1 +x x2 2 +0+0 x x5 5 =40=40 0 0 x x1 1 +3+3 x x2 2 +x x5 5 =75=75 得到得到x x1 1 =15=15，x x2 2 =10=10，x x5 5=45=45，对应的极点：，对应的极点：x x=(=(x x1 1，x x2 2，x x3 3，x x4 4，x x5 5)T T =(15 =(15，1010，0 0，0 0，45)45)T T例题例题 类似可得到极点类似可得到极点 x(2)=(5,25,0,5,0)

41、T （对应（对应B2）x(7)=(20,0,5,0,75)T （对应（对应B5）x(8)=(0,25,15,15,0)T（对应（对应B7）x(9)=(0,0,65,40,75)T（对应（对应B10）而而 x(3)=(0,32.5,0,7.5,-22.5)T（对应（对应B9）x(4)=(65/3,0,0,-10/3,75)T（对应（对应B6）x(5)=(7.5,25,-7.5,0,0)T （对应（对应B1）x(6)=(0,40,-15,0,-45)T （对应（对应B8）不是极点不是极点例题例题 2.3 2.3 多面体、极点、极方向多面体、极点、极方向多面体多面体 S=x Rn Ax=b,x0 的极点和极方向的极点和极方向定理定理3（表示定理）考虑上述多面体（表示定理）考虑上述多面体S，设设A满秩，满秩，x(1),x(2),x(k)为所有极点，为所有极点，d(1),d(2),d(l)为所有极方向。那么，为所有极方向。那么，对于对于 x S，i0，且，且1+2+k=1,j0,j=1,2,l,使使 x=1 x(1)+2 x(2)+k x(k)+1 d(1)+2 d(2)+l d(l).