最優(yōu)化計(jì)算方法(工程優(yōu)化)復(fù)習(xí)_new

1、 12,0,1 ,x xD 12(1),0,1,xxD D,nDR空集和單元素集也是凸集。空集和單元素集也是凸集。 三角形，矩形，圓，球，凸多邊形，第一象限，第一卦限等都三角形，矩形，圓，球，凸多邊形，第一象限，第一卦限等都是凸的。是凸的。設(shè)設(shè) 若集合若集合 中任意兩點(diǎn)的連線都屬于中任意兩點(diǎn)的連線都屬于 ，則稱，則稱 為凸集。為凸集。因?yàn)閮牲c(diǎn)因?yàn)閮牲c(diǎn) 連線上任一點(diǎn)可以表示為連線上任一點(diǎn)可以表示為 12(1) ,0,1.xxx 12,x xDDD凸集的幾何特征凸集的幾何特征凸集的代數(shù)特征凸集的代數(shù)特征稱集合稱集合 為凸集為凸集 。恒有恒有 證明集合證明集合 S = x Ax = b 是凸集，其中

2、是凸集，其中A為為 m n矩陣，矩陣，b為為m維向量。維向量。0,1 , 1212(1)(1)(1),AxxAxAxbbb 12,x xS12,Axb Axb即即12(1),xxS所以所以即即S是凸集。是凸集。,nTHx xRc xb 集合集合是凸集是凸集, 稱為超平面，稱為超平面，c為為n維向量。維向量。鄰域鄰域00,|,0N xx x x 是凸集。是凸集。設(shè)設(shè) 那么稱那么稱 是是 的凸組合。的凸組合。 121,.,0,1,mmniiix xxRS 是凸集是凸集 S 中任意有限個(gè)點(diǎn)的凸組合屬于中任意有限個(gè)點(diǎn)的凸組合屬于 S。1miiix12,.,mx xx 設(shè)設(shè) 是凸集，則是凸集，則 也是凸

3、集。也是凸集。,AB AB AB,nA BR: :,: :,.ABab aA bBABa b aA bB 不一定是凸集。不一定是凸集。AB 設(shè)集合設(shè)集合 D Rn 為凸集，函數(shù)為凸集，函數(shù) f :DR, 若若 x, y D, (0 , 1) ，均有，均有 f( x+(1- ) y ) f(x)+(1- )f(y) ，則稱則稱 f(x)為凸集為凸集 D 上的凸函數(shù)。上的凸函數(shù)。 若進(jìn)一步有上面不等式以嚴(yán)格不等式成立，則稱若進(jìn)一步有上面不等式以嚴(yán)格不等式成立，則稱 f(x)為凸集為凸集 D 上的上的嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù)。 當(dāng)當(dāng)-f(x)為凸函數(shù)為凸函數(shù)(嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù))時(shí)，則稱時(shí)，則稱 f(

4、x)為為凹函數(shù)凹函數(shù) (嚴(yán)格凹函數(shù)嚴(yán)格凹函數(shù))。嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù)凸函數(shù)凸函數(shù)嚴(yán)格凹函數(shù)嚴(yán)格凹函數(shù) 設(shè)設(shè)D Rn 為非空凸集，函數(shù)為非空凸集，函數(shù) f :DR 在在 D 上可微，則上可微，則 (1) f在在D上為凸函數(shù)上為凸函數(shù) 任意任意x，y D，恒有，恒有 f (y) f (x)+ f T(x)(y-x) (1) (2) f在在D上為嚴(yán)格凸函數(shù)上為嚴(yán)格凸函數(shù) 任意任意xy D，恒有，恒有 f (y) f (x)+ f T(x)(y-x) . (2)證明證明 設(shè)設(shè)D Rn 為含有內(nèi)點(diǎn)的非空凸集，為含有內(nèi)點(diǎn)的非空凸集，函數(shù)函數(shù) f :DR在在 D 上二次可微，則上二次可微，則 a) f在在D

5、上為凸函數(shù)上為凸函數(shù) x D， 2f (x) 半正定；半正定； b) 若若 x D， 2f (x) 正定，則正定，則f在在D上為嚴(yán)格凸函數(shù)。上為嚴(yán)格凸函數(shù)?；貞洠夯貞洠涸O(shè)二次函數(shù)設(shè)二次函數(shù) (1)：若：若 為半定矩陣，為半定矩陣， 在在 中為凸函數(shù)中為凸函數(shù) ； (2)：若若 為正定矩陣，為正定矩陣， 在在 中為嚴(yán)格凸函數(shù)。中為嚴(yán)格凸函數(shù)。判斷判斷f(x)=5x12-6x1x2+5x22在凸集在凸集D上是否是凸函數(shù)？上是否是凸函數(shù)？ 的順序主子式都是正的，所以正定，因此的順序主子式都是正的，所以正定，因此f(x)在凸集在凸集D上是嚴(yán)格凸函數(shù)。上是嚴(yán)格凸函數(shù)。 2106( )6 10f x Tf

6、 xx AxA( )f xnRnR( )f xA 考慮如下非線性規(guī)劃考慮如下非線性規(guī)劃當(dāng)當(dāng) 都是凸函數(shù)時(shí)都是凸函數(shù)時(shí),稱規(guī)劃稱規(guī)劃 為凸規(guī)劃為凸規(guī)劃( ),( )(1,2, )if x g x im(1) min(1). .0,1,2,if xst gxim 設(shè)設(shè)(1)為凸規(guī)劃，則為凸規(guī)劃，則 i) (1)的可行集的可行集R是凸集；是凸集； ii) (1)的最優(yōu)解集是凸集；的最優(yōu)解集是凸集； iii) (1)的任何局部極小點(diǎn)都是全局極小點(diǎn)。的任何局部極小點(diǎn)都是全局極小點(diǎn)。 設(shè)設(shè)(1)為凸規(guī)劃，若為凸規(guī)劃，若f(x)在非空可行集在非空可行集R上是嚴(yán)格凸函上是嚴(yán)格凸函 數(shù)，則數(shù)，則(1)的全局極小

7、點(diǎn)是唯一的。的全局極小點(diǎn)是唯一的。見書中見書中(P24)定理定理 3.11. 非線性規(guī)劃的局部最優(yōu)解不一定是非線性規(guī)劃的局部最優(yōu)解不一定是 全局最優(yōu)解全局最優(yōu)解,其可行解和最優(yōu)解集也其可行解和最優(yōu)解集也 不一定是凸集不一定是凸集,甚至不是連通集甚至不是連通集.如如 果是凸規(guī)劃果是凸規(guī)劃, 就有很多好的性質(zhì)。就有很多好的性質(zhì)。見書中見書中(P23)定理定理 3.9、3.10.n=1時(shí)，是一維無(wú)約束優(yōu)化問(wèn)題時(shí)，是一維無(wú)約束優(yōu)化問(wèn)題-n1時(shí)，是多維無(wú)約束優(yōu)化問(wèn)題時(shí)，是多維無(wú)約束優(yōu)化問(wèn)題-n元函數(shù)元函數(shù)求解無(wú)約束優(yōu)化問(wèn)題求解無(wú)約束優(yōu)化問(wèn)題min( )nx Rf x:nf RR找初始點(diǎn)找初始點(diǎn)判斷當(dāng)前點(diǎn)

