最優(yōu)化理論與算法課件

1、最優(yōu)化理論與算法帥天平北京郵電大學(xué)數(shù)學(xué)系7， 最優(yōu)性條件2022/7/271最優(yōu)化理論第七章 最優(yōu)性條件無約束問題的極值條件約束極值問題的最優(yōu)性條件對(duì)偶及鞍點(diǎn)2022/7/272最優(yōu)化理論7.1無約束問題的極值條件考慮非線性規(guī)劃問題1，無約束極值問題稱為無約束極值問題（UNLP）7. 最優(yōu)性條件-無約束12022/7/273最優(yōu)化理論7. 最優(yōu)性條件-無約束2Th7.1.1(非極小點(diǎn)的充分條件) 設(shè)f(x)在點(diǎn)x*處可微,若存在方向d(0)Rn,使得f(x*)d0,使得對(duì)任意(0,),有f(x*+d)f(x*).此時(shí),我們稱d 為f(x)在x*的一個(gè)下降方向.證明. 由 f(x) 在 x* 可

2、微, 則 f(x*+d)=f(x*) + f(x*)d+|d|(x*;d), 其中 (x*;d) 0(當(dāng) 0). 2，必要條件2022/7/274最優(yōu)化理論7. 最優(yōu)性條件-無約束3移項(xiàng)且兩邊同除以( 0),得（f(x*+d)f(x*)）/ f(x*)d+|d|(x*;d)由于 f(x*)d 0 使得對(duì) 任意(0, ), f(x*)d+|d|(x*;d)0 .定理立明.定理7.1.2-3(極小點(diǎn)的必要條件)設(shè)x*處是問題(UNLP)的局部極小點(diǎn).當(dāng) f(x) 在 x*可微時(shí),則梯度 f(x*)=0. 當(dāng)f(x) 在 x*二次可微時(shí). 則 f(x*)=0 且 Hessian 矩陣 H(x*) 是

3、半正定的2022/7/275最優(yōu)化理論7. 最優(yōu)性條件-無約束4(2). 給定任意向量 d. 由 f(x) 在 x*的二次可微性，有f(x*+d)=f(x*) +f(x*)d+ dH(x*)d/2+ |d| (x*;d) (I), 其中 (x*;d) 0( 0). 由（1）的證明有 f(x*)=0. 移項(xiàng)整理并兩端除以 , 得 =dH(x*)d/2+|d| (x*;d) (II).因 x* 局部極小, 對(duì)充分小 有f(x*+d)f(x*) 2222 f(x*+d)f(x*)22證明(1). 若f(x*)0, 作 d=f(x*). 則有 f(x*) d 0 使得 f(x*+d)f(x*)， (0

4、, ), 此與 x* 為局部極小相矛盾，故 f(x*)=0.2022/7/276最優(yōu)化理論7. 最優(yōu)性條件-無約束5dH(x*)d/2+|d| (x*;d)0 2由(II), 顯見對(duì)充分小的 成立 , 對(duì) 0取極限, 則有 dH(x*)d 0, 從而,H(x*) 半正定定義1 若f(x)在點(diǎn)x*處可微,且f(x*)=0,則稱x*為f(x)的一個(gè)駐點(diǎn)或平穩(wěn)點(diǎn).d(0)Rn, 既不是極大點(diǎn)也不是極小點(diǎn)的駐點(diǎn)稱為鞍點(diǎn).Th7.1.4 (二階充分條件). 假設(shè) f(x) 在 x*點(diǎn)二次可微,若 f(x*)=0 且 Hessian 矩陣 H(x*) 是正定的,則 x* 是(UNLP)的一個(gè)(嚴(yán)格)局部極

5、小點(diǎn)3，二階充分條件2022/7/277最優(yōu)化理論7. 最優(yōu)性條件-無約束6證明. 因 f 在 x* 二次可微,故對(duì)任意 x, 有 f(x)=f(x*)+f(x*)(x-x*)+(x-x*)H(x*)(x-x*)/2+|x- x*| (x*; x- x*), 這里 (x*; x- x*) 0,當(dāng) xx*. 假設(shè)命題不真， x* 不是局部極小, 則存在序列 xk 收斂到 x* 并使得 f(xk) 0 使得 f(x*+d)f(x*)（ (0, )）,則 d 稱為 f(x) 在 x*的下降方向(decedent direction)設(shè) f(x) 在 x*可微. 若存在向量 d 滿足 f(x*)d0,

6、 則 由Th7.1.1, d 是 f(x) 在 x*.的下降方向。記所有這樣的向量集合為2022/7/2714最優(yōu)化理論7. 最優(yōu)性條件-有約束3由可行方向定義和下降方向知， 從點(diǎn) x*, 沿可行方向 dD(x*) 作一個(gè)很小的移動(dòng)還是可行點(diǎn). 進(jìn)一步，由 Th 7.1.1, 若 f(x*)d0 ，則d 是f在 x*的下降方向。下面定理將說明 若 x* 是局部最優(yōu)且 f(x*)d0, 則 dD(x*).即不是可行方向。Theorem 7.2.1. (必要條件) 考慮極小化問題： min f(x) ，subject to xS,其中 S 是 Rn 中非空集合，設(shè) f(x) 在 x*可微。若 x*

