優(yōu)化-第123章復習市公開課特等獎市賽課微課一等獎課件

要求：空集和單元素集也是凸集。三角形，矩形，圓，球，凸多邊形，第一象限，第一卦限等都是凸。等價定義（凸集）：設凸集與性質

定義（凸集）：若集合中任意兩點連線都屬于，則稱為凸集。因為兩點

連線上任一點能夠表示為

凸集幾何特征凸集代數(shù)特征稱集合為凸集。恒有凸集、凸函數(shù)與凸規(guī)劃

第1頁

例1:證實集合S={x∣Ax=b}是凸集，其中A為m

n矩陣，b為m維向量。凸集與性質

證實:即所以即S是凸集。例2:集合是凸集,稱為超平面，c為n維向量。例3：鄰域是凸集。第2頁定義：設那么稱是

凸組合。

性質2：S是凸集

S中任意有限個點凸組合屬于S。凸集與性質

性質1：設是凸集，則也是凸集。注：不一定是凸集。第3頁定義（凸函數(shù)）:設集合D

Rn為凸集，函數(shù)f:D

R,若x,y

D,

(0,1)，都有

f(

x+(1-

)y

)≤f(x)+(1-

)f(y)

，則稱f(x)為凸集D上凸函數(shù)。若深入有上面不等式以嚴格不等式成立，則稱f(x)為凸集D上嚴格凸函數(shù)。當-f(x)為凸函數(shù)(嚴格凸函數(shù))時，則稱f(x)為凹函數(shù)(嚴格凹函數(shù))。嚴格凸函數(shù)凸函數(shù)嚴格凹函數(shù)凸函數(shù)----推廣到多元函數(shù)第4頁定理(一階條件):

設D

Rn為非空凸集，函數(shù)f:D

R在D上可微，則(1)f在D上為凸函數(shù)任意x，y

D，恒有

f(y)

≥f(x)+

fT(x)(y-x)

(1)(2)

f在D上為嚴格凸函數(shù)任意x≠y

D，恒有

f(y)>f(x)+

fT(x)(y-x).(2)

凸函數(shù)判定定理第5頁定理（二階條件）:設D

Rn為含有內點非空凸集，函數(shù)f:D

R在D上二次可微，則a)f在D上為凸函數(shù)

x

D，2f(x)

半正定；b)若

x

D，2f(x)

正定，則f在D上為嚴格凸函數(shù)?；叵耄阂粋€矩陣半正定充要條件是全部主子式非負；一個矩陣正定充要條件是全部次序主子式非負。凸函數(shù)判定定理第6頁例：設二次函數(shù)(1)：若為半定矩陣，在中為凸函數(shù)；(2)：若為正定矩陣，在中為嚴格凸函數(shù)。例：判斷f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函數(shù)？次序主子式都是正，所以正定，所以f(x)在凸集D上是嚴格凸函數(shù)。凸函數(shù)判定定理第7頁定義（凸規(guī)劃）:考慮以下非線性規(guī)劃當都是凸函數(shù)時,稱規(guī)劃為凸規(guī)劃凸規(guī)劃第8頁性質1:

設(1)為凸規(guī)劃，則

i)(1)可行集R是凸集；

ii)(1)最優(yōu)解集是凸集；

iii)(1)任何局部極小點都是全局極小點。

性質2:

設(1)為凸規(guī)劃，若f(x)在非空可行集R上是嚴格凸函

數(shù)，則(1)全局極小點是唯一。

證實：見書中(P24)定理3.11.注:非線性規(guī)劃局部最優(yōu)解不一定是全局最優(yōu)解,其可行解和最優(yōu)解集也不一定是凸集,甚至不是連通集.如果是凸規(guī)劃,就有很多好性質。凸規(guī)劃性質證實：見書中(P23)定理3.9、3.10.第9頁普通情況下

,為正整數(shù),分別表示約束條件個數(shù)和決議變量個數(shù),為價值向量,

為決議向量,通常

為已知常數(shù)。稱m為線性規(guī)劃階數(shù),稱n為線性規(guī)劃維數(shù)。線性規(guī)劃標準形第10頁怎樣化成標準形若要求目標函數(shù)是:maxz=cTx,只需將目標函數(shù)最大值變換為求目標函數(shù)最小值,即maxz=min

