北邮最优化课件7_最优性条件.pptx

《北邮最优化课件7_最优性条件.pptx》由会员分享，可在线阅读，更多相关《北邮最优化课件7_最优性条件.pptx（100页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2023/5/17最优化理论1最优化理论与算法帅天平北京邮电大学数学系7，最优性条件2023/5/17最优化理论2第七章 最优性条件无约束问题的极值条件约束极值问题的最优性条件对偶及鞍点2023/5/17最优化理论37.17.1无约束问题的极值条件无约束问题的极值条件考虑非线性规划问题1，无约束极值问题称为无约束极值问题（UNLP）7.最优性条件-无约束12023/5/17最优化理论47.最优性条件-无约束2Th7.1.1(非极小点的充分条件)设f(x)在点x*处可微,若存在方向d(0)Rn,使得f(x*)d0,使得对任意(0,),有f(x*+d)f(x*).此时,我们称d 为f(x)在x*的

2、一个下降方向下降方向.证明证明.由 f(x)在 x*可微,则 f(x*+d)=f(x*)+f(x*)d+|d|(x*;d),其中(x*;d)0(当 0).2，必要条件，必要条件2023/5/17最优化理论57.最优性条件-无约束3移项且两边同除以移项且两边同除以(0),得（f(x*+d)f(x*)）/f(x*)d+|d|(x*;d)由于 f(x*)d 0 使得对 任意(0,),f(x*)d+|d|(x*;d)0.定理立明.定理定理7.1.2-3(极小点的必要条件)设x*处是问题(UNLP)的局部极小点.(1)当 f(x)在 x*可微时,则梯度 f(x*)=0.(2)当f(x)在 x*二次可微时

3、.则 f(x*)=0 且 Hessian 矩阵 H(x*)是半正定的2023/5/17最优化理论67.最优性条件-无约束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.移项整理并两端除以 ,得 =dH(x*)d/2+|d|(x*;d)(II).因 x*局部极小,对充分小 有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(

4、x*)，(0,),此与 x*为局部极小相矛盾，故 f(x*)=0.2023/5/17最优化理论77.最优性条件-无约束5dH(x*)d/2+|d|(x*;d)0 2由(II),显见对充分小的 成立,对 0取极限,则有 dH(x*)d 0,从而,H(x*)半正定定义定义1 若f(x)在点x*处可微,且f(x*)=0,则称x*为f(x)的一个驻点驻点或平稳点平稳点.d(0)Rn,既不是极大点也不是极小点的驻点称为鞍点鞍点.Th7.1.4(二阶充分条件二阶充分条件).假设 f(x)在 x*点二次可微,若 f(x*)=0 且 Hessian 矩阵 H(x*)是正定的,则 x*是(UNLP)的一个(严格

5、)局部极小点3，二阶充分条件，二阶充分条件2023/5/17最优化理论87.最优性条件-无约束6证明证明.因 f 在 x*二次可微,故对任意 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,当 xx*.假设命题不真，x*不是局部极小,则存在序列 xk 收敛到 x*并使得 f(xk)0 使得 f(x*+d)f(x*)（(0,)）,则 d 称为 f(x)在 x*的下降方向(decedent direction)设 f(x)在 x*可微.若存在向量 d 满足 f(x*)d0,则 由Th7.1.1,

6、d 是 f(x)在 x*.的下降方向。记所有这样的向量集合为2023/5/17最优化理论157.最优性条件-有约束3由可行方向定义和下降方向知，可行方向定义和下降方向知，从点 x*,沿可行方向 dD(x*)作一个很小的移动还是可行点.进一步，由 Th 7.1.1,若 f(x*)d0，则d 是f在 x*的下降方向。下面定理将说明 若 x*是局部最优且 f(x*)d0,则 dD(x*).即不是可行方向。Theorem 7.2.1.(必要条件必要条件)考虑极小化问题考虑极小化问题：min f(x)，subject to xS,其中其中 S 是是 Rn 中非空集合中非空集合，设设 f(x)在在 x*可

