1、第 二 章,基本概念 和 基本理論,第二章 基本概念和理論基礎(chǔ),2.1 數(shù)學(xué)規(guī)劃模型的一般形式 min f(x) -目標(biāo)函數(shù) s.t. xS -約束集合，可行集 其中，S Rn，f :S R，xS稱（f S )的可行解 最優(yōu)解: x*S，滿足f (x*) f (x), xS。則稱 x*為(f S)的全局最優(yōu)解(最優(yōu)解), 記 g.opt.(global optimum),簡記 opt. 最優(yōu)值: x*為(f S)的最優(yōu)解, 則稱 f * = f (x*) 為 (f S)的最優(yōu)值(最優(yōu)目標(biāo)函數(shù)值),( f S ),2.1 數(shù)學(xué)規(guī)劃模型的一般形式（續(xù)）,局部最優(yōu)解: x*S， x* 的鄰域 N(x

2、*) ，使?jié)M足 f (x*) f (x), x S N(x*) 。則稱 x*為(f S)的局部最優(yōu)解,記 l .opt.(local optimum) 在上述定義中，當(dāng)x x* 時有嚴(yán)格不等式成立，則分別稱 x* 為(f S)的嚴(yán)格全局最優(yōu)解和嚴(yán)格局部最優(yōu)解。,嚴(yán)格l .opt .,嚴(yán)格g .opt .,l .opt .,2.1 數(shù)學(xué)規(guī)劃模型的一般形式（續(xù)）,函數(shù)形式: f(x), gi(x) , hj(x) : RnR min f(x) (fgh) s.t. gi(x) 0 , i = 1,2,m hj(x) = 0 , j = 1,2,l 矩陣形式: min f(x) ，f(x) : Rn

3、R (fgh) s.t. g(x) 0 , g(x) : RnRm h(x) = 0 , h(x) : RnRl 當(dāng) f(x), gi(x) , hj(x)均為線性函數(shù)時，稱線性規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃。,2.2 凸集、凸函數(shù)和凸規(guī)劃,一、凸集 1、凸集的概念： 定義：設(shè)集合 S Rn，若x(1), x(2)S, 0,1，必有 x(1)(1- ) x(2) S ，則稱 S 為凸集。 規(guī)定：單點集 x 為凸集，空集為凸集。 注: x(1)(1- ) x(2) = x(2)(x(1)- x(2) 是連接 x(1)與x(2)的線段 。,凸集,非凸集,非凸集,2.2 凸集、凸函數(shù)和凸規(guī)

4、劃(續(xù)),一、凸集 1、凸集的概念： 例:證明集合 S = xAx = b 是凸集。其中，A為 mn矩陣，b為m維向量。 凸組合：設(shè) x(1) , x(2) , , x(m) Rn, j 0 m m j =1, 那么稱 j x(j) 為x(1), x(2), , x(m)的 j =1 j = 1 凸組合。 m 比較: z = j x(j) j =1 jR 構(gòu)成線性組合 線性子空間 j0 , j 0 構(gòu)成半正組合 凸錐 j0 , j =0 構(gòu)成凸組合 凸集,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),一、凸集 1、凸集的概念： 定理：S是凸集S中任意有限點的凸組合屬于S 多胞形 H(x(1) , x(2

5、) , , x(m) )： 由 x(1) , x(2) , , x(m) 的所有凸組合構(gòu)成。 單純形：若多胞形 H(x(1) , x(2) , , x(m) )滿足， x(2)-x(1) , x(3) -x(1) , , x(m)- x(1) 線性無關(guān)。,多胞形,單純形,單純形,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),一、凸集 2、凸集的性質(zhì)： 凸集的交集是凸集；（并？） 凸集的內(nèi)點集是凸集；（逆命題是否成立？） 凸集的閉包是凸集。 （逆命題是否成立？） 分離與支撐： 凸集邊界上任意點存在支撐超平面 兩個互相不交的凸集之間存在分離超平面,支撐,強分離,分離,非正常分離,2.2 凸集、凸函數(shù)和凸規(guī)劃

6、(續(xù)),一、凸集 3、凸錐： 定義：C Rn, 若 x C, 0 有 x C, 則稱 C 是以 0 為頂點的錐。如果 C 還是凸集，則稱為凸錐。 集合 0 、Rn 是凸錐。 命題：C是凸錐C中任意有限點的半正組合屬于S,0,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 1、凸函數(shù)及水平集 定義: 設(shè)集合 S Rn 為凸集，函數(shù) f :SR 若 x(1), x(2) S, ( 0 , 1 ) ，均有 f(x(1)(1- ) x(2) ) f(x(1)+(1- )f(x(2) ， 則稱 f(x) 為凸集 S 上的凸函數(shù)。 若進(jìn)一步有上面不等式以嚴(yán)格不等式成立，則稱 f(x) 為凸集 S 上的嚴(yán)格

7、凸函數(shù)。 當(dāng)- f(x) 為凸函數(shù)（嚴(yán)格凸函數(shù)）時，則稱 f(x) 為凹函數(shù)（嚴(yán)格凹函數(shù)）。,嚴(yán)格凸函數(shù),凸函數(shù),嚴(yán)格凹函數(shù),2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 1、凸函數(shù)及水平集： 定理： f(x) 為凸集 S 上的凸函數(shù) S 上任意有限點的凸組合的函數(shù)值不大于各點函數(shù)值的凸組合。 思考：設(shè)f1, f2是凸函數(shù)， 設(shè)1, 2 0, 1f1+2f2 , 1f1 - 2f2是否凸函數(shù)？ f(x)= max f1(x) , f2 (x) , g(x)= min f1(x) , f2 (x) 是否凸函數(shù)？,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 1、凸函數(shù)及水平集： 定義：設(shè)集合

8、 S Rn ，函數(shù) f :SR， R ， 稱 S = x Sf(x) 為 f(x) 在 S 上 的 水平集。 定理：設(shè)集合 S Rn 是凸集，函數(shù) f :SR是凸函數(shù)，則對 R ，S 是凸集。 注： 水平集的概念相當(dāng)于在地形圖中，海拔高度不高于某一數(shù)值的區(qū)域。 上述定理的逆不真。 考慮分段函數(shù)f(x)=1(x0)或0(x0)，函數(shù)非凸，但任意水平集是凸集。,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 2、凸函數(shù)的性質(zhì)： 方向?qū)?shù)：設(shè) S Rn 為非空凸集，函數(shù) f :SR ，再設(shè) x* S, d 為方向，使當(dāng) 0 充分小時有 x*+d S, 如果 lim f(x*+ d )-f(x*) /