(-z)。令zˊ=-z,于是得到：min

zˊ=-cTx。

目標函數(shù)轉換第11頁若約束方程組為不等式約束條件為“”形式不等式,則在“”號左邊加入非負松弛變量;把原“”形不等式變?yōu)榈仁?約束方程轉換：由不等式轉換為等式稱為松弛變量對應松弛變量在目標函數(shù)中價值系數(shù)取值為0。怎樣化成標準形第12頁約束條件為“”形式不等式,則可在“”號左端減去一個非負剩下變量。約束方程轉換：由不等式轉換為等式稱為剩下變量對應剩下變量在目標函數(shù)中價值系數(shù)取值為0。怎樣化成標準形第13頁

若存在取值無約束變量，可令

其中：

變量轉換若，可令，顯然怎樣化成標準形第14頁例1:試將以下線性規(guī)劃問題化成標準形任何形式線性規(guī)劃問題都能夠化成標準形?，F(xiàn)舉例以下：怎樣化成標準形第15頁解：令x3=x4-x5,x4,x50,

(1)式左端加上非負松弛變量x6

,(2)式左端減去非負剩下變量x7,則可將上述線性規(guī)劃問題化成以下標準形:怎樣化成標準形第16頁可行解（或允許解）:滿足約束條件解x=(x1,x2,···,xn)T

稱為線性規(guī)劃問題可行解;可行域：全部可行解集合稱為可行解集或可行域。3.最優(yōu)解:使得目標函數(shù)取到最小值可行解稱為線性規(guī)劃問題最優(yōu)可行解，簡稱為最優(yōu)解或者解。