7、微。若可微。若 x*是局部极是局部极小点，则小点，则 F0(x*)D=,其中其中 F0(x*)=d|f(x*)d0,f(x*+d)0，x*+d S，(0,2)此与局部极小矛盾。此与局部极小矛盾。2023/5/17最优化理论17177.最优性条件-不等式约束1为把最优性的几何条件用代数来表示，引入起作用约束的概为把最优性的几何条件用代数来表示，引入起作用约束的概念。问题的约束条件在点念。问题的约束条件在点x*S S处有两种情形处有两种情形3 不等式约束的一阶最优性条件不等式约束的一阶最优性条件1，I=i|gi(x*)=0在x*处起作用约束2，gi(x*)0.iI在x*处不起作用约束G0(x*)=

8、d|gi(x*)d0,iI.2023/5/17最优化理论18187.最优性条件-不等式约束2证明概要证明概要.设设 d G0(x*).因因 S 为开集，则存在为开集，则存在 10 使得对使得对 (0,1)，x*+d S。另外存在另外存在 20使得使得对对 (0,2)，i I.gi(x*+d)0,最后存在最后存在 30 使得使得对任意对任意 (0,3)and i I有有gi(x*+d)gi(x*),从而从而 d D,D 是是 x*处的可行方向锥处的可行方向锥.于是于是G(x*)D.由由Th 7.2.1,立明。立明。Th7.2.2.(必要条件必要条件)考虑极小化问题考虑极小化问题 min f(x)

9、subject to gi(x)0，i=1,m，x S,其中其中 S 是是 Rn中的非空开集。中的非空开集。设设 x*为可行点，为可行点，I=i|gi(x*)=0.进一步假设，进一步假设，f(x)和和 gi(x)（i I）在）在 x*可微，可微，gi（i I）在在 x*连续连续.若若 x*是局部最优解，则是局部最优解，则 F0(x*)G0(x*)=,其中其中F0(x*)=d|f(x*)d0，i I.2023/5/17最优化理论197.最优性条件-不等式约束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 2Mi