8、是否滿判斷當(dāng)前點(diǎn)是否滿足終止條件足終止條件下一個(gè)迭代點(diǎn)下一個(gè)迭代點(diǎn) 最優(yōu)解最優(yōu)解(a) 找初始點(diǎn)找初始點(diǎn)(b) 終止條件終止條件(c) 迭代格式迭代格式是是否否循循環(huán)環(huán)kkd1kxkdkdmin( )nx Rf x()kkf xdk求目標(biāo)函數(shù)求目標(biāo)函數(shù) f(x) 的極?。旱臉O?。河捎谶@項(xiàng)工作是求以由于這項(xiàng)工作是求以 為變量的一元函數(shù)為變量的一元函數(shù)的極小點(diǎn)的極小點(diǎn)，故常稱這一過(guò)程為，故常稱這一過(guò)程為（精確）一維搜索或（精確）一維搜索或（精確）線搜索或一維最優(yōu)化（精確）線搜索或一維最優(yōu)化，確定的步長(zhǎng)為最佳步長(zhǎng)。，確定的步長(zhǎng)為最佳步長(zhǎng)。: argmin ()kkkf xd( )f x1kx1min

9、 ()kkkkkkkf xdxxd1 T()0.kkf xd 設(shè)目標(biāo)函數(shù)設(shè)目標(biāo)函數(shù)具有一階連續(xù)偏導(dǎo)數(shù)，具有一階連續(xù)偏導(dǎo)數(shù)，規(guī)則產(chǎn)生規(guī)則產(chǎn)生則有則有按下述按下述函數(shù)函數(shù) ，則得，則得( )()kkf xd min kT+1 T0( )()()().kkkkkkkkf xddf xd ( ) k基本思想：一種試探法：從一點(diǎn)出發(fā)，按一定步長(zhǎng)搜索新點(diǎn)，基本思想：一種試探法：從一點(diǎn)出發(fā)，按一定步長(zhǎng)搜索新點(diǎn)，若搜索成功，加大步長(zhǎng)繼續(xù)搜索；若搜索失敗，縮小步長(zhǎng)小若搜索成功，加大步長(zhǎng)繼續(xù)搜索；若搜索失敗，縮小步長(zhǎng)小步后退。步后退。步驟步驟1：選取初始點(diǎn)選取初始點(diǎn) xR , 初始步長(zhǎng)初始步長(zhǎng) h 0 及精度及精

10、度 0，步驟步驟2：計(jì)算：計(jì)算步驟步驟3：若：若 搜索成功搜索成功, 轉(zhuǎn)步驟轉(zhuǎn)步驟4；否則，搜索失敗，；否則，搜索失敗， 轉(zhuǎn)步驟轉(zhuǎn)步驟5。步驟步驟4：令：令 x:= x + h, 轉(zhuǎn)步驟轉(zhuǎn)步驟 2。步驟步驟5：判斷：判斷 若若 停止迭代，停止迭代， ；否則令；否則令 轉(zhuǎn)步驟轉(zhuǎn)步驟 2。缺點(diǎn)：效率低。優(yōu)點(diǎn)：可以求缺點(diǎn)：效率低。優(yōu)點(diǎn)：可以求搜索區(qū)間搜索區(qū)間。1( ).f x2().f xh21,12:,:2hh?hh ，*xx,4hh 注意：初始步長(zhǎng)不能選得太小注意：初始步長(zhǎng)不能選得太?。涸O(shè)給定初始點(diǎn)：設(shè)給定初始點(diǎn)為為 a 及初始步長(zhǎng)為及初始步長(zhǎng)為 h, 求搜索區(qū)間求搜索區(qū)間c, d 1) 前進(jìn)運(yùn)

11、算前進(jìn)運(yùn)算首先計(jì)算首先計(jì)算 f (a), f (a+h), 如果如果 f (a) f (a+h), 則步長(zhǎng)加倍則步長(zhǎng)加倍, 計(jì)計(jì)算算f (a+3h). 若若 f (a+h)= f (a+3h), 則則c=a, d=a+3h; 否則將步否則將步長(zhǎng)再加倍，并重復(fù)上面運(yùn)算長(zhǎng)再加倍，并重復(fù)上面運(yùn)算. 2) 后退運(yùn)算后退運(yùn)算如果如果 f (a) f (a+h), 則將步長(zhǎng)縮為原來(lái)的則將步長(zhǎng)縮為原來(lái)的1/4并改變符號(hào)，即并改變符號(hào)，即將步長(zhǎng)改為將步長(zhǎng)改為-h/4, 如果如果 f (a) f (a-h/4),則則c=a-h /4,d=a+h; 否則否則將步長(zhǎng)加倍，并繼續(xù)后退。將步長(zhǎng)加倍，并繼續(xù)后退。注意注意

12、: 1. h 選擇要適當(dāng)選擇要適當(dāng).(太大含多個(gè)單峰區(qū)間太大含多個(gè)單峰區(qū)間,太小迭代次數(shù)多太小迭代次數(shù)多)； 2. f (x)單調(diào)時(shí)無(wú)結(jié)果單調(diào)時(shí)無(wú)結(jié)果, (加迭代次數(shù)限制加迭代次數(shù)限制)； ：利用利用“成功成功-失敗失敗”法求函數(shù)法求函數(shù) 的搜索區(qū)間，的搜索區(qū)間， 取初始點(diǎn)取初始點(diǎn) ，步長(zhǎng)，步長(zhǎng)取初始點(diǎn)取初始點(diǎn) ，步長(zhǎng)，步長(zhǎng)3( )21f xxx115 ( )(),28f xf( )()f xf xh因?yàn)椋?2x 1.2h 12x 1,2h 11 ()()(0)1,22f xhff搜索成功，步長(zhǎng)加倍；11 (+2 )(3 )(3)(1)0,22f xhhf xhff計(jì)算()(3 )f xhf