線性規(guī)劃問題標準形為：線性規(guī)劃基本概念第17頁基:假設A是約束方程組系數(shù)矩陣,其秩數(shù)為m,B是矩陣A中由m列組成非奇異子矩陣(B行列式值不為0），則稱B是線性規(guī)劃問題一個基。矩陣B是由m個線性無關列向量組成,不失普通性,可假設:稱Pj(j=1,2,···,m)為基向量,與基向量Pj相對應變量xj(j=1,2,···,m)為基變量,不然稱為非基變量。線性規(guī)劃基本概念第18頁5.基本解：

若令(2.1)式中非基變量xm+1=···=xn=0,求出一個解x=(x1,x2,···,xm,0,···,0)T,這個解非0分量數(shù)目小于方程個數(shù)m,稱x為基本解。線性規(guī)劃基本概念當基本解中有一個或者一個以上基變量是0時，稱這個基本解是退化基本解。第19頁基本可行解:滿足非負約束條件基本解稱為基本可行解.基本可行解非0分量數(shù)目小于m,都是非負。7.可行基:對應于基本可行解基稱為可行基.約束方程組Ax=b基本解數(shù)目至多是Cnm個.普通地講,基本可行解數(shù)目要小于基本解數(shù)目,至多相等.以上提到幾個解概念,可用以下列圖來表示:基解可行解基本可行解線性規(guī)劃基本概念第20頁1947年,美國學者GeorgeDantzig(丹茨格)提出了求解線性規(guī)劃單純形法,為線性規(guī)劃推廣奠定了基礎。從可行域一個頂點(基本可行解)開始,轉移到另一個頂點(另一個基本可行解)迭代過程，轉移條件是使目標函數(shù)值得到改進(逐步變優(yōu)),當目標函數(shù)到達最優(yōu)值時,問題也就得到了最優(yōu)解?；舅枷雴渭冃畏ǖ?1頁重復以上過程，能夠深入改進基本可行解，直到全部時為止。單純形法基本原理基變量基變量非基變量非基變量初始基本可行解改進基本可行解目標函數(shù)值減小了進基變量確實定離基變量確實定f0是最優(yōu)值,當前基本可行解是最優(yōu)解第22頁以極小化問題為例每次迭代必出現(xiàn)以下三種情形之一(1).這時當前基本可行解就是最優(yōu)解。(2).這種情形下，我們知道取任何正數(shù)，總能得到可行解。所以當無限增大時，目標函數(shù)趨于負無窮，所以解無界。(3)，大于零。這時求出新基本可行解，經(jīng)迭代使目標函數(shù)下降。單純形法收斂性第23頁zk-ckymkyrky1k

……

zj-cj…zm+1–cm+10…0…0……ymj…ymm+11…0…0

……

…

……yrj…yrm+10…1…0

……

…

……y1j…y1m+10…0…1初始單純形表……………………………………………………使用表格形式單純形方法1.結構單純形表

xk是進基變量，是離基變量；主元把xk

所對應列向量pk變成所對應列向量，即是單位向量。把xk和

位置對換，第24頁對應新目標函數(shù)值即為：使用表格形式單純形方法2.高斯主元消去法以yrk

為主元素進行Gauss消元:將第r行每個元素除以yrk

:將第r行每個元素乘以–yik/yrk

加到第i行(i=1,···,m,

i≠r)將第r行每個元素乘以–(zk–ck)

/yrk

加到檢驗數(shù)行第25頁經(jīng)過Gauss消元后，針對于新基B1基本可行解為：使用表格形式單純形方法2.高斯主元消去法第26頁minx6+x7

s.t.x1+x2-

x3+x6=

2x1-x2-

x4+x7

=1x1+x5=3xj≥0,j=1,2,……,7例3.利用單純形算法求解以下線性規(guī)劃問題。解：

x6，x7，x5對應是單位矩陣，可選擇作為基變量，建立單純形表，利用主元消去法，進行迭代。第27頁xBx1x2x3x4x5x6

x7

11-100101-10-10011000100x6x7x5213

20-1-100002

-1101-11-10-1001010110-1x6x1x5112

02-1100-2cB1102131/2--2100x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000minx6+x7

s.t.x1+x2-

x3+x6=

2x1-x2-

x4+x7

=1x1+x5=3xj≥0,j=1,2,……,7c

000001

1

第28頁x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000xBx1x2x3x4x5x6

x7

cBc

000001

1

全部判別數(shù)zj-cj≤0

，所以到達最優(yōu)解第29頁兩階段法和大M法對于標準線性規(guī)劃問題(簡寫為LP):這里A=(aij)m

n,b≥0,

秩(A)=m.使用單純形方法，需要給定一個初始基本可行解，方便從這個基本可行解出發(fā)，求改進基本可行解。若A中包含m階單位矩陣，則初始基本可行解輕易找到。若A中不包含m階單位矩陣，初始基本可行解怎么找？初始基本可行解怎么找？

第30頁設A中不包含m階單位矩陣引入人工變量得到(5)一個基本可行解：顯然(5)系數(shù)矩陣中包含一個m階單位矩陣，取做基矩陣，人工變量人為引入變量個數(shù)變多了，線性規(guī)劃維數(shù)變大了把每個等式增加一個非負變量，得到怎樣排除人工變量，求出原線性規(guī)劃最優(yōu)解呢？慣用方法：兩階段法大M法第31頁

兩階段法第一階段是用單純形法消去人工變量(可能話)，即把人工變量都變換成非基變量，求出原來問題一個基本可行解。消去人工變量其中一個方法是解以下一個問題：其中e是分量全為1m維列向量，兩階段法基本思想第32頁

兩階段法基本思想設(6)最優(yōu)基本可行解是實際上，假如(LP)存在可行解，則是(6)可行解，對應(6)目標函數(shù)值是矛盾！是(6)最優(yōu)解這時，m個基變量都是原來變量，是(6)基本可行解，(i)若，則標準線性規(guī)劃(LP)沒有可行解；(ii)若，且xa

分量都是非基變量。是(LP)一個基本可行解。第33頁

兩階段法基本思想設(6)最優(yōu)基本可行解是此時最優(yōu)值是0.這時，可用主元消去法，把原來變量中非基變量引進基，替換出基變量中人工變量，此時最優(yōu)值一直都保持是0，從而就

得到(LP)一個基本可行解。第一階段結束，得到原來線性規(guī)劃一個基本可行解。(iii)若，且xa

一些分量是基變量?？苫癁榈?ii)種情況，第34頁兩階段法第二階段，就是從得到基本可行解出發(fā)，用單純形法求問題(*)最優(yōu)解。第35頁例1.利用兩階段法求解以下線性規(guī)劃問題。

