最優(yōu)化方法第2章課件

1、第 二 章基本概念 和基本理論 0 s s L在 平面上任給一點(diǎn) ，就對(duì)應(yīng)有一個(gè)目標(biāo)函數(shù)值這個(gè)值就是過 點(diǎn)作 平面的垂線與S曲面交點(diǎn)的縱坐標(biāo)。 反之，任給一個(gè)值 ,使目標(biāo)函數(shù) 取值為 的點(diǎn)z的 個(gè)數(shù)就不相同了?？赡軟]有，可能只有一個(gè)，可能有多個(gè)。 這一事實(shí)的幾何意義是：過 f 軸上坐標(biāo)為 的點(diǎn)作 坐標(biāo) 平面的平行平面L，可能與曲面S無交點(diǎn)（ 時(shí)），可能與S 有一個(gè)交點(diǎn)（ 時(shí)），可能與S交成一條曲線（ ）。凸集非凸集非凸集多胞形 H(x1 , x2 , , xm)： 由 x1 , x2 , , xm的所有凸組合構(gòu)成。單純形：若多胞形 H(x1 , x2 , , xm)滿足， x2-x1 , x3

2、 -x1 , , xm- x1線性無關(guān)。多胞形單純形單純形性質(zhì)3：分離與支撐： 凸集邊界上任意點(diǎn)存在支撐超平面 兩個(gè)互相不交的凸集之間存在分離超平面支撐強(qiáng)分離分離非正常分離Def：C Rn, 若 x C, 0 有 x C, 則稱 C 是以 0 為頂點(diǎn)的錐。如果 C 還是凸集，則稱為凸錐。集合 0 、Rn 是凸錐。命題：C是凸錐C中任意有限點(diǎn)的半正組合屬于S0定理： f(x) 為凸集 S 上的凸函數(shù) S 上任意有限點(diǎn)的凸組合的函數(shù)值不大于各點(diǎn)函數(shù)值的凸組合。思考：設(shè)f1, f2是凸函數(shù)，設(shè)1, 2 0, 1f1+2f2 , 1f1 - 2f2是否凸函數(shù)？f(x)= max f1(x) , f2

3、(x) , g(x)= min f1(x) , f2 (x) 是否凸函數(shù)？ 定義：設(shè)集合 S Rn ，函數(shù) f :SR， R ，稱 S = x Sf(x) 為 f(x) 在 S 上 的 水平集。定理：設(shè)集合 S Rn 是凸集，函數(shù) f :SR是凸函數(shù)，則對(duì) R ，S 是凸集。注：水平集的概念相當(dāng)于在地形圖中，海拔高度不高于某一數(shù)值的區(qū)域。上述定理的逆不真。 考慮分段函數(shù)f(x)=1(x0)或0(x 0 充分小時(shí)有 x*+d S, 如果 lim f(x*+ d )-f(x*) / 存在（包括 ） 則稱 f(x) 為在點(diǎn)沿方向的方向?qū)?shù)存在，記 f (x*;d) = lim f(x*+ d )-f

4、(x*) / 若 f(x) 在 x* 可導(dǎo)，則 f (x*;d) = f (x*) Td .二、凸函數(shù) 2、凸函數(shù)的性質(zhì)：以下設(shè) S Rn 為非空凸集，函數(shù) f :SR2）若f 凸，則 f 在 S 的內(nèi)點(diǎn)集上連續(xù)； 注： f 在 S 上不一定連續(xù)。 例: f(x)2(當(dāng)x=1)； f(x)x2 (當(dāng)x 0 , 總有 x + d S. d(1) = d(2) ( 0) 時(shí)，稱 d(1)和d(2)同方向。4) 極方向：方向 d 不能表示為兩個(gè)不同方向的組合 ( d = d(1)+d(2) ) .2.3 多面體、極點(diǎn)、極方向多面體 S = xRnAx = b , x0 的極點(diǎn)和極方向定理1（極點(diǎn)特征

5、）設(shè) A 滿秩，x 是 S 極點(diǎn)的充分必要條件是: 存在分解 A = B , N ，其中B為m階非奇異矩陣，使 xT = xBT, xNT , 這里 xB = B-1b0, xN =0.S中必存在有限多個(gè)極點(diǎn)。( Cnm )2.3 多面體、極點(diǎn)、極方向多面體 S = xRnAx = b , x0 的極點(diǎn)和極方向定理2（極方向特征）設(shè) A = p1, p2, ,pn滿秩，d 是 S 極方向的充分必要條件是: 存在分解 A = B , N ，其中B為m階非奇異矩陣，對(duì)于N中的列向量 pj 使 B-1pj0, dT = dBT, dNT , 這里 j dB = -B-1pj , dN = (0, .

6、 , 1, ,0)TS中必存在有限多個(gè)極方向。( (n-m)Cnm )考慮多面體 S = xRnAx = 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 , x4 , x5 0 例題 3 2 1 0 0A = P1 , P2 , P3 , P4 , P5 = 2 1 0 1 0 0 3 0 0 1 A矩陣包含以下10個(gè)33的子矩陣： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p

7、4 B3=p1 ，p2 ，p5 B4=p1 ，p3 ，p4 B5=p1 ，p3 ，p5 B6=p1 ，p4 ，p5 B7=p2 ，p3 ，p4 B8=p2 ，p3 ，p5 B9=p2 ，p4 ，p5 B10=p3 ，p4 ，p5 例題 其中B4= 0，因而B4不能構(gòu)成極點(diǎn)和極方向。其余均為非奇異方陣，因此該問題共有9個(gè)可構(gòu)成極點(diǎn)、極方向的子矩陣，我們稱之為基。 對(duì)于基B3=p1 ，p2 ，p5，令x3 = 0， x4 = 0，在等式約束中令x3 = 0，x4 = 0，解線性方程組： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x

8、2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，對(duì)應(yīng)的極點(diǎn)： x = (x1，x2，x3，x4，x5 )T = (15，10，0，0，45 )T例題 類似可得到極點(diǎn) x(2) = (5, 25, 0, 5, 0 )T （對(duì)應(yīng)B2） x(7) = (20, 0, 5, 0, 75 )T （對(duì)應(yīng)B5） x(8) = (0, 25, 15, 15, 0 )T （對(duì)應(yīng)B7） x(9) = (0, 0, 65, 40, 75 )T （對(duì)應(yīng)B10）而 x(3)= (0, 32.5, 0, 7.5, -22.5 )T（對(duì)應(yīng)B9） x(4)= (65/3, 0, 0, -10/3, 75 )T （對(duì)應(yīng)B6） x(5)= ( 7.5, 25, -7.5, 0, 0 )T （對(duì)應(yīng)B1） x(6) = ( 0, 40, -15, 0, -45 )T （對(duì)應(yīng)B8） 不是極點(diǎn)例題 2.3 多面體、極點(diǎn)、極方向多面體 S = xRnAx = b , x0 的極點(diǎn)和極方向定理3（表示定理）考慮上述多面體S， 設(shè)A滿秩，x(1),x(2) , ,x(k