管理科學(xué)理論

1、第四章 約束非線性優(yōu)化的理論與方法一，等式約束問題1，切向量與正規(guī)性定義1 設(shè)x0 是由方程組gi(x)=0， i=1,2, ,m，確定的曲面S上的一點，若在S上存在曲線x(t)，x(0)= x0，x(0)=h，則稱向量是曲面S上點x0處的切向量。定義2：如果關(guān)于h 的線性方程組：系數(shù)矩陣1滿秩，則稱x0為曲面S上的一個正規(guī)點。注1 是x0處法空間的一組基。注2 方程組 的一組線性無關(guān)的解構(gòu)成曲面S上x0處切空間的一組基。2，具等式約束問題的極值必要條件考慮二維問題： min f (x,y) S.t. g (x,y)=0結(jié)論1:若在極小點(x0,y0)處,g (x0,y0) 0，則f (x0,

2、y0)與g (x0,y0)線性相關(guān)，即f (x0,y0) + g (x0,y0)=0。結(jié)論2：(Lagrange乘子規(guī)則)設(shè)(x0,y0)是局部極小點，且g (x0,y0) 0，則存在常數(shù) ，對函數(shù)F (x0,y0)= f (x0,y0)+ g (x0,y0)，滿足 F(x0,y0)= f (x0,y0) + g (x0,y0)=0.2結(jié)論3（充分條件）：設(shè)點x0滿足必要條件： F(x0)= f (x0) + g (x0)=0.若則x0是局部極小點。二，具不等式約束的問題1，下降方向和可行方向考慮一般非線性約束優(yōu)化問題：例：求解 31) 下降方向的選擇 如果方向P在點x0處是下降方向，則P應(yīng)與

3、f (x0)同側(cè)，即：記 為點x0處的下降方向集。2) 可行方向的選擇 在x0處的可行方向應(yīng)滿足:結(jié)論1：若 所有方向P都是可行的。結(jié)論2：若 當(dāng) 時4則P為可行方向。 記 為可行方向集。注：對等式約束而言，所有約束都是起作用約束。2，最優(yōu)性條件定義1：若對xC和0，有 xC ，則稱C為錐，如果C是凸的，則稱其為凸錐。定義2：設(shè)是約束集，稱為x0處的可行方向錐。 下面進一步討論最優(yōu)性條件。設(shè)x*是問題 的最優(yōu)解，則x*處5 換言之，在x*處滿足 的方向P必有 稱 為FritzJohn 條件。其中 線性無關(guān)。 在最優(yōu)點x*處應(yīng)滿足 Farkas引理：給定向量a i（i =1,2,k）與b，不存在

4、向量P同時滿足條件 和 的充要條件是 向量b 在ai 所張成的凸錐內(nèi)，即滿足 6定理1:設(shè)x*為問題的一個可行點,并且前t個約束為起作用約束,則x*為最優(yōu)解的一個必要條件是下式成立:例:考慮問題7從上例看出，滿足定理1還需增加一些約束規(guī)范，如梯度向量線性無關(guān)等，上例有 更一般的有：定理2（KuhnTucker）最優(yōu)性必要條件：在最優(yōu)點x*處，設(shè)線性無關(guān)，則存在滿足：稱上式為KT條件，滿足上式的點稱KT點。相應(yīng)的廣義Lagrange函數(shù)為：8例1：驗證以下問題在最優(yōu)解處K-T條件成立。解:例2: 9解:定理3 設(shè)x*是一個可行點，若存在使K-T條件成立，并且對應(yīng)的Lagrange函數(shù)的Hesse

5、n陣在子空間M上正定，則x*是一個嚴(yán)格的局部極小點。其中：注 若 線性無關(guān)，則M是約束集在x*處的切空間。10定理4： 凸規(guī)劃問題的可行K-T點必為最優(yōu)解。3，Lagrange函數(shù)的鞍點定義1：如果對有則稱點 是Lagrange函數(shù)： 的鞍點。定理5 ：若 是鞍點，則 是原問題的整體最優(yōu)解，但逆一般不成立。例 考慮非線性規(guī)劃問題：注 可驗證x*=(0,0)T是問題的極小點(在x*是處，取* =3，則K-T條件成立)。11下證其Lagrange函數(shù)沒有鞍點。 反證法 ，假設(shè)鞍點 存在，由定理5知， 必為問題的最優(yōu)解，故 , 由鞍點定義，對所有的x與， 有即: 由于當(dāng)x1=0，x2取充分大時，總能

6、使右端為負(fù)值，推出矛盾。鞍點迭代方法:設(shè)Lagrange函數(shù)其中為某個取定的步長，迭代過程中逐步縮小，每次迭代需計算兩迭代點之間的距離，如距離減小 被接受，否則縮小，最后當(dāng)兩點距離充分小時，迭代終止。124，對偶問題 原 對 問 偶 題： 問(1) 題(2) 例 考慮問題極小點為x*=(2,2)T，極小值為8，令 因此最優(yōu)點*= 4，最大值 (*)=8。131）對偶定理定理1（弱對偶定理）若x 是原問題（1）的可行解，而（，）是對偶問題（2）的可行解，則進一步有：定理2（對偶定理）： 是Lagrange函數(shù)鞍點的充要條件是：（i）x* 是原問題的解；（ii）*0，* 是對偶問題的解；（iii）