min-2x1-x2

s.t.x1+x2≥

2x1-x2≥1x1≤3x1,x2≥0min-2x1-x2

s.t.x1+x2-

x3=

2x1-x2-

x4=1x1+x5=3xj≥0,j=1,2,…,5解：

1.首先把問題化成標準形式：系數(shù)矩陣中不包含單位矩陣第36頁minx6+x7

s.t.x1+x2-

x3+x6=

2x1-x2-

x4+x7

=1x1+x5=3xj≥0,j=1,2,……,7

2.

引進人工變量x6,x7結構單位矩陣，求解下面問題3.

x6，x7，x5對應是單位矩陣，可選擇作為基變量，建立單純形表，利用主元消去法，進行迭代。第37頁xBx1x2x3x4x5x6

x7

11-100101-10-10011000100x6x7x5213

20-1-100002

-1101-11-10-1001010110-1x6x1x5112

02-1100-2cB1102131/2--2100x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000minx6+x7

s.t.x1+x2-

x3+x6=

2x1-x2-

x4+x7

=1x1+x5=3xj≥0,j=1,2,……,7c

000001

1

第38頁x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000xBx1x2x3x4x5x6

x7

cBc

000001

1

4.全部判別數(shù)zj-cj≤0

，所以到達最優(yōu)解。從表中可看到：在一階段問題最優(yōu)解中，人工變量x6，x7都是非基變量。所以我們得到了原線性規(guī)劃基本可行解

第39頁xBx1x2x3x4x5

cB-1-2001-1/21/2010-1/2-1/20001/2-1/21x2x1x51/23/23/2min-2x1-x2

s.t.x1+x2-

x3=

2x1-x2-

x4=1x1+x5=3xj≥0,j=1,2,…,5

003/21/20c

-2-1000

5.第二階段，修改最終單純形表。x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000xBx1x2x3x4x5x6

x7

cBc

000001

1

修改檢驗數(shù)和目標函數(shù)，去掉人工變量對應列，其它不變。第40頁xBx1x2x3x4x5

x2x1x3233

000-1-3cB-1-20----3-1-2001-1/21/2010-1/2-1/20001/2-1/21x2x1x51/23/23/2

003/21/2001001100-11001-12c

-2-1000

6.這時，檢驗數(shù)全部小于等于0，得到最優(yōu)解：

