为了正常的体验网站,请在浏览器设置里面开启Javascript功能!
首页 > 非光滑最优化讲义-2

非光滑最优化讲义-2

2012-01-18 7页 pdf 128KB 54阅读

用户头像

is_777549

暂无简介

举报
非光滑最优化讲义-2 第二章 凸函数 §1 凸函数及其连续性 定义 1.1 设 定义在非空凸集f nR⊂Ω 上,如果对任意 Ω∈yx, 和 ]1,0[∈α ,有 ),()()1())1(( yfxfyxf αααα +−≤+− 则称 是 上的凸函数;如果对任意f Ω Ω∈yx, 和 )1,0(∈α ,当 yx ≠ 时,有 ),()()1())1(( yfxfyxf αααα +−c ,)1()()()1())1(( 2yxcyfxfyxf −−−+−≤+− αααααα 则称 是 上的强凸函数,称c是 的强凸常数. ...
非光滑最优化讲义-2
第二章 凸函数 §1 凸函数及其连续性 定义 1.1 设 定义在非空凸集f nR⊂Ω 上,如果对任意 Ω∈yx, 和 ]1,0[∈α ,有 ),()()1())1(( yfxfyxf αααα +−≤+− 则称 是 上的凸函数;如果对任意f Ω Ω∈yx, 和 )1,0(∈α ,当 yx ≠ 时,有 ),()()1())1(( yfxfyxf αααα +−<+− 则称 是 上的严格凸函数;如果存在常数 ,使得 f Ω 0>c ,)1()()()1())1(( 2yxcyfxfyxf −−−+−≤+− αααααα 则称 是 上的强凸函数,称c是 的强凸常数. f Ω f 如果 是 上的凸函数(严格凸函数,强凸函数),则称 是f− Ω f Ω上的凹函数(严格 凹函数,强凹函数). 基本性质: (1)强凸⇒严格凸⇒凸; (2)如果 是f Ω上的凸函数,则对任意 Ω∈ix 和 0≥iα , ri ,,2,1 "= , , 有 ∑ = = r i i 1 1α ∑∑ == ≤ r i ii r i ii xfxf 11 )()( αα ; (3)如果 是if Ω上的凸函数, rii ,,2,1,0 "=≥α ,则 也是 上的凸函数; ∑ = r i ii f 1 α Ω (4) 是 上的凸函数的充分必要条件是 的上图 f Ω f )}(,|),{( xfxxfepi ≥Ω∈= ββ 为 Ω×R 中的凸集。 定理 1.1 设 是非空凸集Ω上的凸函数,如果存在f Ω∈21, xx 和数 ]1,0[∉α ,使得 ,)1( 21 Ω∈−+= xxx αα 则 ).()1()()( 21 xfxfxf αα −+≥ 定理 1.2 设 是非空凸集Ω上的严格凸函数(强凸常数为 的强凸函数),如果存在 和数 f c Ω∈21, xx ]1,0[∉α ,使得 Ω∈−+= 21 )1( xxx αα ,则 )()1()()( 21 xfxfxf αα −+> ( 22121 )1()()1()()( xxcxfxfxf −−−−+≥ αααα )。 定理 1.3 设 是非空凸集 上的凸函数,则 在f Ω f Ωint 上连续。 定义 1.2 设函数 在 的某邻域内有定义, ,如果极限 f 0x nRg ∈ α α α )()( lim);( 00 0 0 xfgxfgxf −+=′ +→ 存在,则称 是 在 沿方向);( 0 gxf ′ f 0x g 的方向导数;如果对任意 ,方向导数 都存在,则称 在 方向可微。 nRg ∈ );( 0 gxf ′ f 0x 注 (1)若 );( 0 gxf ′ 存在,则 )();()()( 000 ααα ogxfxfgxf +′+=+ ; (2)若 在 方向可微,则对任意f 0x 0≥β ,有 );();( 00 gxfgxf ′=′ ββ ; (3)若 在 可微,则 在 方向可微,且f 0x f 0x )),(();( 00 gxfgxf ′=′ ,其中 T nx xf x xf x xfxf ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ∂ ∂ ∂ ∂ ∂ ∂=′ )(,,)(,)()( 0 2 0 1 0 0 " 是 在 处的梯度。 f 0x 定理 1.4 设 是非空凸集 上的凸函数,f Ω Ω∈ int0x ,则 在 方向可微。 f 0x 推论 1.1 设 是非空凸集 上的凸函数,f Ω Ω∈ int0x ,则 (1) α αα )()()( 00 xfgxfh −+= 在某区间 ],0( δ 上单调增加; (2) .)()(inf);( 00 00 α α α xfgxfgxf −+=′ > 定理 1.5 设 nR⊂Ω 是非空凸集, ,函数mRG ⊂ RG→×Ω:ϕ 满足如下条件: (1)对任意 Gy∈ , ),( yxϕ 是Ω上的凸函数; (2) +∞< ∈ ),(sup yx Gy ϕ , 则上确界函数 ),(sup)( yxxf Gy ϕ ∈ = 是Ω上的凸函数。 定理 1.6 设 nR⊂Ω 和 是非空凸集,函数mRG ⊂ RG→×Ω:ϕ 是凸函数,如果 ,),(inf −∞> ∈ yx Gy ϕ 则下确界函数 ),(inf)( yxxf Gy ϕ ∈ = 是Ω上的凸函数。 推论 1.2 设 是非空凸集,则 nRG ⊂ n Gy Rxxyxf ∈∀−= ∈ ,inf)( 是 nR 上的凸函数。 §2 凸函数的次微分 定义 2.1 设 nR⊂Ω 是非空开凸集, 是f Ω上的凸函数, Ω∈x ,称集合 }),,()()(|{)( Ω∈∀−≥−∈=∂ yxyvxfyfRvxf n 是 在f x的次微分。 以下始终假设 nR⊂Ω 是非空开凸集, 是f Ω上的凸函数。 定理 2.1 设 Ω∈0x ,则 是非空紧凸集。 )( 0xf∂ 定义 2.2 设 nRA ⊂ , 0>δ ,记 },inf|{)( δδ ≤−∈= ∈ xyRxAS Ayn 则称 是集合)(ASδ A的δ 邻域。 推论 2.1 设 是Ω上的凸函数,则f f∂ 在Ω的任何有界闭子集上有界。 定理 2.2 设 是 上的凸函数,则f Ω f∂ 在Ω的每一点都上半连续。 推论 2.2 设 是Ω上的凸函数,f Ω∈0x ,则对任意 0>ε ,存在 0>δ ,使得 .)()),(()( 00 Ω⊂∈∀∂⊂∂ xSxxfSxf δε 定理 2.3 设 是Ω上的凸函数,f Ω∈0x ,则 .),,(max))(|();( )(00 0 n xfv Rggvxfggxf ∈∀=∂=′ ∂∈ σ 推论 2.3 在定理 2.3 的条件下,如果 在 可微,则f 0x )}({)( 00 xfxf ′=∂ 。 定义 2.3 设ϕ 定义在 nR 上,如果对任意 和nRyx ∈, 0≥λ ,有 ),()(),()()( xxyxyx λϕλϕϕϕϕ =+≤+ 则称ϕ 是次线性函数。 定理 2.4 设 ,则RRn →:ϕ ϕ 是次线性函数的充分必要条件是存在非空紧凸集 nRA ⊂ ,使得 .),|()( nRgAgg ∈∀= σϕ 推论 2.4 设ϕ 是次线性函数,则 ))0(|()( ϕσϕ ∂= gg 。 推论 2.5 设 是Ω上的凸函数,f Ω∈0x ,则 );()( 0 gxfg ′=ϕ 是次线性函数;如果 0);( 0 <−=′ αgxf ,则 0);( 0 >≥−′ αgxf 。 推论 2.6 设 是 上的凸函数,则对任意f Ω Ω∈yx, ,有 ).;()()();( xyyfxfyfxyxf −′≤−≤−′ 定理 2.5 设 是 上的凸函数,f Ω Ω∈0x ,则 在 取极小值的充分必要条件是 。 f 0x )(0 0xf∂∈ 定义 2.4 设 是Ω上的凸函数,f Ω∈0x ,如果存在单位向量 ,使得 nRg ∈0 ),;(min);( 0100 gxfgxf g ′=′ = 则称 是 在 处的最速下降方向。 0g f 0x 定理 2.6 设 是Ω上的凸函数,f Ω∈0x ,如果 )(0 0xf∂∉ ,记 ,min )(0 0 vv xfv ∂∈= 则 0 0 0 v vg −= 是 在 处的唯一最速下降方向。 f 0x §3 次微分的运算法则 假设 nR⊂Ω 是非空开凸集。 定理 3.1 设 和 都是Ω上的凸函数,则1f 2f 21 fff += 也是Ω上的凸函数,且 .),()()( 21 Ω∈∀∂+∂=∂ xxfxfxf 定理 3.2 设 是 上的凸函数,1f Ω 0≥α ,则 1ff α= 也是Ω上的凸函数,且 .),()( 1 Ω∈∀∂=∂ xxfxf α 推论 3.1 设 和 都是Ω上的凸函数,1f 2f 0, 21 ≥αα ,则 2211 fff αα += 也是Ω上 的凸函数,且 .),()()( 2211 Ω∈∀∂+∂=∂ xxfxfxf αα 定理 3.3 设 都是),,2,1( mifi "= Ω上的凸函数,而 ,),(max)( 1 Ω∈∀= ≤≤ xxfxf imi 则 也是 上的凸函数,且 f Ω ,),)(()( )( Ω∈∀∂=∂ ∈ xxfcoxf xRi i∪ 其中 }1),()(|{)( mixfxfixR i ≤≤== 。 例 3.1 设 xxfRx =∈ )(, ,求 )(xf∂ 。 例 3.2 设 )()(, in xxfRx =∈ ,其中 表示)(ix x的第 个分量,求 。 i )(xf∂ 例 3.3 设 )( 1 max)(, i ni n xxfRx ≤≤ =∈ ,求 )0(f∂ 。 §4 Leibniz 公式及其应用 定义 4.1 设函数 定义在集合f nR⊂Ω 上, Ω∈x ,如果存在 x的δ 邻域 和常 数 ,使得 )(xSδ 0>K ,)(,,)()( 212121 Ω∈∀−≤− ∩xSxxxxKxfxf δ 则称 在f x为 Lipschitz 连续的(也称 在f x为 K-Lipschitz 连续的);如果对任意 , 在 Ω∈x f x为 Lipschitz 连续的,则称 是f Ω上的 Lipschitz 函数。 定理 4.1 设 是非空开凸集f nR⊂Ω 上的凸函数,则 是f Ω上的 Lipschitz 函数。 引理 4.1 设向量函数 满足条件 nRRh →: ,0 )( lim 0 =+→ α α α h 如果 在 方向可微且 Lipschitz 连续,则对任意 ,有 f 0x nRg ∈ ).;( )())(( lim 0 00 0 gxfxfhgxf ′=−+++→ α αα α 引理 4.2 设ψ 是 上的 Lipschitz 函数,则存在定义于 上的可积函数],0[ T ],0[ T ϕ ,使 得 ].,0[),()(,)()0()( a.e 0 Ttttdsst t ∈∀=′+= ∫ ϕψϕψψ 定理 4.2(Leibniz 公式) 设 是非空开凸集f nR⊂Ω 上的凸函数, 是定义在 上的n维向量函数,且满足如下条件: )(tx ],0[ T (1)对任意 ],0[ Tt∈ ,有 Ω∈)(tx ; (2)存在常数 ,使得 0>L ];,0[,,)()( 212121 TttttLtxtx ∈∀−≤− (3) 在 上可微,即 )(tx ],0[ T ),()()()( tottxtxttx Δ+Δ′+=Δ+ 则 ],,0[,))();(())0(())(( 0 Ttdssxsxfxftxf t ∈∀′′+= ∫ 且在 上几乎处处有 ],0[ T )).();(())(( txtxf dt txdf ′′= 推论 4.1 设 是非空开凸集f nR⊂Ω 上的凸函数,则对任意 Ω∈xx ,0 ,有 .));(()()( 1 0 0000 ∫ −−+′+= dtxxxxtxfxfxf 以下给出 Lipschitz 公式的应用。 定理 4.3 设 和 都是非空开凸集1f 2f nR⊂Ω 上的凸函数,如果 ,),()( 21 Ω∈∀∂=∂ xxfxf 则 常数。 ≡− 21 ff 定理 4.4 设 是非空开凸集f nR⊂Ω 上的凸函数, Ω∈0x ,则 ).();()()( 000 gogxfxfgxf +′+=+ 此时,称 在 一致方向可微。 f 0x 定理 4.5 设 是非空开凸集f nR⊂Ω 上的凸函数,则 (1) 在 上严格凸的充分必要条件是对任意f Ω Ω∈x 和 )(xfv ∂∈ ,有 ;:),,()()( xyyxyvxfyf ≠Ω∈∀−+> (4.1) (2) 在Ω上强凸(强凸常数为 )的充分必要条件是对任意f c Ω∈x 和 , 有 )(xfv ∂∈ .,),()()( 2 Ω∈∀−+−+≥ yxycxyvxfyf 定义 4.2 设 nR⊂Ω 是非空开凸集, 是集值映射, )(: nRF Π→Ω (1)如果对任意 )(),(,, yFvxFuyx ∈∈Ω∈ ,有 ,0),( ≥−− yxvu 则称 在Ω上单调; F (2)如果对任意 )(),(,,, yFvxFuyxyx ∈∈≠Ω∈ ,有 ,0),( >−− yxvu 则称 在Ω上严格单调; F (3)如果存在常数 ,使得对任意0>c )(),(,, yFvxFuyx ∈∈Ω∈ ,有 ,),( 2yxcyxvu −≥−− 则称 在Ω上强单调, 称为强单调常数。 F c 定理 4.6 设 是非空凸集 上的凸函数,则 f Ω (1) 在 上单调; f∂ Ω (2) 在 上严格凸 在f Ω ⇔ f∂ Ω上严格单调; (3) 在 上强凸⇔ 在f Ω f∂ Ω上强单调。
/
本文档为【非光滑最优化讲义-2】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索