7、142）對偶問題的幾何解釋設(shè)原問題為： 對偶問題為：當(dāng)約束集S在映射（g，f）下的像G是非凸時，可能出現(xiàn)對偶間隙：三，常用非線性約束優(yōu)化的方法1，序列線性規(guī)劃法（Sequence Linear Programming）152, 序列無約束極小化方法例構(gòu)造新函數(shù)如下：為避免間斷，令新函數(shù)為：F（x）=f（x）+M p（x），其中M為某正數(shù)， 為某一連續(xù)可微函數(shù)。上例取16以下就不同的函數(shù)構(gòu)造方法分別介紹1）外罰函數(shù)法（外點法）上例中：注（1）對等式約束問題可取 （2）對不等式約束問題可取17(3) 對一般問題?。憾ɡ?設(shè) 的最優(yōu)解存在，Mk為滿足Mk+1 Mk (k =1,2, )的正數(shù)序列，

8、且Mk， 如果F(x, Mk)的極小點序列x (k)存在且收斂到x #，則x #為原問題的最優(yōu)解。注 由于 ，故常以此作為收斂判別準(zhǔn)則。182）內(nèi)罰函數(shù)法（內(nèi)點法）罰函數(shù)（響應(yīng)函數(shù)）： 對不等式約束問題，取懲罰因子為3）混合罰函數(shù)法 對一般約束問題記：19取罰函數(shù)為4）精確罰函數(shù)法 罰函數(shù)取為：例精確罰函數(shù)為：205）乘子法（1）等式約束問題Lagrange函數(shù)為罰函數(shù)為：其中的迭代公式為（2）不等式約束問題引入松弛變量得增廣Lagrange函數(shù)：21經(jīng)過推導(dǎo)得關(guān)于z的極?。?）具等式和不等式的問題增廣Lagrange函數(shù)為：22其中的迭代公式為例解 增廣Lagrange函數(shù)為：233，可行方

9、向法定理 如果方向p 滿足 則稱p是 x（k）處的可行下降方向。1）Zoutendijk可行方向法(1) 線性約束需求解如下線性規(guī)劃問題例24(2) 非線性約束(具不等式約束問題)點 處的可行方向P應(yīng)滿足但在此嚴(yán)格不等式約束下，可能得不到最優(yōu)解，為此將嚴(yán)格不等式改為為了避免 的選取過大或過小，引進新變量 ，于是找方向的線性規(guī)劃問題為:為避免拉鋸現(xiàn)象，引入 起約束可行方向法，起作用約束集改為：25全約束可行方向法：求解如下線性規(guī)劃問題： 設(shè)最優(yōu)解為（P（k）， k），若 k =0，則x（k）為最優(yōu)解，迭代終止。若 k 0, 則得到可行下降方向P（k） 。 例26取初始點 x(0) =(1/2，1

10、)T。得到找方向的線性規(guī)劃問題為：其最優(yōu)解為 ,可行下降方向為271）相關(guān)投影概念（1）正交互補空間（2）正交投影算子定理：設(shè)子空間 U 的基矩陣為 N，則(i) 從R到子空間U 的投影算子 f 可表為矩陣(ii)從R 到子空間 V=UT 的正交投影算子 q 可表為矩陣（3）正交投影算子的性質(zhì)2）線性約束問題28 設(shè) x 處起作用約束超平面的法矩陣為 N（其秩為 r）；Q 為從R n 到起作用約束超平面交集上的投影算子，則 (i) 如果 則 是可行下降方向。(ii) 如果當(dāng) 0，則 x 為K-T點。(3) 步長的選擇 先確定出不違反約束的最大步長，再求最優(yōu)步長。4) 非線性約束的處理 首先將約束線性化，即用迭代點處起作用約束曲面的切平面近似曲面，再用該點處負(fù)梯度方向作為近似搜索方向; 最后將29所求得的點投影到約束曲面上. (i) 約束線性化后, 原問題的近似問題為(ii) 拉回措施 設(shè)起作用約束的法矩陣為N，取方向 q=N，其中 應(yīng)滿足:線性化得:拉回方向:305, 直接法網(wǎng)格法 事實上是一種窮舉法，在約束區(qū)域上打網(wǎng)格，在全部網(wǎng)格點上計算目標(biāo)函數(shù)值，（在滿足約束的點上）通過比較目標(biāo)函數(shù)值，選出最優(yōu)點。隨機實驗法 ( Monte Carlo ) 在約束區(qū)域上隨機選出一些（實驗）點，希望這些點在區(qū)域內(nèi)的分布是均勻的，被選到的機會相同，由此認(rèn)識目標(biāo)函數(shù)的大致