最優(yōu)化方法教案

./第3章無約束最優(yōu)化方法無約束最優(yōu)化問題：,方法：迭代法●直線搜索：直線搜索方法：黃金分割法,拋物線插值法,平分法§3.1直線搜索一、黃金分割法二、平分法問題：設(shè),,,,并給出精度.求近似極小點和極小值?；驹恚涸趦?nèi)有極小點,且.令,若,則在內(nèi)有極小點,將的右邊一半去掉,得新的搜索區(qū)間;若,則在內(nèi)有極小點,將的左邊一半去掉,得新的搜索區(qū)間。計算步驟1．令；2．若,則轉(zhuǎn)4,否則；3．計算,若,則轉(zhuǎn)4；若,則,轉(zhuǎn)1；若,則,轉(zhuǎn)1；4．令,停止。注：若滿足條件的尚未得到,則可按以下步驟確定：首先任取一點,指定步長。1．計算,若,則,停止；若,則轉(zhuǎn)4；若,則；2．令；3．若,則,停止；若,則令,,停止；若,則令,轉(zhuǎn)2；4．令；5．若,則,停止；若,則令,,停止；若,則令,轉(zhuǎn)4。例：三、拋物線插值法§3.2最速下降法最速下降法,又稱梯度法。是最古老的一種算法。在每次迭代中,沿最速下降方向進(jìn)行搜索。迭代公式為：§3.3牛頓法設(shè)二次函數(shù)的最優(yōu)解存在,用梯度法迭代一次即得最優(yōu)解：。由極值的必要條件,有則若取,則。推廣到一般函數(shù),取其中,為在處的海色矩陣。一、牛頓法的基本思想：在迭代過程中將在點附近按泰勒公式展開,取到二次項以二次函數(shù)的極小點作為的極小點的第次近似：得牛頓法的迭代公式：………………〔*特殊地,若〔一維,〔*式為即為一維情形〔一維搜索的牛頓法的迭代公式。牛頓法的步驟已知及梯度,海色矩陣,給出精度。1．選定初始點,計算,,令；2．計算；若,則令,停止,否則；3．計算；4．計算,；5．計算；6．令,轉(zhuǎn)2。三、主要結(jié)論定理：已知目標(biāo)函數(shù)及梯度,正定,則由式〔*確定的為下降方向。證明：由正定,則也正定。又,則有則為下降方向。例1：例2：§3.4共軛方向法與共軛梯度法〔一共軛方向法一、共軛方向定義1：設(shè)為n階對稱正定方陣,若對于n維空間中的兩個非零向量和有,和正交,即,則稱向量和關(guān)于共軛,或稱和是共軛的。推廣：設(shè)為n階對稱正定方陣,n維非零向量滿足,即其中任何兩個向量都是共軛的,則稱向量組是共軛〔向量。特殊：當(dāng),共軛即為正交。例：定理1：設(shè)為n階對稱正定方陣,非零向量組為共軛,則此向量組線性無關(guān)。二、共軛方向法1.特點：第次迭代時所取的方向和以前各次迭代所取的方向都是共軛的。2.性質(zhì)設(shè)二次函數(shù),其中為n階正定矩陣,,為常數(shù),為初始點。定理2：設(shè)是n元二次函數(shù)的極小點,方向為共軛,是由共軛方向法產(chǎn)生的點列,則至多迭代n次就能夠達(dá)到極小點?！矊τ诙魏瘮?shù),該性質(zhì)稱為二次終止性共軛方向的形成可以概括為以下定理：定理3：設(shè)1o二次函數(shù),為n階正定矩陣,為初始點；2o；3o；4o若,則確定方向：則i>都是下降方向;ii>是共軛的;iii>,;iv>,.<二>共軛梯度法一、系數(shù)的其它形式1.對于上述二次函數(shù),由,得〔由3o：>則有————SW共軛梯度法2.由,,得〔由4o：則有————FR共軛梯度法3.————PRP共軛梯度法二、最佳步長的計算公式由有得最佳步長：三、FR共軛梯度法的步驟〔適用于一般非線性函數(shù),包括二次函數(shù)已知初始點及收斂精度。1．計算；若,令,停；否則2．令,,轉(zhuǎn)63．按FR公式計算：,4．令,若,轉(zhuǎn)8；否則5．若,轉(zhuǎn)8；否則6．作線搜索：7．計算；若,則令,停；否則轉(zhuǎn)38．令,,,,轉(zhuǎn)6；例：試用FR共軛梯度法求下列函數(shù)的極小點,取初始點。解：§3.5步長加速法§3.6方向加速法〔Powell法方向加速法,又稱Powell法,是無約束最優(yōu)化的直接方法之一。一、基本思想：在迭代過程中的每個階段都作n+1次線搜索。首先,依次沿給定的n個線性無關(guān)的方向作線搜索,再沿由這一階段的起點到第n次搜索所得點的方向作一次線搜索,把這次所得的點作為下一階段的起點。下一階段的n個搜索方向。二、步驟設(shè)的極小點的初始近似為,控制誤差為。取n個線性無關(guān)的方向,是第個分量為1的單位向量。1．,；2．,；3．作線搜索：令4．令；5．若,則轉(zhuǎn)3,否則；6．；7．作線搜索：令8．若或。則轉(zhuǎn)10,否則；9．令,〔可略,,轉(zhuǎn)2；10．令,停.例：設(shè),初始點為.試用Powell法求的極小點。解：1.第一次迭代,.<1>；取.<或><為常數(shù)>令得.于是得<2><為常數(shù)>令得.于是得<3>；令得.于是得2.第二次迭代,.<1>起點；取.令得.于是得<2>令得.于是得<3>；令得.于是得.,則§3.7最小二乘問題的解法一、最小二乘問題多參數(shù)曲線擬合問題：確定函數(shù),其中,參數(shù)待定。問題：已知個實驗點：,試確定個參數(shù),從而建立回歸方程。解：首先得到"偏差"〔或距離：原問題轉(zhuǎn)化為：,求出回歸方程：上述方法稱為最小二乘法。簡記：則上述問題轉(zhuǎn)化為或〔*式〔*稱為最小二乘問題的一般形式；當(dāng)是線性向量函數(shù)時,稱為線性最小二乘問題；否則稱為非線性最小二乘問題。二、最小二乘法1.線性最小二乘問題〔1線性最小二乘問題如下：〔**其中,是矩陣,是維向量?！?預(yù)備引理引理1：對任意矩陣,則都是半正定的。證明：對,。引理2：設(shè)是矩陣,則正定的充要條件是為列滿秩的,即。引理3：設(shè)是矩陣,則正定的充要條件是為行滿秩的,即。推論1：正定非奇異?！惨驗樘卣髦怠?主要結(jié)論定理1：是線性最小二乘問題〔**的極小點的充要條件是是如下方程組的解：上式稱為法方程組。證明：令,則是可微凸函數(shù)。由性質(zhì)知,是極小點的充要條件是即推論2：設(shè)為列滿秩,則是〔**的唯一全局極小點〔稱為最小二乘解。例：2.非線性最小二乘問題第4章約束最優(yōu)化方法§4.1最優(yōu)性條件〔一等式約束問題的最優(yōu)性條件一、等式約束問題〔1二、最優(yōu)性條件定理1：〔一階必要條件假設(shè)〔1為等式約束<1>的局部極小點；〔2在的某鄰域內(nèi)連續(xù)可微；〔3線性無關(guān)。則存在使得〔*其中,引入的Lagrange函數(shù)定理2〔二階充分條件假設(shè)〔1是二階連續(xù)可微函數(shù)；〔2存在與使得〔即式〔*成立〔3對于滿足的任意非零向量,都有則點是問題<1>的嚴(yán)格局部極小點。注：稱為處的切子空間,即各個切平面交集上的點的集合。上述不等式即為Lagrange函數(shù)的海色矩陣在切子空間上正定。例：〔二只含不等式約束問題的最優(yōu)性條件一、不等式約束問題〔2記容許域。二、幾何最優(yōu)性條件1.容許方向定義1：設(shè)〔容許點,若,則稱為的起作用約束；若,則稱為的不起作用約束。注：1在起作用約束的邊界上；2等式約束都是起作用約束。例：定義2：設(shè),對于非零向量,若存在,使對,均有則稱方向是點的一個容許方向。性質(zhì)1〔容許方向的必要條件：若是容許點的任一容許方向,且〔在點處可微,〔在點處連續(xù),則對點的所有起作用約束,,均有〔銳角關(guān)系證明：由是容許方向,則存在,對,均有由及泰勒公式：有證畢性質(zhì)2〔容許方向的充分條件：設(shè)容許點的起作用約束〔在該點處可微,〔在該點處連續(xù),且方向滿足：,則是點的一個容許方向。證明：由泰勒公式：1考慮情形.由,即是在點處的上升方向,則存在,使對,均有2考慮情形.由函數(shù)的連續(xù)性從而存在,使對,均有綜上,取,當(dāng)時,對所有的均有,即于是是點的一個容許方向。證畢2．下降方向定義3：對容許點的任一方向,若存在,對,均有則稱方向是的一個下降方向。性質(zhì)3設(shè)在點可微。1°為下降方向〔必要條件2°為下降方向〔充分條件證明類似于容許方向的證明。定義4：若方向既是點的容許方向,又是下降方向,則稱它是的容許下降方向。定理3〔幾何最優(yōu)性條件：設(shè)是非線性規(guī)劃〔2的一個局部極小點,目標(biāo)函數(shù)在處可微,且1°〔在處可微；2°〔在處連續(xù)。則在處不存在容許下降方向,即不存在方向滿足…〔*‘幾何意義：滿足〔*‘的方向與處目標(biāo)函數(shù)負(fù)梯度方向的夾角成銳角,與處起作用約束梯度方向的夾角也成銳角。例：三、庫恩—塔克條件〔Kuhn-Tucker定理4〔K—T條件：設(shè)是非線性規(guī)劃〔2的局部極小點,在點處可微,且點處的全部起作用約束的梯度線性無關(guān),則存在實數(shù),使下述條件成立〔**式〔**又稱為庫恩—塔克條件〔K—T條件,且滿足該條件的點稱為庫恩—塔克點〔K—T點。推論1：若位于容許域的內(nèi)部且為〔P的局部極小點,則證明：所有約束都不起作用,則,則?！布醇s束不起作用事實上是個無約束問題,由極值條件即得下面考慮位于容許域的邊界情形。結(jié)論1：若是極小點,則必與在一條直線上且方向相反,其中為的起作用約束〔。由結(jié)論1,則存在使得。結(jié)論2：若,,則在極小點處,必處于與的夾角之內(nèi)。由結(jié)論2,當(dāng)和線性無關(guān)時,存在使即推廣得若再考慮不起作用約束,有其中,當(dāng)時；時,即定義5：設(shè),若在點的全部起作用約束的梯度線性無關(guān),則稱為正則點。例：〔三一般約束問題的最優(yōu)性條件考慮一般的非線性規(guī)劃<NP>：s.t.〔3記。定理5〔K—T條件：設(shè)是〔NP的局部極小點,在點處可微,且點處的全部起作用約束的梯度線性無關(guān)〔即是正則點,則存在實數(shù),使下述條件成立〔***式中,稱為Lagrange乘子。例：〔四凸規(guī)劃問題的最優(yōu)性條件凸規(guī)劃問題：s.t.〔4其中,是可微凸函數(shù),是可微凹函數(shù),是線性函數(shù)。定理6〔凸規(guī)劃的極值：若是凸規(guī)劃〔4的K—T點,則為全局極小點。例：§4.2Zoutendijk容許方向法容許方向法是從已知容許點出發(fā)〔設(shè)不是K—T點,沿容許下降方向作直線搜索,從而獲得一個改進(jìn)了的容許點。〔一線性約束的情形線性約束最優(yōu)化問題〔1其中,是矩陣,是矩陣,是維向量,是維向量,是可微函數(shù)。一、下降容許方向的確定1.容許方向的確定定理1：在約束問題〔1中,假設(shè)i是容許點；ii不妨設(shè),使得〔起作用約束,〔不起作用約束則非零向量為點的容許方向向量的充要條件是,〔2證明：〔必要性設(shè)為點的容許方向,即存在,使對,均有,又有,代人上式,即有〔2成立?！渤浞中栽O(shè)滿足<2>。1°對點的所有起作用約束及,均有2°對點的所有不起作用約束,則存在,使對,有綜上,對于上述的,當(dāng)時,是容許點,故是點的容許方向。證畢注1：對點的起作用約束,令,則由容許方向的必要條件,有〔銳角或直角關(guān)系2.容許下降方向的確定尋找容許下降方向的問題轉(zhuǎn)化為：〔LP〔因為時,為下降方向為保證目標(biāo)函數(shù)有界,或規(guī)定i；ii；iii；iv。于是確定容許下降方向的線性規(guī)劃為：s.t.〔3其中,。注2：因0是〔3的容許解,則；若,則最優(yōu)解就是點的一個容許下降方向。二、直線搜索從點出發(fā),沿容許下降方向作直線搜索,即為保證點仍是容許點,直線搜索為s.t.又由〔2和已知：,,,點的起作用約束是多余的,問題化簡為s.t.令〔因1°當(dāng)時,約束恒成立,則的上界；2°當(dāng)時,,取上界從而