9、 存在（包括 ） 則稱 f(x) 為在點沿方向的方向?qū)?shù)存在，記 f (x*;d) = lim f(x*+ d )-f(x*) / 若 f(x) 在 x* 可導(dǎo)，則 f (x*;d) = f (x*) Td .,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 2、凸函數(shù)的性質(zhì)： 以下設(shè) S Rn 為非空凸集，函數(shù) f :SR 2）若f 凸，則 f 在 S 的內(nèi)點集上連續(xù)； 注： f 在 S 上不一定連續(xù)。 例: f(x)2(當(dāng)x=1)； f(x)x2 (當(dāng)x1) . 3）設(shè)f 凸，則對任意方向方向?qū)?shù)存在。 4）設(shè) S 是開集，f 在 S 上可微，則 f凸 x*S，有f (x) f (x*)+

10、 f T(x*)(x-x*) , x S . 5) 設(shè) S 是開集，f 在 S 上二次可微，則 a) f 凸 xS，2f (x) 半正定； b) 若 xS，2f (x) 正定，則f嚴(yán)格凸。,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 2、凸函數(shù)的性質(zhì)： 例： f(x)x12+2x1x2+2x22+10 x1 - 4 ； f(x)-3x12+x1x2-x22-2x32-2x2x3+26 ; f(x)3x12+ax1x2+2x22-4x1+6 ( a=5, 4.5 )；,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),三、凸規(guī)劃： 當(dāng)（f S）中，S為凸集，f是S上的凸函數(shù)（求min），稱（f S）為凸規(guī)

11、劃； 對于（fgh）, f,gi為凸函數(shù)，hj為線性函數(shù)時，（fgh）為凸規(guī)劃。 定理：設(shè)集合 S Rn 為凸集，函數(shù) f :SR f(x) 為凸集 S 上的凸函數(shù)。X*為問題（fs）的l.opt，則X*為g.opt；又如果f是嚴(yán)格凸函數(shù)，那么X*是（fs）的唯一g.opt。,2.3 多面體、極點、極方向,1）多面體：有限個半閉空間的交 例：S = xRnAx = b , x0 ,2.3 多面體、極點、極方向,2) 多面體的極點（頂點）： xS，不存在 S 中的另外兩個點x(1)和x(2)，及 (0,1)，使 x = x(1)+(1-)x(2). 3) 方向：xS , dRn , d 0 及

12、0 , 總有 x + d S. d(1) = d(2) ( 0) 時，稱 d(1)和d(2)同方向。 4) 極方向：方向 d 不能表示為兩個不同方向的組合 ( d = d(1)+d(2) ) .,2.3 多面體、極點、極方向,多面體 S = xRnAx = b , x0 的極點和極方向 定理1（極點特征）設(shè) A 滿秩，x 是 S 極點的充分必要條件是: 存在分解 A = B , N ，其中B為m階非奇異矩陣，使 xT = xBT, xNT , 這里 xB = B-1b0, xN =0. S中必存在有限多個極點。( Cnm ),2.3 多面體、極點、極方向,多面體 S = xRnAx = b ,

13、 x0 的極點和極方向 定理2（極方向特征） 設(shè) A = p1, p2, ,pn滿秩，d 是 S 極方向的充分必要條件是: 存在分解 A = B , N ，其中B為m階非奇異矩陣，對于N中的列向量 pj 使 B-1pj0, dT = dBT, dNT , 這里 j dB = -B-1pj , dN = (0, . , 1, ,0)T S中必存在有限多個極方向。( (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 +

14、 x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0,例題,3 2 1 0 0 A = P1 , P2 , P3 , P4 , P5 = 2 1 0 1 0 0 3 0 0 1 A矩陣包含以下10個33的子矩陣： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p4 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)成極點和極方向

15、。其余均為非奇異方陣，因此該問題共有9個可構(gòu)成極點、極方向的子矩陣，我們稱之為基。 對于基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 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，對應(yīng)的極點： x = (x1，x2，x3，x4，x5 )T = (15，10，0，0，45 )T,例題,類似可得到極點 x(2) = (5, 25, 0, 5, 0 )T （對應(yīng)B2） x(7) = (20, 0, 5, 0, 75 )T （對應(yīng)B5） x(8) = (0, 25, 15, 15, 0 )T （對應(yīng)B7） x(9) = (0, 0, 65, 40, 75 )T （對應(yīng)B10） 而 x(3)= (0, 32.5, 0, 7.5, -22.5 )T（對應(yīng)B9） x(4)= (65/3, 0, 0, -10/3, 75 )T （對應(yīng)B6） x(5)= ( 7.5, 25, -7.5, 0, 0 )T （對應(yīng)B1） x(6) = ( 0, 40, -15