北邮最优化课件-7-最优性条件.ppt

最优化理论与算法帅天平北京邮电大学数学系7，最优性条件2024/5/25 周六1最优化理论第七章 最优性条件无约束问题的极值条件约束极值问题的最优性条件对偶及鞍点2024/5/25 周六2最优化理论7.17.1无约束问题的极值条件无约束问题的极值条件考虑非线性规划问题1，无约束极值问题称为无约束极值问题（UNLP）7.最优性条件-无约束12024/5/25 周六3最优化理论7.最优性条件-无约束2Th7.1.1(非极小点的充分条件)设f(x)在点x*处可微,若存在方向d(0)Rn,使得f(x*)d0,使得对任意(0,),有f(x*+d)f(x*).此时,我们称d 为f(x)在x*的一个下降方向下降方向.证明证明.由 f(x)在 x*可微,则 f(x*+d)=f(x*)+f(x*)d+|d|(x*;d),其中(x*;d)0(当 0).2，必要条件，必要条件2024/5/25 周六4最优化理论7.最优性条件-无约束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*二次可微时.则 f(x*)=0 且 Hessian 矩阵 H(x*)是半正定的2024/5/25 周六5最优化理论7.最优性条件-无约束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(x*)，(0,),此与 x*为局部极小相矛盾，故 f(x*)=0.2024/5/25 周六6最优化理论7.最优性条件-无约束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)的一个严格)局部极小点3，二阶充分条件，二阶充分条件2024/5/25 周六7最优化理论7.最优性条件-无约束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,d 是 f(x)在 x*.的下降方向。记所有这样的向量集合为2024/5/25 周六14最优化理论7.最优性条件-有约束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 中非空集合中非空集合，设设 fx)在在 x*可微。若可微。若 x*是局部极是局部极小点，则小点，则 F0(x*)D=,其中其中 F0(x*)=d|f(x*)d0,f(x*+d)0，x*+d S，(0,2)此与局部极小矛盾。此与局部极小矛盾。2024/5/25 周六16最优化理论177.最优性条件-不等式约束1为把最优性的几何条件用代数来表示，引入起作用约束的概为把最优性的几何条件用代数来表示，引入起作用约束的概念。问题的约束条件在点念。问题的约束条件在点x*S S处有两种情形处有两种情形3 不等式约束的一阶最优性条件不等式约束的一阶最优性条件1，I=i|gi(x*)=0在x*处起作用约束2，gi(x*)0.iI在x*处不起作用约束G0(x*)=d|gi(x*)d0,iI.2024/5/25 周六最优化理论187.最优性条件-不等式约束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)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.2024/5/25 周六最优化理论7.最优性条件-不等式约束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*2024/5/25 周六19最优化理论7.最优性条件-不等式约束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*2024/5/25 周六20最优化理论7.最优性条件-不等式约束5Th7.2.3.(Fritz John Condition,1948)考虑极小化问题考虑极小化问题 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*)=0,uigi(x*)=0,u0,ui(所有 i)，且(u0,u)0.i=1i=m2024/5/25 周六21最优化理论227.最优性条件-不等式约束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 of Chicago,Kuhn 和 Tucker 1951 独立给出的最优性必要条件恰是 Fritz John 条件条件加上加上 u00.2024/5/25 周六27最优化理论7.最优性条件-不等式约束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 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=m2024/5/25 周六28最优化理论7.最优性条件-不等式约束13Karush-Kuhn-Tucker 条件可写成向量形式条件可写成向量形式f(x*)-ug(x*)=0,ug(x*)=0,u0.这表明 f(x*)属于起作用约束的这些约束的梯度所形成的锥中。2024/5/25 周六29最优化理论7.最优性条件-不等式约束142024/5/25 周六30最优化理论7.最优性条件-不等式约束152024/5/25 周六31最优化理论7.最优性条件-不等式约束162024/5/25 周六32最优化理论7.最优性条件-不等式约束172024/5/25 周六33最优化理论347.最优性条件-不等式约束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 是凸的，是凸的，进一步假设进一步假设 f(x)和和 gi(x)(i I)在在 x*可可微微,gi(i I)在在 x*连续连续.若若 K-K-T条件在条件在 x*成立，则成立，则x*是全局是全局最优解最优解.证明略证明略2024/5/25 周六最优化理论7.最优性条件-等与不等式约束14.一般约束问题的一阶最优性条件记2024/5/25 周六35最优化理论7.最优性条件-等与不等式约束22024/5/25 周六36最优化理论7.最优性条件-等与不等式约束32024/5/25 周六37最优化理论7.最优性条件-等与不等式约束4证明略2024/5/25 周六38最优化理论7.最优性条件-等与不等式约束52024/5/25 周六39最优化理论7.最优性条件-等与不等式约束62024/5/25 周六40最优化理论7.最优性条件-等与不等式约束72024/5/25 周六41最优化理论7.最优性条件-等与不等式约束82024/5/25 周六42最优化理论7.最优性条件-等与不等式约束92024/5/25 周六43最优化理论7.最优性条件-等与不等式约束10现定义两集合2024/5/25 周六44最优化理论7.最优性条件-等与不等式约束112024/5/25 周六45最优化理论7.最优性条件-等与不等式约束12例:2024/5/25 周六46最优化理论7.最优性条件-等与不等式约束13例2024/5/25 周六47最优化理论7.最优性条件-等与不等式约束142024/5/25 周六48最优化理论7.最优性条件-等与不等式约束15KKT最优性必要条件（Th2.4）加以推广。这是通过增加约束规格来实现的.前面FJ条件中w0不一定为正,在下面定理中。我们将前面提到的2024/5/25 周六49最优化理论7.最优性条件-等与不等式约束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)2024/5/25 周六50最优化理论7.最优性条件-等与不等式约束17则KKT条件可表为2024/5/25 周六51最优化理论7.最优性条件-等与不等式约束182024/5/25 周六52最优化理论7.最优性条件-等与不等式约束192024/5/25 周六53最优化理论7.最优性条件-等与不等式约束205.二阶条件2024/5/25 周六54最优化理论7.最优性条件-等与不等式约束21为此,我们考虑函数的二阶导数,首先给出如下定义2024/5/25 周六55最优化理论7.最优性条件-等与不等式约束22例2024/5/25 周六56最优化理论7.最优性条件-等与不等式约束232024/5/25 周六57最优化理论7.最优性条件-等与不等式约束24现在我们考虑问题(7.2.1).2024/5/25 周六58最优化理论7.最优性条件-等与不等式约束252024/5/25 周六59最优化理论7.最优性条件-等与不等式约束262024/5/25 周六60最优化理论7.最优性条件-等与不等式约束272024/5/25 周六61最优化理论7.最优性条件-等与不等式约束282024/5/25 周六62最优化理论7.最优性条件-等与不等式约束292024/5/25 周六63最优化理论7.最优性条件-等与不等式约束302024/5/25 周六64最优化理论7.最优性条件-等与不等式约束312024/5/25 周六65最优化理论7.最优性条件-等与不等式约束32为给出局部最优解的二阶充分条件，我们定义集合2024/5/25 周六66最优化理论7.最优性条件-等与不等式约束332024/5/25 周六67最优化理论7.最优性条件-等与不等式约束342024/5/25 周六68最优化理论7.最优性条件-等与不等式约束35下面分两种情况讨论2024/5/25 周六69最优化理论7.最优性条件-等与不等式约束362024/5/25 周六70最优化理论7.最优性条件-等与不等式约束372024/5/25 周六71最优化理论7.最优性条件-等与不等式约束382024/5/25 周六72最优化理论7.最优性条件-等与不等式约束39例7.2.7 考虑下列非线性规划问题检验以下各点是否为局部最优解2024/5/25 周六73最优化理论7.最优性条件-等与不等式约束40记目标函数和约束函数分别为f(x),g(x),h(x),他们在点x处的梯度分别是Lagrange函数是Lagrange函数关于x的Hessian矩阵是2024/5/25 周六74最优化理论7.最优性条件-等与不等式约束412024/5/25 周六75最优化理论7.最优性条件-等与不等式约束422024/5/25 周六76最优化理论7.最优性条件-等与不等式约束43后两点请自行验证之2024/5/25 周六77最优化理论7.最优性条件-等与不等式约束44例7.2.8 考虑下列非线性规划问题记目标函数和约束函数分别为f(x),h(x),他们在点x处的梯度分别是2024/5/25 周六78最优化理论7.最优性条件-等与不等式约束45例2024/5/25 周六79最优化理论7.最优性条件-等与不等式约束462024/5/25 周六80最优化理论7.最优性条件-等与不等式约束472024/5/25 周六81最优化理论Ch7.3 对偶理论17.3.1 对偶形式2024/5/25 周六82最优化理论Ch7.3 对偶理论2其对偶形式其对偶形式(对偶问题对偶问题)定义如下定义如下2024/5/25 周六83最优化理论Ch7.3 对偶理论3于是(LP)问题(*)的对偶形如2024/5/25 周六84最优化理论Ch7.3 对偶理论42024/5/25 周六85最优化理论Ch7.3 Ch7.3 对偶理论对偶理论5 57.3.2 对偶定理对偶定理对于上面的两例我们有原问题与对偶问题的最优值相等.对一般形式的非线性规划问题,是否也对?即1.1.弱对偶定理弱对偶定理2024/5/25 周六86最优化理论Ch7.3 对偶理论62024/5/25 周六87最优化理论Ch7.3 对偶理论72.2.凸规划与凸规划与SlaterSlater约束规格约束规格2024/5/25 周六88最优化理论Ch7.3 对偶理论82024/5/25 周六89最优化理论Ch7.3 对偶理论93.强对偶定理强对偶定理2024/5/25 周六90最优化理论Ch7.3 对偶理论10证明:先证第一部分:(1)无解=(2)有解.令集合2024/5/25 周六91最优化理论Ch7.3 对偶理论112024/5/25 周六92最优化理论Ch7.3 对偶理论122024/5/25 周六93最优化理论Ch7.3 对偶理论132024/5/25 周六94最优化理论Ch7.3 对偶理论14例 考虑如下约束优化问题显然该问题无最优解,但目标函数的下确界fmin=0.该问题的Lagrange对偶函数2024/5/25 周六95最优化理论Ch7.3 对偶理论157.3.3 鞍点定理鞍点定理2024/5/25 周六96最优化理论Ch7.3 对偶理论16o1 鞍点与最优解2024/5/25 周六97最优化理论Ch7.3 对偶理论172024/5/25 周六98最优化理论Ch7.3 对偶理论18对于(2),在假设条件成立时,根据强对偶定理5.11,对于问题(PNLP)的最优解 ,存在 ,使得2024/5/25 周六99最优化理论Ch7.3 对偶理论192.鞍点与鞍点与KKT点点2024/5/25 周六100最优化理论