7、 是局部極小點(diǎn)，則 F0(x*)D=,其中 F0(x*)=d |f(x*)d0, f(x*+d)0， x*+dS ， (0, 2)此與局部極小矛盾。2022/7/2716最優(yōu)化理論177. 最優(yōu)性條件-不等式約束1為把最優(yōu)性的幾何條件用代數(shù)來表示，引入起作用約束的概念。問題的約束條件在點(diǎn)x*S處有兩種情形3 不等式約束的一階最優(yōu)性條件1，I= i| gi(x*)=0在x*處起作用約束2， gi(x*)0. iI在x*處不起作用約束G0(x*)=d |gi(x*)d0 , iI .2022/7/27最優(yōu)化理論187. 最優(yōu)性條件-不等式約束2證明概要. 設(shè) dG0(x*).因 S 為開集，則存在

8、 10 使得對(duì) (0, 1)， x* +d S。 另外存在 20使得對(duì) (0, 2) ，iI. gi(x*+d)0,最后存在 30 使得對(duì)任意 (0, 3) and iI有g(shù)i(x*+d)gi(x*), 從而 dD, D 是 x*處的可行方向錐. 于是G(x*)D. 由Th 7.2.1, 立明。Th7.2.2. (必要條件) 考慮極小化問題 min f(x) subject to gi(x)0， i=1, m ，xS, 其中 S 是 Rn中的非空開集。 設(shè) x* 為可行點(diǎn)， I= i| gi(x*)=0. 進(jìn)一步假設(shè)， f(x) 和 gi(x) （ iI ）在 x* 可微， gi （ iI）

9、在 x*連續(xù). 若 x* 是局部最優(yōu)解，則 F0(x*)G0(x*)=, 其中F0(x*)=d |f(x*)d0， iI .2022/7/27最優(yōu)化理論7. 最優(yōu)性條件-不等式約束3g1(x)=-x - y + 5,g2(x)=-x - y + 3,g3(x)=x,g4(x)=y； I=2f(x)2(x 3),2(y 2) 2 2Min (x-3) + (y-2) s.t. x + y 5 x + y 3 x, y 0.2 222f(x*)g2(x*)(9/5, 6/5)F(x*)G(x*). g2(x)g1(x)x*2022/7/2719最優(yōu)化理論7. 最優(yōu)性條件-不等式約束4Min (x-

10、3) + (y-2) s.t. x + y 5 x + y 3 x, y 0.2 222x*=(2, 1)g1(x*)=(-4, -2),g2(x*)=(-1, -1),f(x*)(-2, -2)f(x*)g1(x*)x* 是最優(yōu)解g2(x*)(2,1)x*2022/7/2720最優(yōu)化理論7. 最優(yōu)性條件-不等式約束5Th7.2.3. (Fritz John Condition, 1948)考慮極小化問題 min f(x) subject to gi(x)0， i=1, m ，xS, 其中 S 是 En.中非空開集. 設(shè) x* 為可行點(diǎn), I= i| gi(x*)=0. 進(jìn)一步假設(shè) f(x)

11、和 gi(x)( iI )在 x* 可微, gi ( iI) 在 x*連續(xù). 若 x* 是局部最優(yōu)解.則存在一組非負(fù)數(shù) u0 , ui ( iI )使得 u0f(x*) - uigi(x*)=0, u0, ui0 for iI and (u0, uI)0.iI進(jìn)一步, 若 gi(x) ( iI) 在 x*也可微，則 u0f(x*) uigi(x*)=0, uigi(x*)=0, u0, ui (所有 i ) ，且 (u0, u)0.i=1i=m2022/7/2721最優(yōu)化理論227. 最優(yōu)性條件-不等式約束6證明. 由Th7.2.2, 不存在向量 d 同時(shí)滿足 f(x*)d0 和 gi(x*)

12、d0 ，( iI). 設(shè) A 是其行由 f(x*) 和 gi(x*)(iI)組成的矩陣. 則 Ad0,可以對(duì)約束強(qiáng)加某種限制，這種限制條件叫做約束規(guī)格或約束品性( constraint qualifications).已有很多的約束規(guī)格，特別的, Karush 1939, MS Thesis, Dept of Math, Univ of Chicago , Kuhn 和 Tucker 1951 獨(dú)立給出的最優(yōu)性必要條件恰是 Fritz John 條件加上 u00.2022/7/2727最優(yōu)化理論7. 最優(yōu)性條件-不等式約束12Th7.2.4. (Karush-Kuhn-Tucker 必要條件)

13、考慮極小化問題 min f(x) subject to gi(x)0， i=1, m ，xS, 其中 S 是 En.中非空開集. 設(shè) x* 為可行點(diǎn), I= i| gi(x*)=0. 進(jìn)一步假設(shè) f(x) 和 gi(x)( iI )在 x* 可微, gi ( iI) 在 x*連續(xù). gi for iI 線性獨(dú)立.若 x* 是局部最優(yōu)解.則存在一組非負(fù)數(shù)ui( iI )使得 f(x*) uigi(x*)=0, ui 0 ( iI ).iI若還有 gi ( iI )在 x*可微, 則 f(x*) uigi(x*)=0, uigi(x*)=0, ui0 ， i=1, m.i=1i=m2022/7/2