13、xh因?yàn)椋?搜索成功，步長(zhǎng)加倍；11 (3 +4 )(7 )(7)(3)22,22f xhhf xhff計(jì)算(3 )(7 )f xhf xh因?yàn)椋?搜索失敗，停止迭代；,7 0,3.xh xh得到搜索區(qū)間為得到搜索區(qū)間為 0.618法是求單峰函數(shù)極值的一種試探法，有的書上也稱為區(qū)法是求單峰函數(shù)極值的一種試探法，有的書上也稱為區(qū)間收縮法。間收縮法。 在搜索區(qū)間在搜索區(qū)間a,b上插入兩個(gè)點(diǎn)，將分為三個(gè)子區(qū)間，通過(guò)比較上插入兩個(gè)點(diǎn)，將分為三個(gè)子區(qū)間，通過(guò)比較2個(gè)插入點(diǎn)的函數(shù)值的大小，可刪去左邊或者右邊區(qū)間，使搜索個(gè)插入點(diǎn)的函數(shù)值的大小，可刪去左邊或者右邊區(qū)間，使搜索區(qū)區(qū)間縮短。重復(fù)上述過(guò)程，使搜索區(qū)

14、間不斷縮短，當(dāng)區(qū)間縮短到一間縮短。重復(fù)上述過(guò)程，使搜索區(qū)間不斷縮短，當(dāng)區(qū)間縮短到一定程度時(shí)，區(qū)間上各點(diǎn)都可以作為極小點(diǎn)的近似。定程度時(shí)，區(qū)間上各點(diǎn)都可以作為極小點(diǎn)的近似。 僅適用于求解單峰函數(shù)僅適用于求解單峰函數(shù)：設(shè)設(shè) f(x) 是定義在是定義在a, b上的函數(shù)，若上的函數(shù)，若 1） x* a, b 是是在在a, b上的最小點(diǎn)上的最小點(diǎn) ， 2） 若對(duì)任意若對(duì)任意 x1 , x2, a x1 f (x2); 2 若若x1 x* ，則，則 f (x1) f (x2).則稱則稱 f(x) 為為a, b上的單峰函數(shù)。上的單峰函數(shù)。 設(shè)設(shè) f：RR 在在a, b 上是單峰函數(shù)，上是單峰函數(shù)， a x1

15、 x2 b 。 那么那么 1若若 f (x1) f (x2)，則，則 x* x1 , b ,如左下圖如左下圖 2若若 f (x1) f (x2) ，則，則 x* a, x2 , 如右下圖如右下圖 a x1 x2 b a x1 x2 b考慮條件：考慮條件： 2對(duì)稱原則：對(duì)稱原則： x1 a = b- x2 （使（使“壞壞”的情況去掉，區(qū)間長(zhǎng)度不小于的情況去掉，區(qū)間長(zhǎng)度不小于“好好”的情況）的情況） 3保持縮減比原則保持縮減比原則 t =(保留的區(qū)間長(zhǎng)度原區(qū)間長(zhǎng)度保留的區(qū)間長(zhǎng)度原區(qū)間長(zhǎng)度) 不變。不變。 （使每次保留下來(lái)的節(jié)點(diǎn)，（使每次保留下來(lái)的節(jié)點(diǎn)， x1或或 x2 ，在下一次的比較中成，在下一

16、次的比較中成 為一個(gè)相應(yīng)比例位置的節(jié)點(diǎn)為一個(gè)相應(yīng)比例位置的節(jié)點(diǎn) ）。）。 推導(dǎo)縮減比推導(dǎo)縮減比 t : 如圖設(shè)第一次保留如圖設(shè)第一次保留a, x2 (去掉去掉x2 , b), 第二次第二次保留的長(zhǎng)度為保留的長(zhǎng)度為, x1 , 則則 x1 x2 b212(2)xxtbx整理整理 ： x2 = a + t ( b - ) x1 = a + t ( x2 -)結(jié)合式：結(jié)合式：t 2 + t 1 = 0 故故 t0.618注意注意: 上式有上式有 t 2 = 1-t , 故有故有 x1 = a+(1-t)(b-a)=a+0.328(b-a) x2 = a+t(b-a)= a+0.618(b-a)(25

17、1舍去負(fù)值t 優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一 個(gè)函數(shù)值，計(jì)算量小，程序簡(jiǎn)單個(gè)函數(shù)值，計(jì)算量小，程序簡(jiǎn)單缺點(diǎn)：收斂速度慢。缺點(diǎn)：收斂速度慢。黃金分割法（黃金分割法（0.618 法）的優(yōu)缺點(diǎn)法）的優(yōu)缺點(diǎn) ：試用試用0.618法求目標(biāo)函數(shù)法求目標(biāo)函數(shù) 的最優(yōu)解。的最優(yōu)解。 給定初始區(qū)間給定初始區(qū)間0,2，收斂精度，收斂精度第一次區(qū)間縮短計(jì)算過(guò)程：第一次區(qū)間縮短計(jì)算過(guò)程：計(jì)算兩點(diǎn)及對(duì)應(yīng)函數(shù)值：計(jì)算兩點(diǎn)及對(duì)應(yīng)函數(shù)值： 作數(shù)值比較，可見作數(shù)值比較，可見 ,再做置換：再做置換：3( )21f xxx2:1.236,bx=0.002.0,2ab10.382

18、()0.764,xaba1 ()0.0821, f x20.618()1.236,xaba2()0.4162,f x12()()f xf x1.2360.002ba20.764,x2 ()0.0821, f x , 0,1.236,a b第二次區(qū)間縮短計(jì)算過(guò)程：第二次區(qū)間縮短計(jì)算過(guò)程： 作數(shù)值比較，作數(shù)值比較， , ,再做置換：再做置換：10.382()0.472,xaba1 ()0.1612,f x12()()f xf x1:0.472,ax0.7880.002;ba第三次區(qū)間縮短計(jì)算過(guò)程：第三次區(qū)間縮短計(jì)算過(guò)程： 作數(shù)值比較，作數(shù)值比較， , ,再做置換：再做置換：2:0.944,bx20

19、.618()0.944,xaba2 ()0.0468, f x12()()f xf x0.4720.002ba22 , 0,1.236,0.764,()0.0821,a bxf x , 0.472,1.236,a b 110.764,( )0.0821,xf x 220.764,()0.0821,xf x , 0.472,0.944,a b 各次的迭代結(jié)果如下：各次的迭代結(jié)果如下：迭代次數(shù)迭代次數(shù)x1x2f (x1)f (x2)a,b|b-a|第第1次次0.7641.236-0.08210.41260,1.2361.236第第2次次0.4720.7640.1612-0.0821 0.472,1

20、.236 0.788第第3次次0.7640.944-0.0821 -0.0468 0.472,0.944 0.472第第4次次0.6520.764-0.0268 -0.0821 0.652,0.944 0.292第第5次次0.7640.832-0.0821 -0.0881 0.764,0.944 0.230第第6次次0.8320.906-0.0881 -0.0683 0.764,0.906 0.124缺點(diǎn)：收斂速度慢缺點(diǎn)：收斂速度慢優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一個(gè)函數(shù)優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一個(gè)函數(shù) 值，計(jì)算量小值，計(jì)算量小 設(shè)設(shè) f (x)在在 a ,b上可微，求

21、函數(shù)上可微，求函數(shù)f在在a,b的極小點(diǎn)，就是求的極小點(diǎn)，就是求函數(shù)導(dǎo)數(shù)為零的點(diǎn)。如果函數(shù)導(dǎo)數(shù)為零的點(diǎn)。如果 ，則在，則在(a,b)內(nèi)一定存在一點(diǎn)內(nèi)一定存在一點(diǎn)x，使得，使得 。為求極小點(diǎn)，可取。為求極小點(diǎn)，可取 ，若，若 , x 為最小點(diǎn)為最小點(diǎn), x= x0 ; , x0 在上升段在上升段, x* x0，去掉，去掉a, x0 .00fx00fx00fx 0,0,fafb 0fx02abx用用 或者或者 作新的區(qū)間作新的區(qū)間a,b，繼續(xù)這個(gè)過(guò)程，繼續(xù)這個(gè)過(guò)程，逐步將區(qū)間逐步將區(qū)間a,b縮小，縮小，當(dāng)區(qū)間當(dāng)區(qū)間a,b的長(zhǎng)度充分小時(shí)，可將的長(zhǎng)度充分小時(shí)，可將a,b的中點(diǎn)取做極小的中點(diǎn)取做極小點(diǎn)的近

22、似點(diǎn)的近似點(diǎn)。點(diǎn)。 0, a x0,x b優(yōu)點(diǎn)：計(jì)算量較少，而且總能收斂到一個(gè)局部極小點(diǎn)。優(yōu)點(diǎn)：計(jì)算量較少，而且總能收斂到一個(gè)局部極小點(diǎn)。缺點(diǎn)：收斂速度較慢缺點(diǎn)：收斂速度較慢0=2abx步驟步驟1：計(jì)算：計(jì)算步驟步驟2：若：若 ，令，令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟3； 若若 ，令，令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟3； 若若 ，停止，停止， 。步驟步驟3：若：若 ，則，則 ，停止，否則，轉(zhuǎn)步驟，停止，否則，轉(zhuǎn)步驟1.0ax00fx00fx00fx0bx0*xx|b a *2abx ：試用二分法求目標(biāo)函數(shù)試用二分法求目標(biāo)函數(shù) 的最優(yōu)解。的最優(yōu)解。 給定初始區(qū)間給定初始區(qū)間0,2，收斂精度，收斂精度在在0,2內(nèi)有極小點(diǎn)。

23、內(nèi)有極小點(diǎn)。3( )21f xxx0:1,bx故=0.004.(0)=2,(2)=10,ff01,2abx10.004;ba , 0,1,a b 第一次區(qū)間縮短計(jì)算過(guò)程：第一次區(qū)間縮短計(jì)算過(guò)程：2( )32,fxx因?yàn)橐驗(yàn)樗院瘮?shù)所以函數(shù)3( )21f xxx0()= (1)10fxf ，第二次區(qū)間縮短計(jì)算過(guò)程：第二次區(qū)間縮短計(jì)算過(guò)程：第三次區(qū)間縮短計(jì)算過(guò)程：第三次區(qū)間縮短計(jì)算過(guò)程：2 , 0,1,( )32,a bfxx1 , ,1,2a b 01:,2ax故01,22abx10.004;2ba015()= ()024fxf ，3 , ,1,4a b 03:,4ax故03,24abx10.0