10、n (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*2023/5/17最优化理论207.最优性条件-不等式约束4Min (x-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*是最优解g2(x*)(2,1)x*2023/5/17最优化理论217.最优性条件-不等式约束5Th7.2.3.(Fritz John Condition,1

11、948)考虑极小化问题考虑极小化问题 min f(x)subject to gi(x)0，i=1,m，x S,其中其中 S 是是 En.中非空开集中非空开集.设设 x*为可行点为可行点,I=i|gi(x*)=0.进一进一步假设步假设 f(x)和和 gi(x)(i I)在在 x*可微可微,gi(i I)在在 x*连续连续.若若 x*是局部最优解是局部最优解.则则存在一组非负数存在一组非负数 u0,ui(iI)使得使得 u0f(x*)-uigi(x*)=0,u0,ui0 for iI and(u0,uI)0.iI进一步进一步,若若 gi(x)(iI)在 x*也可微，则 u0f(x*)uigi(x*

12、)=0,uigi(x*)=0,u0,ui(所有 i)，且(u0,u)0.i=1i=m2023/5/17最优化理论22227.最优性条件-不等式约束6证明证明.由由Th7.2.2,不存在向量不存在向量 d 同时满足同时满足 f(x*)d0 和和 gi(x*)d0，(i I).设设 A 是其行由是其行由 f(x*)和和 gi(x*)(i I)组成的矩阵组成的矩阵.则则 Ad0,可以对约束强加某种限制，这种限制条件叫做约束规格或约束品性(constraint qualifications).已有很多的约束规格，特别的,Karush 1939,MS Thesis,Dept of Math,Univ o

13、f Chicago,Kuhn 和 Tucker 1951 独立给出的最优性必要条件恰是 Fritz John 条件条件加上加上 u00.2023/5/17最优化理论287.最优性条件-不等式约束12Th7.2.4.(Karush-Kuhn-Tucker 必要条件必要条件)考虑极小化问题考虑极小化问题 min f(x)subject to gi(x)0，i=1,m，x S,其中其中 S 是是 En.中非空开集中非空开集.设设 x*为可行点为可行点,I=i|gi(x*)=0.进一进一步假设步假设 f(x)和和 gi(x)(i I)在在 x*可微可微,gi(i I)在在 x*连续连续.gi for

14、iI 线性独立线性独立.若若 x*是局部最优解是局部最优解.则则存在一组非负数存在一组非负数ui(iI)使得使得 f(x*)uigi(x*)=0,ui 0(iI).iI若还有若还有 gi(i I)在在 x*可微可微,则则 f(x*)uigi(x*)=0,uigi(x*)=0,ui0，i=1,m.i=1i=m2023/5/17最优化理论297.最优性条件-不等式约束13Karush-Kuhn-Tucker 条件可写成向量形式条件可写成向量形式f(x*)-ug(x*)=0,ug(x*)=0,u0.这表明 f(x*)属于起作用约束的这些约束的梯度所形成的锥中。2023/5/17最优化理论307.最优

15、性条件-不等式约束142023/5/17最优化理论317.最优性条件-不等式约束152023/5/17最优化理论327.最优性条件-不等式约束162023/5/17最优化理论337.最优性条件-不等式约束172023/5/17最优化理论34347.最优性条件-不等式约束18Th7.2.5.(Karush-Kuhn-Tucker 充分条件充分条件)考虑极小化问题考虑极小化问题 min f(x)subject to gi(x)0，i=1,m，x S,其中其中 S 是是 En.中非空开集中非空开集.设设 x*为可行点为可行点,I=i|gi(x*)=0.设设f(x)和诸和诸 gi 是凸的，是凸的，进一

16、步假设进一步假设 f(x)和和 gi(x)(i I)在在 x*可可微微,gi(i I)在在 x*连续连续.若若 K-K-T条件在条件在 x*成立，则成立，则x*是全局是全局最优解最优解.证明略证明略2023/5/17最优化理论357.最优性条件-等与不等式约束14.一般约束问题的一阶最优性条件记2023/5/17最优化理论367.最优性条件-等与不等式约束22023/5/17最优化理论377.最优性条件-等与不等式约束32023/5/17最优化理论387.最优性条件-等与不等式约束4证明略2023/5/17最优化理论397.最优性条件-等与不等式约束52023/5/17最优化理论407.最优性

17、条件-等与不等式约束62023/5/17最优化理论417.最优性条件-等与不等式约束72023/5/17最优化理论427.最优性条件-等与不等式约束82023/5/17最优化理论437.最优性条件-等与不等式约束92023/5/17最优化理论447.最优性条件-等与不等式约束10现定义两集合2023/5/17最优化理论457.最优性条件-等与不等式约束112023/5/17最优化理论467.最优性条件-等与不等式约束12例:2023/5/17最优化理论477.最优性条件-等与不等式约束13例2023/5/17最优化理论487.最优性条件-等与不等式约束142023/5/17最优化理论497.最

18、优性条件-等与不等式约束15KKT最优性必要条件（Th2.4）加以推广。这是通过增加约束规格来实现的.前面FJ条件中w0不一定为正,在下面定理中。我们将前面提到的2023/5/17最优化理论507.最优性条件-等与不等式约束16进一步假设,gi(iI)在 x*,连续可微,则 f(x*)+uigi(x*)+vjhj(x*)=0,uigi(x*)=0,ui(i=1,m.)i=1i=mo若采用矩阵和向量记号,则KKT可如下简洁表示定义定义Lagrange函数为函数为(7.2.48)2023/5/17最优化理论517.最优性条件-等与不等式约束17则KKT条件可表为2023/5/17最优化理论527.

19、最优性条件-等与不等式约束182023/5/17最优化理论537.最优性条件-等与不等式约束192023/5/17最优化理论547.最优性条件-等与不等式约束205.二阶条件2023/5/17最优化理论557.最优性条件-等与不等式约束21为此,我们考虑函数的二阶导数,首先给出如下定义2023/5/17最优化理论567.最优性条件-等与不等式约束22例2023/5/17最优化理论577.最优性条件-等与不等式约束232023/5/17最优化理论587.最优性条件-等与不等式约束24现在我们考虑问题(7.2.1).2023/5/17最优化理论597.最优性条件-等与不等式约束252023/5/1

20、7最优化理论607.最优性条件-等与不等式约束262023/5/17最优化理论617.最优性条件-等与不等式约束272023/5/17最优化理论627.最优性条件-等与不等式约束282023/5/17最优化理论637.最优性条件-等与不等式约束292023/5/17最优化理论647.最优性条件-等与不等式约束302023/5/17最优化理论657.最优性条件-等与不等式约束312023/5/17最优化理论667.最优性条件-等与不等式约束32为给出局部最优解的二阶充分条件，我们定义集合2023/5/17最优化理论677.最优性条件-等与不等式约束332023/5/17最优化理论687.最优性条

21、件-等与不等式约束342023/5/17最优化理论697.最优性条件-等与不等式约束35下面分两种情况讨论2023/5/17最优化理论707.最优性条件-等与不等式约束362023/5/17最优化理论717.最优性条件-等与不等式约束372023/5/17最优化理论727.最优性条件-等与不等式约束382023/5/17最优化理论737.最优性条件-等与不等式约束39例7.2.7 考虑下列非线性规划问题检验以下各点是否为局部最优解2023/5/17最优化理论747.最优性条件-等与不等式约束40记目标函数和约束函数分别为f(x),g(x),h(x),他们在点x处的梯度分别是Lagrange函数

22、是Lagrange函数关于x的Hessian矩阵是2023/5/17最优化理论757.最优性条件-等与不等式约束412023/5/17最优化理论767.最优性条件-等与不等式约束422023/5/17最优化理论777.最优性条件-等与不等式约束43后两点请自行验证之2023/5/17最优化理论787.最优性条件-等与不等式约束44例7.2.8 考虑下列非线性规划问题记目标函数和约束函数分别为f(x),h(x),他们在点x处的梯度分别是2023/5/17最优化理论797.最优性条件-等与不等式约束45例2023/5/17最优化理论807.最优性条件-等与不等式约束462023/5/17最优化理论

23、817.最优性条件-等与不等式约束472023/5/17最优化理论82Ch7.3 对偶理论17.3.1 对偶形式2023/5/17最优化理论83Ch7.3 对偶理论2其对偶形式其对偶形式(对偶问题对偶问题)定义如下定义如下2023/5/17最优化理论84Ch7.3 对偶理论3于是(LP)问题(*)的对偶形如2023/5/17最优化理论85Ch7.3 对偶理论42023/5/17最优化理论86Ch7.3 Ch7.3 对偶理论对偶理论5 57.3.2 对偶定理对偶定理对于上面的两例我们有原问题与对偶问题的最优值相等.对一般形式的非线性规划问题,是否也对?即1.1.弱对偶定理弱对偶定理2023/5/

24、17最优化理论87Ch7.3 对偶理论62023/5/17最优化理论88Ch7.3 对偶理论72.2.凸规划与凸规划与SlaterSlater约束规格约束规格2023/5/17最优化理论89Ch7.3 对偶理论82023/5/17最优化理论90Ch7.3 对偶理论93.强对偶定理强对偶定理2023/5/17最优化理论91Ch7.3 对偶理论10证明:先证第一部分:(1)无解=(2)有解.令集合2023/5/17最优化理论92Ch7.3 对偶理论112023/5/17最优化理论93Ch7.3 对偶理论122023/5/17最优化理论94Ch7.3 对偶理论132023/5/17最优化理论95Ch7.3 对偶理论14例 考虑如下约束优化问题显然该问题无最优解,但目标函数的下确界fmin=0.该问题的Lagrange对偶函数2023/5/17最优化理论96Ch7.3 对偶理论157.3.3 鞍点定理鞍点定理2023/5/17最优化理论97Ch7.3 对偶理论16o1 鞍点与最优解2023/5/17最优化理论98Ch7.3 对偶理论172023/5/17最优化理论99Ch7.3 对偶理论18对于(2),在假设条件成立时,根据强对偶定理5.11,对于问题(PNLP)的最优解 ,存在 ,使得2023/5/17最优化理论100Ch7.3 对偶理论192.鞍点与鞍点与KKT点点