x=(3,2,3,0,0)T目標函數(shù)最小值為：f=-2*3-1*2=-8第41頁大M法基本思想在約束中添加人工變量，M>0,e為全1m維列向量。(7）是可行,基本可行解因為大M是充分大正數(shù)，在極小化目標函數(shù)過程中，就會迫使人工變量離基。同時修改目標函數(shù)，加上處罰項經(jīng)過求解（7）而取得(*)最優(yōu)解第42頁用單純形法求解(7)，假如(7)存在有限最優(yōu)解，設為(ii)當時，(7)無可行解。(i)當時,x*是問題(*)最優(yōu)解。實際上，假如(*)存在可行解，則是(7)可行解，對應(7)目標函數(shù)值是M是充分大正數(shù)是(7)最優(yōu)解矛盾！第43頁在單純形表中假如(7)不存在有限最優(yōu)解(i)當時，問題(LP)無界;(ii)當時，即，問題(LP)無可行解.第44頁例3.利用大M法求解以下線性規(guī)劃問題。

minx1+x2-3x3

s.t.x1-2x2+x3≤112x1+x2-4x3≥3x1-2x3=1x1,x2,x3≥0解：

1.將問題化成標準形式，引進松弛變量x4,x5minx1+x2-3x3

s.t.x1-2x2+x3+

x4=112x1+x2-4x3-x5=3x1-2x3=1xj,≥0,j=1,2,…,5系數(shù)矩陣中不包含單位矩陣第45頁2.引進人工變量x6,x7

結構單位矩陣，用單純形法求解以下問題minx1+x2-3x3+M(x6+x7)

s.t.x1-2x2+x3+

x4=112x1+x2-4x3-x5+

x6=3x1-2x3+

x7=1xj,≥0,j=1,2,…,73.

x4，x6，x7對應是單位矩陣，可選擇作為基變量，建立單純形表，利用主元消去法，進行迭代。第46頁xBx1x2x3x4x5x6

x7

x4x6x711313M-1M-1-6M+30-M00x4x6x11011

0M-110-M01-3McB0MM113/21--1--0M1x4x2x11211011c

11-300M

M1-21100021-40-11010-20001minx1+x2-3x3+M(x6+x7)

s.t.x1-2x2+x3+

x4=112x1+x2-4x3-x5+

x6=3x1-2x3+

x7=1xj,≥0,j=1,2,…,70-23100-10100-11-210-200010031-22-50100-11-210-20001

0010-11-M-1-M4----第47頁

000-1/3-1/31/3-M2/3-M419xBx1x2x3x4x5x6

x7

cBx4x2x11211011c

11-300M

M0031-22-50100-11-210-20001

0010-11-M-1-M4----x3x2x1-3110011/3-2/32/3-5/30100-11-21002/3-4/34/3-7/34.檢驗數(shù)全部小于等于0，而且人工變量全取0，

于是得到最優(yōu)解：最優(yōu)值為：f=9+1-3*4=-2

x=(9,1,4)T第48頁(1)對稱形式 特點：目標函數(shù)求極小值，約束條件“≥”，變量非負;目標函數(shù)求極大值，約束條件“≤”，變量非負;對偶定義互為對偶第49頁普通稱不含有對稱形式一對線性規(guī)劃為非對稱形式對偶規(guī)劃。

方法一：對于非對稱形式線性規(guī)劃，能夠先化成對稱形式線性規(guī)劃，寫出其對偶規(guī)劃。(2)非對稱形式對偶問題對偶定義第50頁例1：寫出以下線性規(guī)劃問題對偶問題第51頁第52頁原問題對偶問題第53頁例2：標準形式對偶問題對偶定義對偶問題第54頁變量數(shù)：n個第j個變量≤0第j個變量≥0第j個變量是自由變量約束條件：m個第i個約束類型為“≥”第i個約束類型為“≤”第i個約束類型為“＝”目標函數(shù)max對偶問題（原問題）約束條件：n個第j個約束類型為“≤”第j個約束類型為“≥”第j個約束類型為“＝”變量數(shù)：m個第i個變量≤0第i個變量≥0第i個變量是自由變量目標函數(shù)min原問題（對偶問題）方法二：按照下面對應關系直接給出其對偶規(guī)劃:(2)非對稱形式對偶問題第55頁變量數(shù)：n個第j個變量≤0第j個變量≥0第j個變量是自由變量約束條件：m個第i個約束類型為“≥”第i個約束類型為“≤”第i個約束類型為“＝”目標函數(shù)max對偶問題（原問題）約束條件：n個第j個約束類型為“≤”第j個約束類型為“≥”第j個約束類型為“＝”變量數(shù)：m個第i個變量≤0第i個變量≥0第i個變量是自由變量目標函數(shù)min原問題（對偶問題）第56頁定理1(對稱性)對偶問題對偶是原問題對偶問題基本定理第57頁定理2(弱對偶定理)設

分別是原問題

和對偶問題可行解,

則

原問題任一可行解對應目標函數(shù)值大于其對偶問題任一可行解對應目標函數(shù)值。對偶問題基本定理第58頁定理3(最優(yōu)性定理)設

分別是原問題

和對偶問題可行解,

若

則分別是它們最優(yōu)解。對偶問題基本定理定理4(強對偶定理)若原問題

有最優(yōu)解，則其對偶問題一定有最優(yōu)解,

且它們目標函數(shù)值相等。第59頁n=1時，是一維無約束優(yōu)化問題---------第三章第1部分內容n>1時，是多維無約束優(yōu)化問題---------第三章第2部分內容n元函數(shù)求解無約束優(yōu)化問題第60頁找初始點判斷當前點是否滿足終止條件下一個迭代點最優(yōu)解(a)找初始點(b)終止條件(c)迭代格式找步長和下降方向，確定下一個迭代點不一樣對應不一樣算法是否循環(huán)線搜索迭代法框架分析不一樣對應不一樣算法第61頁求目標函數(shù)f(x)極?。阂驗檫@項工作是求以

為變量一元函數(shù)極小點，故常稱這一過程為（準確）一維搜索或線搜索迭代法框架分析----一維搜索（準確）線搜索或一維最優(yōu)化，確定步長為最正確步長。第62頁在搜索方向上所得最優(yōu)點處梯度和該搜索方向正交。定理設目標函數(shù)含有一階連續(xù)偏導數(shù)，規(guī)則產(chǎn)生則有（準確）一維搜索一個主要性質按下述證實：結構函數(shù)，則得即是函數(shù)極小點，所以第63頁“成功—失敗”法（進退法）基本思想：一個試探法：從一點出發(fā)，按一定步長搜索新點，若搜索成功，加大步長繼續(xù)搜索；若搜索失敗，縮小步長小步后退。第64頁“成功—失敗”法（進退法）步驟1：選取初始點x∈R,初始步長h>0及精度ε>0，步驟2：計算步驟3：若搜索成功,轉步驟4；不然，搜索失敗，轉步驟5。步驟4：令x:=x+h,轉步驟2。步驟5：判斷若停頓迭代，；不然令轉步驟2。缺點：效率低。優(yōu)點：能夠求搜索區(qū)間。注意：初始步長不能選得太小第65頁例1：設給定初始點為a及初始步長為h,求搜索區(qū)間[c,d]1)前進運算首先計算f(a),f(a+h),假如f(a)>f(a+h),則步長加倍,計算f(a+3h).若f(a+h)<=f(a+3h),則c=a,d=a+3h;不然將步長再加倍，并重復上面運算.2)后退運算假如f(a)<f(a+h),則將步長縮為原來1/4并改變符號，即將步長改為-h/4,假如f(a)<f(a-h/4),則c=a-h/4,d=a+h;不然將步長加倍，并繼續(xù)后退。注意:1.h選擇要適當.(太大含多個單峰區(qū)間,太小迭代次數(shù)多)；2.f(x)單調時無結果,(加迭代次數(shù)限制)；