24、04;4ba035()= ()0416fxf ，各次的迭代結(jié)果如下：各次的迭代結(jié)果如下：迭代迭代9次后，次后，|b-a|=0.003910.004, 故故迭代次數(shù)迭代次數(shù)x0=(a+b)/2f(x0)a,b|b-a|第第1次次x0=110,11第第2次次x0=1/2-5/41/2,11/2第第3次次x0=3/4-5/163/4,11/4第第4次次x0=7/819/643/4,7/81/8第第5次次x0=13/16-0.019513/16,7/81/16第第6次次x0=27/320.013613/16,27/321/32第第7次次x0=53/640.057413/16,53/641/64第第8次

25、次x0=105/1280.018413/16,105/1281/128第第9次次x0=209/256-0.0004209/256,105/1281/256*0.81836.x 對(duì)對(duì) f (x) 在在 x k 點(diǎn)二階泰勒展開：點(diǎn)二階泰勒展開：略去高階項(xiàng)得略去高階項(xiàng)得兩邊對(duì)兩邊對(duì)x求導(dǎo)，求導(dǎo)，令令 ，得到，得到 牛頓法是一種函數(shù)逼近法，牛頓法是一種函數(shù)逼近法，基本思想是：基本思想是：在極小點(diǎn)附近用在極小點(diǎn)附近用函數(shù)的二階泰勒多項(xiàng)式近似代替目標(biāo)函數(shù)，從而求得目標(biāo)函數(shù)函數(shù)的二階泰勒多項(xiàng)式近似代替目標(biāo)函數(shù)，從而求得目標(biāo)函數(shù)的極小點(diǎn)的近似值。的極小點(diǎn)的近似值。221( )()()()()()() )2kk

26、kkkkf xf xfxxxfxxxo xx21( )()()()()()2kkkkkf xf xf xxxfxxx( )()()()kkkf xf xfxxx( )=0f x()()kkkf xxxfx取取 作為新的迭代點(diǎn)，繼續(xù)迭代，直到達(dá)到精度，這樣就得到了作為新的迭代點(diǎn)，繼續(xù)迭代，直到達(dá)到精度，這樣就得到了函數(shù)函數(shù) f 的一個(gè)駐點(diǎn)的一個(gè)駐點(diǎn) 。1()=()kkkkf xxxfx*x步驟步驟1：給定初始點(diǎn)：給定初始點(diǎn) 令令 。步驟步驟2：計(jì)算：計(jì)算 。步驟步驟3：若：若 ，停止，停止， ，否則轉(zhuǎn)步驟，否則轉(zhuǎn)步驟4。步驟步驟4：計(jì)算：計(jì)算 令令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟2。10,xR，1k (),(

27、)kkf xfx()kf x*kxx1()=()kkkkf xxxfx1kk 特點(diǎn)：收斂速度快，局部二階收斂。特點(diǎn)：收斂速度快，局部二階收斂。缺點(diǎn)：須計(jì)算二次導(dǎo)數(shù)，工作量大；對(duì)初始點(diǎn)要求高，要求初缺點(diǎn)：須計(jì)算二次導(dǎo)數(shù)，工作量大；對(duì)初始點(diǎn)要求高，要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極小點(diǎn)；局部收斂小點(diǎn)；局部收斂。 ：試用試用Newton法求函數(shù)法求函數(shù) 的最優(yōu)解。的最優(yōu)解。432( )46164f xxxxx206,10 x0100()()fxxxfx(6)89664.75(6)69ff1211()()fxxxfx(4.

28、75)84.944.75=4.75=4.163(4.75)144.75ff21()(4.75)84.9410,fxf繼續(xù)迭代；22()(4.163)14.66610,fxf繼續(xù)迭代；32( )4121216,fxxxx2( )122412,fxxx2322()()fxxxfx(4.163)14.6664.1634.1634.010(4.163)96.055ff3433()()fxxxfx(4.010)0.84364.010=4.010=4.00004(4.010)84.7212ff24.163x 33()(4.010)0.843610,fxf繼續(xù)迭代；24()(4.00004)0.003410