14、728最優(yōu)化理論7. 最優(yōu)性條件-不等式約束13Karush-Kuhn-Tucker 條件可寫成向量形式f(x*)-ug(x*)=0, ug(x*)=0, u0.這表明 f(x*) 屬于起作用約束的這些約束的梯度所形成的錐中。2022/7/2729最優(yōu)化理論7. 最優(yōu)性條件-不等式約束142022/7/2730最優(yōu)化理論7. 最優(yōu)性條件-不等式約束152022/7/2731最優(yōu)化理論7. 最優(yōu)性條件-不等式約束162022/7/2732最優(yōu)化理論7. 最優(yōu)性條件-不等式約束172022/7/2733最優(yōu)化理論347. 最優(yōu)性條件-不等式約束18Th7.2.5. (Karush-Kuhn-Tuc

15、ker 充分條件)考慮極小化問題 min f(x) subject to gi(x)0， i=1, m ，xS, 其中 S 是 En.中非空開集. 設(shè) x* 為可行點(diǎn), I= i| gi(x*)=0. 設(shè)f(x)和諸 gi 是凸的， 進(jìn)一步假設(shè) f(x) 和 gi(x)( iI )在 x* 可微, gi ( iI) 在 x*連續(xù). 若 K-K-T條件在 x*成立，則x*是全局最優(yōu)解.證明略2022/7/27最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束14.一般約束問題的一階最優(yōu)性條件記2022/7/2735最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束22022/7/2736最優(yōu)化理論7. 最優(yōu)性條

16、件-等與不等式約束32022/7/2737最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束4證明略2022/7/2738最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束52022/7/2739最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束62022/7/2740最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束72022/7/2741最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束82022/7/2742最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束92022/7/2743最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束10現(xiàn)定義兩集合2022/7/2744最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束112022/7/2745最優(yōu)化理

17、論7. 最優(yōu)性條件-等與不等式約束12例:2022/7/2746最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束13例2022/7/2747最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束142022/7/2748最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束15KKT最優(yōu)性必要條件（Th2.4）加以推廣。這是通過增加約束規(guī)格來實(shí)現(xiàn)的.前面FJ條件中w0不一定為正, 在下面定理中。我們將前面提到的2022/7/2749最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束16進(jìn)一步假設(shè),gi ( iI )在 x*, 連續(xù)可微,則 f(x*)+ uigi(x*)+ vjhj(x*) =0, uigi(x*)=0, ui(i

18、=1, m.)i=1i=m若采用矩陣和向量記號(hào),則KKT可如下簡潔表示定義Lagrange函數(shù)為(7.2.48)2022/7/2750最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束17則KKT條件可表為2022/7/2751最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束182022/7/2752最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束192022/7/2753最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束205.二階條件2022/7/2754最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束21為此,我們考慮函數(shù)的二階導(dǎo)數(shù),首先給出如下定義2022/7/2755最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束22例2

19、022/7/2756最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束232022/7/2757最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束24現(xiàn)在我們考慮問題(7.2.1).2022/7/2758最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束252022/7/2759最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束262022/7/2760最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束272022/7/2761最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束282022/7/2762最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束292022/7/2763最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束302022/7/2764最優(yōu)

20、化理論7. 最優(yōu)性條件-等與不等式約束312022/7/2765最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束32為給出局部最優(yōu)解的二階充分條件，我們定義集合2022/7/2766最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束332022/7/2767最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束342022/7/2768最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束35下面分兩種情況討論2022/7/2769最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束362022/7/2770最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束372022/7/2771最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束382022/7/277

21、2最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束39例7.2.7 考慮下列非線性規(guī)劃問題檢驗(yàn)以下各點(diǎn)是否為局部最優(yōu)解2022/7/2773最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束40記目標(biāo)函數(shù)和約束函數(shù)分別為f(x),g(x),h(x),他們?cè)邳c(diǎn)x處的梯度分別是Lagrange函數(shù)是Lagrange函數(shù)關(guān)于x的Hessian矩陣是2022/7/2774最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束412022/7/2775最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束422022/7/2776最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束43后兩點(diǎn)請(qǐng)自行驗(yàn)證之2022/7/2777最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束44例7.2.8 考慮下列非線性規(guī)劃問題記目標(biāo)函數(shù)和約束函數(shù)分別為f(x), h(x),他們?cè)邳c(diǎn)x處的梯度分別是2022/7/2778最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束45例2022/7/2779最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束462022/7/2780最優(yōu)化理論7. 最優(yōu)性條件-等與不等式約束472022/7/2781最優(yōu)化理論Ch7.3 對(duì)偶理論17.3.1 對(duì)偶形式2022/7/2782最優(yōu)化理論Ch7.3 對(duì)偶理論2其對(duì)偶形式(對(duì)偶問題)定義如下2022/7/2783最優(yōu)化理論Ch