“成功—失敗”法（進退法）第66頁0.618法（黃金分割法）0.618法是求單峰函數(shù)極值一個試探法，有書上也稱為區(qū)間收縮法。在搜索區(qū)間[a,b]上插入兩個點，將分為三個子區(qū)間，經(jīng)過比較2個插入點函數(shù)值大小，可刪去左邊或者右邊區(qū)間，使搜索區(qū)間縮短。重復上述過程，使搜索區(qū)間不?？s短，當區(qū)間縮短到一定程度時，區(qū)間上各點都能夠作為極小點近似。僅適合用于求解單峰函數(shù)第67頁例：利用“成功-失敗”法求函數(shù)搜索區(qū)間，取初始點，步長解：取初始點，步長“成功—失敗”法----算例得到搜索區(qū)間為第68頁0.618法（黃金分割法）

定義(單峰函數(shù))：設f(x)是定義在[a,b]上函數(shù)，若1）

x*∈[a,b]是φ在[a,b]上最小點，2）若對任意x1,x2,a≤x1<x2

≤b,滿足：1o若x2

≤x*，則f(x1)>f(x2);

2o若x1

≥x*，則f(x1)<f(x2).則稱f(x)為[a,b]上單峰函數(shù)。

第69頁定理：設f：R→R在[a,b]上是單峰函數(shù)，a≤x1<x2

≤b。那么1°若f(x1)≥f(x2)，則x*

∈[x1

,b],如左下列圖2°若f(x1)<f(x2)，則x*

∈[a,x2

],如右下列圖

α

x1

x2

b

αx1

x2

b0.618法（黃金分割法）縮短區(qū)間第一個標準---去壞留好標準選二點x1

<x2

,比較f(x1

)與f(x2

),可去掉[a,x1

]或者[x2,b].第70頁考慮條件：

2°對稱標準：x1–a=b-x2……①