29、,fxf得到近似解得到近似解*4.00004.x 用用 在在2 個(gè)或個(gè)或3 個(gè)點(diǎn)的函數(shù)值或?qū)?shù)值，構(gòu)造個(gè)點(diǎn)的函數(shù)值或?qū)?shù)值，構(gòu)造2 次或次或3次多項(xiàng)式作為次多項(xiàng)式作為 的近似值，以這多項(xiàng)式的極小點(diǎn)作為新的的近似值，以這多項(xiàng)式的極小點(diǎn)作為新的迭代點(diǎn)。包含迭代點(diǎn)。包含3點(diǎn)點(diǎn)2次，次，2點(diǎn)點(diǎn)2次，次，4點(diǎn)點(diǎn)3次，次，3點(diǎn)點(diǎn)3次，次，2點(diǎn)點(diǎn)3次等次等插值法插值法. 下面以下面以3點(diǎn)點(diǎn)2次插值法（二次插值法）為例：次插值法（二次插值法）為例：利用利用 在區(qū)間在區(qū)間 的函數(shù)值的函數(shù)值123xxx yf x 123fxfxfx作出如下的二次插值多項(xiàng)式作出如下的二次插值多項(xiàng)式 2012P xaa xa x它應(yīng)

30、滿足條件它應(yīng)滿足條件 210112111P xaa xa xffx（1） P x P x 220122222P xaa xa xffx 230132333P xaa xa xffx（2）（3）從極值的必要條件從極值的必要條件 求得求得 1220Pxaa x 12/ 2xaa 求出系數(shù)求出系數(shù) 和和 ，就可得到極小點(diǎn)的表達(dá)式。，就可得到極小點(diǎn)的表達(dá)式。1a2a 222222231312123122313121231/ 22xxfxxfxxfxaaxxfxxfxxf 11213212113121213231/ 2()2,.cxaaxxcffcffxxccxxxx 1. 尋找滿足如下條件的點(diǎn)（成功失

31、敗法尋找），成為兩頭大尋找滿足如下條件的點(diǎn)（成功失敗法尋找），成為兩頭大中間小的點(diǎn)：中間小的點(diǎn)： x 1 x 2 f (x2 ), f (x2 ) 0 , 則則 為為g(x)的極小值點(diǎn)，且的極小值點(diǎn)，且3.若若 ，則迭代結(jié)束，取，則迭代結(jié)束，取 ，否則在點(diǎn)，否則在點(diǎn) 中中，選取使，選取使f (x) 最小的點(diǎn)作為新的最小的點(diǎn)作為新的x2，并使新的并使新的x 1 ， x3各是新的各是新的x2近旁的左右兩點(diǎn)，繼續(xù)進(jìn)行迭代，直到滿近旁的左右兩點(diǎn)，繼續(xù)進(jìn)行迭代，直到滿足終止準(zhǔn)則。足終止準(zhǔn)則。x13,xx x2xx*xx123,x x x x算法思路：算法思路：2）用二次插值法逼近極小點(diǎn)）用二次插值法逼近

32、極小點(diǎn)(1) 相鄰三點(diǎn)及其函數(shù)值相鄰三點(diǎn)及其函數(shù)值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 1121321/ 2()2cxaaxxc ,例用二次插值法求函數(shù)例用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，的極小點(diǎn)， 給定給定 x0=0, h=1, =0.2。解：解：1）確定初始搜索區(qū)間）確定初始搜索區(qū)間初始區(qū)間初始區(qū)間a,b=0,2, 另有一中間點(diǎn)另有一中間點(diǎn)x2=1。1211312121323,ffcffxxccxxxx0 5550 292xf x.,( ).,根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn)根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn) (2) 在新區(qū)間，相鄰三點(diǎn)

33、及其函數(shù)值在新區(qū)間，相鄰三點(diǎn)及其函數(shù)值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.故新區(qū)間故新區(qū)間a,b=a,x2=0,1， 應(yīng)繼續(xù)迭代。應(yīng)繼續(xù)迭代。0 5550 292xf x.,( ).,x1=0, x2=1, x3=2; f1=2, f2=1, f3=18220 2921,0.5551,f xfxx( ).由于由于210.5550.4450.2,xx 1121321/ 2()2cxaaxxc ,1211312121323,ffcffxxccxxxx0 6070 243xf x.,( ).,根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn)根據(jù)公式計(jì)算差值多項(xiàng)式的

34、極小點(diǎn)故新區(qū)間故新區(qū)間a,b=x2,b=0.555,1， 迭代終止。迭代終止。x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1220 2430.292,0.6070.555,f xfxx( ).0, e 為全為全1的的m維列向量。維列向量。(7）是可行的）是可行的,基本可行解基本可行解 由于大由于大M是充分大的正數(shù)，在極小化目標(biāo)函數(shù)的過(guò)程中，就是充分大的正數(shù)，在極小化目標(biāo)函數(shù)的過(guò)程中，就會(huì)迫使人工變量離基。會(huì)迫使人工變量離基。同時(shí)修改目標(biāo)函數(shù)，加上懲罰項(xiàng)同時(shí)修改目標(biāo)函數(shù)，加上懲罰項(xiàng)minTTafc xMe x(7) 用單純形法求解用單純形法求解(7)，(ii

35、) 當(dāng)當(dāng) 時(shí)，時(shí)， (7)無(wú)可行解。無(wú)可行解。. .0,aAxxbstxminTTafc xMe x(7)*axx(i) 當(dāng)當(dāng) 時(shí)時(shí), x*是問(wèn)題是問(wèn)題(*)的最優(yōu)解。的最優(yōu)解。*=0axmin. .(*)0Tfc xAxbstx*0ax 事實(shí)上，如果事實(shí)上，如果(*)存在可行解存在可行解 ，則，則 是是(7)的可行的可行解，對(duì)應(yīng)解，對(duì)應(yīng)(7)的目標(biāo)函數(shù)值是的目標(biāo)函數(shù)值是 x0 axxx0TTc xMe是是(7)的最優(yōu)解的最優(yōu)解*axxTc x*TTac xMe x在單純形表中在單純形表中max()0,0,Nkkjjkj Rzczcy0ax. .0,aAxxbstxminTTafc xMe x

36、(7)(i) 當(dāng)當(dāng) 時(shí)，時(shí)，問(wèn)題問(wèn)題(LP)無(wú)界無(wú)界;min. .()0Tfc xAxbstLPx(ii) 當(dāng)當(dāng) 時(shí)，時(shí)，即即 ，問(wèn)題，問(wèn)題(LP)無(wú)可行解無(wú)可行解.0ax0Tae x 利用大利用大M法求解如下的線性規(guī)劃問(wèn)題。法求解如下的線性規(guī)劃問(wèn)題。 min x1+x2 -3x3 s.t. x1 -2x2 + x3 11 2x1 + x2 - 4x3 3 x1 - 2x3 = 1 x1, x2 , x3 0解解： 1. 將問(wèn)題化成標(biāo)準(zhǔn)形式將問(wèn)題化成標(biāo)準(zhǔn)形式，引進(jìn)松弛變量，引進(jìn)松弛變量x4 ,x5min x1+x2 -3x3 s.t. x1 -2x2 + x3 + x4 = 11 2x1 +

37、x2 - 4x3 - x5 = 3 x1 - 2x3 = 1 xj,0, j=1,2,5系數(shù)矩陣系數(shù)矩陣中不包含中不包含單位矩陣單位矩陣2. 引進(jìn)人工變量引進(jìn)人工變量x6 ,x7 構(gòu)造單位矩陣構(gòu)造單位矩陣，用單純形法求解下列問(wèn)題用單純形法求解下列問(wèn)題min x1+x2 -3x3+ M(x6 +x7) s.t. x1 -2x2 + x3 + x4 = 11 2x1 + x2 - 4x3 - x5 + x 6 = 3 x1 - 2x3 + x 7 = 1 xj,0, j=1,2,73. x4 ，x6 ， x 7 對(duì)應(yīng)的是單位矩陣，可選擇作為基變量，建立對(duì)應(yīng)的是單位矩陣，可選擇作為基變量，建立單純形

38、表，利用主元消去法，進(jìn)行迭代。單純形表，利用主元消去法，進(jìn)行迭代。xB x1 x2 x3 x4 x5 x6 x7 x4x6x711 3 13M-1 M-1 -6M+3 0 -M 0 0 x4x6x1 10 1 1 0 M-1 1 0 -M 0 1-3McBb j0MM113/2 1 j - 1 - 0M 1x4x2x1 j 12 1 1011c 1 1 -3 0 0 M M1 -2 1 1 0 0 02 1 -4 0 -1 1 01 0 -2 0 0 0 1min x1+x2 -3x3+ M(x6 +x7) s.t. x1 -2x2 + x3 + x4 = 11 2x1 + x2 - 4x3

39、- x5 + x 6 = 3 x1 - 2x3 + x 7 = 1 xj,0, j=1,2,70 -2 3 1 0 0 -10 1 0 0 -1 1 -21 0 -2 0 0 0 10 0 3 1 -2 2 -50 1 0 0 -1 1 -21 0 -2 0 0 0 1 0 0 1 0 -1 1-M -1-M 4 - - 0 0 0 -1/3 -1/3 1/3-M 2/3-M 4 1 9xB x1 x2 x3 x4 x5 x6 x7 cBbx4x2x1 j12 1 1011c 1 1 -3 0 0 M M0 0 3 1 -2 2 -50 1 0 0 -1 1 -21 0 -2 0 0 0 1

40、0 0 1 0 -1 1-M -1-M 4 - -x3x2x1 j-3 1 10 0 1 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -21 0 0 2/3 -4/3 4/3 -7/34. 檢驗(yàn)數(shù)全部小于等于檢驗(yàn)數(shù)全部小于等于0，并且人工變量全取，并且人工變量全取0， 于是得到最優(yōu)解：于是得到最優(yōu)解：最優(yōu)值為：最優(yōu)值為： f = 9+1-3*4=- 2 x = (9,1,4)T特點(diǎn)：目標(biāo)函數(shù)求極小值，約束條件特點(diǎn)：目標(biāo)函數(shù)求極小值，約束條件“”，變量非負(fù)，變量非負(fù); 目標(biāo)函數(shù)求極大值，約束條件目標(biāo)函數(shù)求極大值，約束條件“”，變量非負(fù)，變量非負(fù); : min. .0TPc xs

41、tAxbx: max. .0TTTDb ys ty Acy互為對(duì)偶互為對(duì)偶b不一定是非負(fù)的 一般稱不具有對(duì)稱形式的一對(duì)線性規(guī)劃為非對(duì)稱形式的對(duì)一般稱不具有對(duì)稱形式的一對(duì)線性規(guī)劃為非對(duì)稱形式的對(duì)偶規(guī)劃。偶規(guī)劃。 方法一：方法一： 對(duì)于非對(duì)稱形式的線性規(guī)劃，可以先化成對(duì)稱形式的線性對(duì)于非對(duì)稱形式的線性規(guī)劃，可以先化成對(duì)稱形式的線性規(guī)劃，寫出其對(duì)偶規(guī)劃。規(guī)劃，寫出其對(duì)偶規(guī)劃。123123123123123min284. .33305480424500,0,zxxxst xxxxxxxxxxxx無(wú)限制寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題12312354805480 xxxxxx

42、 110 xx 33333,0 xxxx x=12342450 xxx 123312331233123312331233min284(). .33()3054()8054()80424()50,0zxxxxstxxxxxxxxxxxxxxxxx x x x 123412341234123412341234max3080()50. .()4235()2834()4434()44,0wyyyystyyyyyyyyyyyyyyyyy yyy : min. .0TPc xs tAxbx: max. .0TTTDb ys ty Acy123412341234123412341234max3080()50

43、. .()4235()2834()4434()44,0wyyyystyyyyyyyyyyyyyyyyy yyy 154154154154145max308050. .423528344=4,0,wyyystyyyyyyyyyy yy無(wú)限制523=yyy無(wú)限制123434()4=4yyyy154154154154145max308050. .423528344=40,0,wyyystyyyyyyyyyyyy無(wú)限制44=0yy123123123123123max308050. .43523440,0wyyystyyyyyyyyyyyy無(wú)限制,123123123123min284. .3330548

44、042450zxxxst xxxxxxxxx 10,x 20,x 3x 無(wú)限制284原問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題123123123123123min284. .33305480424500,0,zxxxst xxxxxxxxxxxx無(wú)限制min. .0Tc xs tAxbxmax. .0TTTb ys ty Acymin. .0Tc xs tAxbAxbx min. .0Tc xAbs txAbxmax (,). . (,),0TTTTTbuvbAs tuvcAu v對(duì)偶問(wèn)題對(duì)偶問(wèn)題max (). . (),0TTTTTuvbs tuvAcu vyuv min. .0Tc xstAxbxmax

45、. .TTTy bsty Ac變量數(shù)：變量數(shù)：n個(gè)個(gè)第第 j 個(gè)變量個(gè)變量 0第第 j 個(gè)變量個(gè)變量 0第第 j 個(gè)變量是自由變量個(gè)變量是自由變量 約束條件：約束條件： m個(gè)個(gè)第第i個(gè)約束類型為個(gè)約束類型為“”第第i個(gè)約束類型為個(gè)約束類型為“”第第i個(gè)約束類型為個(gè)約束類型為“” 目標(biāo)函數(shù)目標(biāo)函數(shù)max對(duì)偶問(wèn)題（原問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）約束條件：約束條件：n個(gè)個(gè)第第 j 個(gè)約束類型為個(gè)約束類型為“”第第 j 個(gè)約束類型為個(gè)約束類型為“”第第 j 個(gè)約束類型為個(gè)約束類型為“” 變量數(shù)：變量數(shù)： m個(gè)個(gè)第第i個(gè)變量個(gè)變量 0第第i個(gè)變量個(gè)變量 0第第i個(gè)變量是自由變量個(gè)變量是自由變量 目標(biāo)函數(shù)目標(biāo)

46、函數(shù) min原問(wèn)題（對(duì)偶問(wèn)題）原問(wèn)題（對(duì)偶問(wèn)題）方法二：方法二：按照下面的對(duì)應(yīng)關(guān)系直接給出其對(duì)偶規(guī)劃按照下面的對(duì)應(yīng)關(guān)系直接給出其對(duì)偶規(guī)劃: :123123123123min284. .3354424zxxxst xxxxxxxxx10,x 20,x 3x 無(wú)限制123123123123max308050. .4352344wyyystyyyyyyyyy28480305010,y 2y 無(wú)限制，30y 變量數(shù)：變量數(shù)：n個(gè)個(gè)第第 j 個(gè)變量個(gè)變量 0第第 j 個(gè)變量個(gè)變量 0第第 j 個(gè)變量是自由變量個(gè)變量是自由變量 約束條件：約束條件： m個(gè)個(gè)第第i個(gè)約束類型為個(gè)約束類型為“”第第i個(gè)約束類型

47、為個(gè)約束類型為“”第第i個(gè)約束類型為個(gè)約束類型為“” 目標(biāo)函數(shù)目標(biāo)函數(shù)max對(duì)偶問(wèn)題（原問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）約束條件：約束條件：n個(gè)個(gè)第第 j 個(gè)約束類型為個(gè)約束類型為“”第第 j 個(gè)約束類型為個(gè)約束類型為“”第第 j 個(gè)約束類型為個(gè)約束類型為“” 變量數(shù)：變量數(shù)： m個(gè)個(gè)第第i個(gè)變量個(gè)變量 0第第i個(gè)變量個(gè)變量 0第第i個(gè)變量是自由變量個(gè)變量是自由變量 目標(biāo)函數(shù)目標(biāo)函數(shù) min原問(wèn)題（對(duì)偶問(wèn)題）原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題min. .0Tc xs tAxbxmax. .0TTTb ys ty Acy設(shè)設(shè) 分別是原問(wèn)題分別是原問(wèn)題 和對(duì)偶問(wèn)題和對(duì)偶問(wèn)題的可

48、行解的可行解, 則則 原問(wèn)題任一可行解對(duì)應(yīng)的目標(biāo)函數(shù)值不小于其對(duì)偶問(wèn)題的任原問(wèn)題任一可行解對(duì)應(yīng)的目標(biāo)函數(shù)值不小于其對(duì)偶問(wèn)題的任一可行解對(duì)應(yīng)目標(biāo)函數(shù)值。一可行解對(duì)應(yīng)目標(biāo)函數(shù)值。min. .0Tc xs tAxbxmax. .0TTTb ys ty Acy,x y.TTc xy bTc xTy AxTy b0 x TTy Ac0y Axb設(shè)設(shè) 分別是原問(wèn)題分別是原問(wèn)題 和對(duì)偶問(wèn)題和對(duì)偶問(wèn)題的可行解的可行解, 若若 則則 分別是它們的最優(yōu)解。分別是它們的最優(yōu)解。min. .0Tc xs tAxbxmax. .0TTTb ys ty Acy,x y,TTc xy b,x y若原問(wèn)題若原問(wèn)題 有最優(yōu)解，

49、則其對(duì)偶問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題一定有最優(yōu)解一定有最優(yōu)解, 且它們的目標(biāo)函數(shù)值相等。且它們的目標(biāo)函數(shù)值相等。min. .0Tc xs tAxbxmax. .0TTTb ys ty Acy約束優(yōu)化問(wèn)題的一般形式約束優(yōu)化問(wèn)題的一般形式( )0( )0( )0jjjh xh xh x因?yàn)橐驗(yàn)橐话阈问揭部蓪憺橐话阈问揭部蓪憺閙in( ). .( )0(*)f xst g x min( ). .( )0,1,2,.,(1)( )0,1,2,.,ijf xst g ximh xjl,xD( )0ig x ( )0ig x ( )，I x( ) |( )0,1,2, .iI xi g xim設(shè)可行解設(shè)可行