（使“壞”情況去掉，區(qū)間長度大于“好”情況）

3°保持縮減比標準t=(保留區(qū)間長度／原區(qū)間長度)不變。

（使每次保留下來節(jié)點，x1或x2，在下一次比較中成為一個對應百分比位置節(jié)點）。推導縮減比t:如圖設第一次保留[a,x2](去掉[x2,b]),第二次保留長度為[α,x1],則αx1

x2b0.618法（黃金分割法）第71頁整理②：

x2=a+t(b-α)

x1=a+t(

x2-α)結合①式：t2+t–1=0

故

t≈0.618注意:上式有

t2=1-t,故有

x1=a+(1-t)(b-a)=a+0.328(b-a)x2=a+t(b-a)=a+0.618(b-a)0.618法（黃金分割法）第72頁

優(yōu)點：不要求函數(shù)可微，且每次迭代只需計算一個函數(shù)值，計算量小，程序簡單缺點：收斂速度慢。黃金分割法（0.618法）優(yōu)缺點0.618法（黃金分割法）第73頁例：試用0.618法求目標函數(shù)最優(yōu)解。給定初始區(qū)間[0,2]，收斂精度解：第一次區(qū)間縮短計算過程：計算兩點及對應函數(shù)值：作數(shù)值比較，可見,再做置換：0.618法----算例第74頁第二次區(qū)間縮短計算過程：作數(shù)值比較，,再做置換：第三次區(qū)間縮短計算過程：作數(shù)值比較，,再做置換：第75頁各次迭代結果以下：迭代次數(shù)x1x2f

(x1)f