50、解，則稱，則稱是在是在處的處的積極積極約束約束指標(biāo)集，記為指標(biāo)集，記為若若x積極約束指標(biāo)的全體組成的集合，稱為積極約束指標(biāo)的全體組成的集合，稱為 處的積極約束處的積極約束xmin( ). .( )0,1,2,.,(1)( )0,1,2,.,ijf xst g ximh xjl或稱緊約束、或稱緊約束、起用作約束。起用作約束。處的處的,xD( )0ig x ( )0ig x ( ) |( )0,1,2,.iI xi gxim設(shè)設(shè)，則稱，則稱是在是在處的處的積極積極約束或稱緊約束、約束或稱緊約束、在在 積極約束指標(biāo)集積極約束指標(biāo)集若若xxmin( ). .( )0,1,2,.,(1)( )0,1,2

51、,.,ijf xst g ximh xjl222112212( )20,( )10,g xxxgxxx 2122( )2()0,22g x 22222( )()()1 0,22g x 22(,) ,22Tx 31( )0.gxx求在求在 的起作用約束集。的起作用約束集。x32( )0,2gx ( )1,2.I x令令因?yàn)橐驗(yàn)槠鹩米骷s束。起用作約束。 為為(1)的可行點(diǎn)，的可行點(diǎn)， 處可微，處可微， 在在 處連續(xù)處連續(xù), 在在 處連續(xù)處連續(xù) 向量集向量集 線性無(wú)關(guān)。線性無(wú)關(guān)。若若 是是(1)的局部最優(yōu)解，的局部最優(yōu)解，使得使得x證明：參見陳寶林書證明：參見陳寶林書 P253.x( )( )0 ,

52、iI xi g x( )ig iI xx( )iw iI x(1, )jvjl ( )1( )( )( )00,( )liijji I xjif xwg xvh xwiI x( ),( )( ),1,ijg xh x iI xjl (2)min( ). .( )0,1,2,.,(1)( )0,1,2,.,ijf xst g ximh xjlxx,( )if g iI x(1,., )jhjl在在可微，可微，則存在則存在 和和x( )ig iI x( )1( )( )( )00,( )liijji I xjif xwg xvh xwiI x(2)定理中的條件定理中的條件 在在 處連續(xù)變?yōu)檫B續(xù)可微

53、，則處連續(xù)變?yōu)檫B續(xù)可微，則11( )( )( )00,1,.,( )0,1,.,mliijjijiiif xwg xvh xwimw g xim(3)當(dāng)當(dāng) 時(shí)，時(shí)， ，由，由(3)可知，可知， 從從(3)中自然消失中自然消失,得到得到(2).( )iI x( )0ig x 0,iw ( )0( )iwg xiI x( )1( )( )( )00,( )liijji I xjif xwg xvh xwiI x(2)11( )( )( )00,1,.,( )0,1,.,mliijjijiiif xwg xvh xwimw g xim(3) (1)的一階必要條件是由的一階必要條件是由Kuhn和和Tu

54、chker與與1951年提出，年提出，故一階必要條件稱為故一階必要條件稱為K-T條件，條件，互補(bǔ)松弛條件互補(bǔ)松弛條件 1939年，年，Karush也類似考慮了約束優(yōu)化的最優(yōu)性條件，故一也類似考慮了約束優(yōu)化的最優(yōu)性條件，故一階必要條件稱作階必要條件稱作K-K-T條件，將條件，將K-T點(diǎn)稱作點(diǎn)稱作K-K-T點(diǎn)。點(diǎn)。滿足滿足(2)或或(3)的點(diǎn)是的點(diǎn)是K-T點(diǎn)。點(diǎn)。11( , , )( )( )( )(4)mliijjijL x w vf xw g xv h x11( )( )( )0mliijjijf xwg xvh x與與(3)中的第一個(gè)式子密切相關(guān)的是下面一個(gè)函數(shù)：中的第一個(gè)式子密切相關(guān)的是下

55、面一個(gè)函數(shù)：0 11( )( )( )mliijjijf xwg xvh x (3)( , , )xL x w v函數(shù)函數(shù)(4)的思想可追溯到的思想可追溯到Lagrange，故常被稱為，故常被稱為L(zhǎng)agrange函數(shù)，函數(shù)，其中其中 稱為稱為L(zhǎng)agrange乘子向量。乘子向量。11(,.,) ,( ,.,)TTmlwwwvvv0,1,.,( )0,1,.,iiiwimw g xim( )1( )( )( )00,( )liijji I xjif xwg xvh xwiI x(2)11( )( )( )00,1,.,( )0,1,.,mliijjijiiif xwg xvh xwimw g xi

56、m(3)滿足滿足(2)或或(3)的點(diǎn)是的點(diǎn)是K-T點(diǎn)點(diǎn) 若題目要求若題目要求K-T點(diǎn)點(diǎn) 求解求解(3.1)(3.3)，的的 就是就是K-T點(diǎn)點(diǎn); 若驗(yàn)證某點(diǎn)若驗(yàn)證某點(diǎn) 是否為是否為K-T點(diǎn)，求解點(diǎn)，求解(2.1)，它們的解中使得，它們的解中使得(2.2)成立的成立的 就是就是K-T點(diǎn)點(diǎn) .(2.1)(2.2)(3.1)(3.2)(3.3), xxxxnm l 個(gè)未知量nm個(gè)方程它們的解中使得它們的解中使得(3.2)成立成立123( )2,3xf xx21( ),gxx32( ),gxx 求約束極值問(wèn)題求約束極值問(wèn)題記記的的K-T點(diǎn)。點(diǎn)。112( )4,g xxx2212121212min( )

57、6684. .00f xxxxxxxstxx則則11( ),1g x21( ),0gx 30( ),1gx 11232311003101xx 31( )( )0,iiif xg x由由K-T條件條件得到得到11( )( )( )0 (3.1)0,1,.,(3.2)( )0,1,.,(3.3)mliijjijiiif xwg xvhxwimw g xim11232311003101xx 0,( )0,1,2,3iiig xi由由K-T約束條件約束條件21( )0gxx32( )0gxx112( )40g xxx再加上問(wèn)題本身的約束條件再加上問(wèn)題本身的約束條件聯(lián)立聯(lián)立(1-1),(1-2)和和(1

58、-3),求求x和相應(yīng)的乘子和相應(yīng)的乘子 1122133(1 1)3xx123,0 121240,0,0(13)xxxx1122132(4)000 xxxx(12)11( )( )( )0 (3.1)0,1,.,(3.2)( )0,1,.,(3.3)mliijjijiiif xwg xvhxwimw g xim， 得到得到12(1)0:xx若1121(4)00 xx由可得123 23 20 與矛盾。:0,0)2(21 xx若若30 2112x33 22x0 22x0 20 與矛盾。2 13200 xx11221333xx112(4)0 xx121212340,0,0 xxx x 1113x33

59、13x0 31x0 30 與矛盾。2 13200 xx11221333xx112(4)0 xx121212340,0,0 xxx x :0,0)3(21 xx若若20 :0,0)4(21 xx若若230 421 xx若若10 321 xx4621 xx矛盾。矛盾。421 xx221 xx11 22 1121x3x3 11221333xx112(4)0 xx2 13200 xx121212340,0,0 xxx x 12xx是是K-T點(diǎn)。點(diǎn)。1(1,1)Tx 2(0,0)Tx 221221212min(2)6. .00 xxstxxxx22212112212( )(2)6,( ),( )f xx

60、xg xxxgxxx112222(2)11( ),( ),( )221xf xg xgxxx11112211(),(),()221f xg xgx12( )0,( )0gxgx驗(yàn)證點(diǎn)驗(yàn)證點(diǎn)是否為是否為K-T點(diǎn)？點(diǎn)？記記 在點(diǎn)在點(diǎn)處，處，都是起作用約束，都是起作用約束，則則 1(1,1)Tx 目標(biāo)函數(shù)和約束函數(shù)的梯度分別是目標(biāo)函數(shù)和約束函數(shù)的梯度分別是( )( )( )0(2)0,( )iii I xif xw g xwi I x1( )ljjjv h x11112211(),(),()221f xg xgx故點(diǎn)故點(diǎn)是是K-T點(diǎn)。點(diǎn)。1(1,1)Tx 設(shè)設(shè)1221102210 121220220