(x2)[a,b]|b-a|第1次0.7641.236-0.08210.4126[0,1.236]1.236第2次0.4720.7640.1612-0.0821[0.472,1.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缺點：收斂速度慢優(yōu)點：不要求函數(shù)可微，且每次迭代只需計算一個函數(shù)值，計算量小第76頁

設f(x)在

[a,b]上可微，求函數(shù)f在[a,b]極小點，就是求函數(shù)導數(shù)為零點。假如，則在(a,b)內一定存在一點x，使得。為求極小點，可取，若

,x為最小點,x=x*;,x0

在上升段,x*<x0，去掉[x0

,b];

,x0

在下降段,x*>x0，去掉[a,x0].二分法---基本思想第77頁用或者作新區(qū)間[a,b]，繼續(xù)這個過程，逐步將區(qū)間[a,b]縮小，當區(qū)間[a,b]長度充分小時，可將[a,b]中點取做極小點近似點。二分法---基本思想第78頁優(yōu)點：計算量較少，而且總能收斂到一個局部極小點。缺點：收斂速度較慢二分法---計算步驟步驟1：計算步驟2：若，令，轉步驟3；若，令，轉步驟3；若，停頓，。步驟3：若，則，停頓，不然，轉步驟1.第79頁例：試用二分法求目標函數(shù)最優(yōu)解。給定初始區(qū)間[0,2]，收斂精度解：在[0,2]內有極小點。二分法----算例第一次區(qū)間縮短計算過程：因為所以函數(shù)第80頁第二次區(qū)間縮短計算過程：第三次區(qū)間縮短計算過程：第81頁各次迭代結果以下：迭代9次后，|b-a|=0.00391<0.004,故迭代次數(shù)x0=(a+b)/2f’(x0)[a,b]|b-a|第1次x0=11[0,1]1第2次x0=1/2-5/4[1/2,1]1/2第3次x0=3/4-5/16[3/4,1]1/4第4次x0=7/819/64[3/4,7/8]1/8第5次x0=13/16-0.0195[13/16,7/8]1/16第6次x0=27/320.0136[13/16,27/32]1/32第7次x0=53/640.0574[13/16,53/64]1/64第8次x0=105/1280.0184[13/16,105/128]1/128第9次x0=209/256-0.0004[209/256,105/128]1/256第82頁牛頓法（Newton）---基本思想對f(x)在xk點二階泰勒展開：略去高階項得兩邊對x求導，令，得到牛頓法是一個函數(shù)迫近法，基本思想是：在極小點附近用函數(shù)二階泰勒多項式近似代替目標函數(shù)，從而求得目標函數(shù)極小點近似值。第83頁牛頓法（Newton）---基本思想取作為新迭代點，繼續(xù)迭代，直到抵達精度，這么就得到了函數(shù)f一個駐點。第84頁牛頓法（Newton）---計算步驟步驟1：給定初始點令。步驟2：計算。步驟3：若，停頓，，不然轉步驟4。步驟4：計算令，轉步驟2。特點：收斂速度快，局部二階收斂。缺點：須計算二次導數(shù)，工作量大；對初始點要求高，要求初始點離極小點不太遠，不然有可能使極小化發(fā)散或收斂到非極小點；局部收斂。第85頁例：試用Newton法求函數(shù)最優(yōu)解。解：Newton法----算例第86頁Newton法----算例Newton法收斂速度快得到近似解第87頁用

在2個或3個點函數(shù)值或導數(shù)值，結構2次或3次多項式作為

近似值，以這多項式極小點作為新迭代點。包含3點2次，2點2次，4點3次，3點3次，2點3次等插值法.下面以3點2次插值法（二次插值法）為例：利用在區(qū)間函數(shù)值作出以下二次插值多項式它應滿足條件（1）插值法（2）（3）第88頁從極值必要條件求得求出系數(shù)和，就可得到極小點表示式。插值法---求二次插值多項式極小點第89頁1.尋找滿足以下條件點（成功失敗法尋找），成為兩頭大中間小點：x1<

x

2<x3，f(x1)>f(x2),f(x2)<f(x3

)2.兩頭大中間小，可得a2>0

,則為g(x)極小值點，且3.若，則迭代結束，取，不然在點

中，選取使f(x)最小點作為新x2，并使新x1，x3各是新x2近旁左右兩點，繼續(xù)進行迭代，直到滿足終止準則。插值法---算法思緒：第90頁2）用二次插值法迫近極小點(1)相鄰三點及其函數(shù)值:x1=0,x2=1,x3=2;

f1=2,f2=1,f3=18.例用二次插值法求函數(shù)f(x)=3x3-4x+2極小點，

給定x0=0,h=1,ε=0.2。解：1）確定初始搜索區(qū)間初始區(qū)間[a,b]=[0,2],另有一中間點x2=1。依據(jù)公式計算差值多項式極小點第91頁(2)在新區(qū)間，相鄰三點及其函數(shù)值:

x1=0,x2=0.555,x3=1;

f1=2,f2=0.292,f3=1.故新區(qū)間[a,b]=[a,x2]=[0,1]，應繼續(xù)迭代。x1=0,x2=1,x3=2;f1=2,f2=1,f3=18因為依據(jù)公式計算差值多項式極小點第92頁故新區(qū)間[a,b]=[x2,b]=[0.555,1]，迭代終止。x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1因為故第93頁目標是找中一點，使對，都有，稱為此無約束最優(yōu)化問題全局極小點。

無約束最優(yōu)化問題：求解無約束最優(yōu)化問題計算方法稱為無約束最優(yōu)化方法。多維無約束最優(yōu)化方法第94頁無約束最優(yōu)化方法應用廣泛，理論也比較成熟；可將約束優(yōu)化問題轉化為無約束優(yōu)化問題來處理；最優(yōu)化方法中基本方法---無約束優(yōu)化方法：利用函數(shù)一階或二階導數(shù)方法收斂速度快，需要計算梯度或者Hesse矩陣：僅利用函數(shù)值信息，尋找最優(yōu)解不包括導數(shù)，適用性強，但收斂速度慢可求得目標函數(shù)梯度時使用解析法在不可能求得目標函數(shù)梯度或偏導數(shù)時使用直接法我們介紹解析法第95頁最優(yōu)性條件(OptimalityConditions)所謂最優(yōu)性條件，是指最優(yōu)化問題最優(yōu)解所要滿足必要條件或充分條件。解析法要用到目標函數(shù)梯度或者Hesse矩陣，輕易想到利用一階必要條件將無約束優(yōu)化問題轉化成一個梯度為0確定方程組。這里用到一階必要條件就是最優(yōu)性條件。第96頁定理(一階必要條件)

設，若為