1、認(rèn)知無(wú)線網(wǎng)絡(luò)行為分析與網(wǎng)絡(luò)效能研究973 項(xiàng)目；認(rèn)知無(wú)線網(wǎng)絡(luò)的全局性能優(yōu)化；迭代收斂的全局最優(yōu)性調(diào)研；簡(jiǎn)介本文檔主要分兩大部分：第一部分， 2,3 節(jié)主要是問(wèn)題是否存在全局最優(yōu)解，以及局部最優(yōu)解為全局最優(yōu)解的條件，涉及到凸優(yōu)化和對(duì)偶分解的基本理論。第二部分，迭代算法能收斂到最優(yōu)的條件?；靖拍钆c定理2.1全局最優(yōu)與局部最優(yōu)min f ( x)x S（ 1）S gi (x)0, i 1,2,., m; hj (x) 0, j 1,2,., p; xX 其中，X為n的一個(gè)緊子集1【1】。定義 1.1.1 （全局最優(yōu)解）如果存在一個(gè)點(diǎn)x*S ，使得 f ( x* ) f (x), xS 成立，則稱(chēng)

2、x* 為問(wèn)題（ 1）的全局最優(yōu)解，f (x*) 為全局最優(yōu)值。定義 1.1.2（局部最優(yōu)解）如果存在xS 的鄰域 W ，使得對(duì)所有 xSW 都有不等式 f ( x )f ( x) 成立，則 x 為問(wèn)題（ 1）的局部最優(yōu)解。【 2】圖1 一維變量情形時(shí)，無(wú)約束優(yōu)化問(wèn)題的極值示例圖局部最優(yōu)條件：定 義1.1.3 （可行方向）設(shè)集合Sn,xcl S d是 非零向 量，若 存在，使得,有界閉集即為緊集。xd S,(0,) ，則稱(chēng) d 為集合S 在 x 的可行方向 。定義 1.1.4（下降方向 ） f(x) 為定義在n上的實(shí)函數(shù)， x*n ，d 為非零向量，若存在0 ，使得 f ( xd)f ( x),

3、(0,) ，則稱(chēng) d 為 f(x) 在 x 處的下降方向 。推論 1.1.1：如果f (x* )T d0，則 d 為 f(x) 在 x* 處的一個(gè)下降方向。記 D d | d 0, x*cl S,0,使得(0, ), x*d SF d | f (x* )T d 0定理1.1.3（一階必要條件 ）假設(shè) f在 x* 處可微，如果 x*是（ 1）的局部最優(yōu)解，則DF（即 x* 處的可行方向一定不是下降方向）如果 Sn ，則f (x* ) 0；如果 S 為凸集，則f ( x* )T ( xx* )0,xS 。定理 1.1.4（一階充分條件 ）f (x* )T d0, d 為 S 在 x* 處的所有非

4、0 可行方向。定義1.1.5（有效約束）|( )0,1,., ，即等號(hào)成立的不等式約束。Iigixim定理（二階必要條件）dnd Txx2 L( x* , * , * )d 0, d Ggi ( x* )T d0,iI ,d |0,iI ,gi (x* )T dhj ( x* )T d0, jii00如果 Sn ，則 x* 局部最優(yōu) =f ( x* )0,2 f (x* )0 （ Hess 矩陣半正定） 。定理（二階充分條件）d 0d Txx2 L( x* , * , * )d 0, d Gd |gi (x* )T d0, iI ,gi (x* )T d0, iI ,hj (x* )T d0,

5、 jii00如果 Sn ，則f ( x* )0,2 f (x* )0 （ Hess 矩陣正定） = x* 局部最優(yōu)。全局最優(yōu)存在條件：1） f 連續(xù)，且S 為緊集；2） S 為閉集，且f 連續(xù)，且coercive?，即 | x |時(shí) f ( x)。2.2凸優(yōu)化（凸集、凸函數(shù)的定義與性質(zhì)，此處省略）定理凸規(guī)劃的局部極小點(diǎn)就是全局極小點(diǎn)，且極小點(diǎn)的集合為凸集。如果凸規(guī)劃的目標(biāo)函數(shù)是嚴(yán)格凸函數(shù)，又存在極小點(diǎn)，則它的極小點(diǎn)是唯一的。定義 2.2.1（擬凸函數(shù)quasi-convex ）設(shè) S 是n 中的一個(gè)非空凸集，f 是定義在S 上的實(shí)函數(shù)。若對(duì)任 意 的 x(1) ,x(2)S及 每一 個(gè) 數(shù)(0

6、,1)， 有(1)( 1 x )(2 )ax x f(1)為擬(凸函數(shù))。（更直觀的定義，f ( x) fmx(，則稱(chēng)) ,f滿足 xS | f ( x), 為凸集3 ）【 】定理 2.2.2若 f ( x) 是凸集 S 上的擬凸函數(shù)， x 是 f (x) 在 S 上的嚴(yán)格局部極小點(diǎn)，則 x也是 f ( x) 在 S 上的全局極小點(diǎn)。定義 2.2.2（偽凸函數(shù) pseudo-convex）設(shè) S 是n 中的非空開(kāi)凸集， f (x) 是定義在 S 上的 可 微 實(shí) 函 數(shù) ， 如 果 對(duì) 任 意 兩 點(diǎn) x(1) ,x(2)S ， 有 (x( 1 ) x ( 2)T)f (x ( 2)0蘊(yùn) 含f

7、 (x( 1 ) f (x( 2 )，則稱(chēng) f (x) 是偽凸函數(shù) 。)定理若 f (x) 是開(kāi)凸集S 上的偽凸函數(shù)， 且對(duì)某個(gè) xS 有f ( x)0 ，則 x 是(x) 在 S 上的全局極小點(diǎn)。凸擬凸偽凸圖2 凸、擬凸、偽凸關(guān)系圖2.3對(duì)偶分解理論這里的對(duì)偶指拉格朗日對(duì)偶。對(duì)偶是約束優(yōu)化中一個(gè)很重要的概念，它為很多約束分解方案（如可分離規(guī)劃） ，以及得到空間分解算法（如分支定界）的下界，提供了理論基礎(chǔ)。【 4】2.3.1 拉格朗日對(duì)偶1）。定義 2.3.1（原始問(wèn)題）問(wèn)題（定義 2.3.2（拉格朗日函數(shù)）( ,)()()( )（ 2）L xf xi gixi hixi定義 2.3.3（對(duì)偶

8、函數(shù)）g(, )minL( x,)xX定義 2.3.4（對(duì)偶問(wèn)題）max g(,)0,定理 2.3.1對(duì)偶函數(shù)是和的凹函數(shù)， 即對(duì)偶問(wèn)題為凸問(wèn)題。如果 f ( x) 嚴(yán)格凸， 則對(duì)偶函數(shù)連續(xù)可微。假設(shè)原始問(wèn)題的最優(yōu)解為x*，最優(yōu)值為 p*，對(duì)偶問(wèn)題的最優(yōu)解為* ,*，最優(yōu)值為 d *定理 2.3.2（弱對(duì)偶） d*p*定理 2.3.3（強(qiáng)對(duì)偶） d*p*，即對(duì)偶間隙為0。定義 2.3.5（ slater 條件）原始問(wèn)題存在嚴(yán)格可行點(diǎn)。定理 2.3.3如果原問(wèn)題為凸問(wèn)題，且滿足slater 條件，則滿足強(qiáng)對(duì)偶。定義 2.3.6（ KKT 條件）假設(shè)目標(biāo)函數(shù)和約束函數(shù)均可微，且滿足強(qiáng)對(duì)偶， (x*

9、 ,*, *)為原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解對(duì)，則*處的偏導(dǎo)為0；*)*)*)01）（ 2）在 xf (xigi ( xihi (xii2）互補(bǔ)松弛： i gi ( x)0,i3）原問(wèn)題和對(duì)偶問(wèn)題的約束：gi ( x) 0,i1,., m; hi(x* )0, i1,., p;0 。定理 2.3.4對(duì)于凸問(wèn)題， KKT條件是充要條件（即2.3.6 的反向也成立） 。分解【5】分解的基本思想 ：基于目標(biāo)函數(shù)和約束的特定結(jié)構(gòu)，將問(wèn)題分解為一個(gè)主問(wèn)題和一系列更易求解的子問(wèn)題。 這些子問(wèn)題可以獨(dú)立求解，但是一般需要協(xié)調(diào)器（主問(wèn)題）來(lái)保證局部決策能收斂到全局最優(yōu)。對(duì)偶分解的基本思想是利用對(duì)偶函數(shù)的結(jié)構(gòu)來(lái)提

10、高計(jì)算效率或得到分布式算法。價(jià)格機(jī)制解釋?zhuān)簩Ⅰ詈系募s束看作公共資源， 將對(duì)偶變量看作是公共資源的價(jià)格， 對(duì)于供給方， 如果資源緊張時(shí)，提高價(jià)格，在資源充裕的時(shí)候，降低價(jià)格；對(duì)于需求方，根據(jù)當(dāng)前價(jià)格最大化自身凈效益，來(lái)請(qǐng)求資源。這樣就可以達(dá)到需求近似與供給對(duì)齊。耦合的約束的處理舉例：min1 (x1)2 ( x2 )st. x1x2xtot約束中變量是耦合的。1）引入對(duì)偶變量，將約束松弛，得到：L (x,) 1 ( x1)2 ( x2 )( x1 x2xtot )( 1 ( x1 )x1 )( 2 ( x2 )x2 )xtotq( )inf ( 1 (x1)x1 )inf ( 2 ( x2 )x

11、2 )xtot q1( )q2 ( ) xtotx1x2q1 ()q2 ( )這樣就成了一個(gè)可分離問(wèn)題。2）對(duì)于給定的，可以并行求解得到使1( x1 )x1 、 2 (x2 )x2 最小的 x1 、 x2 ，記為 x1* ( ) 、 x*2 ( ) 。3）使用影射子梯度算法，更新(t 1)(t )(t ) (xtotx1* ( )x*2 ( )4）如果滿足迭代停止條件，則終止；否則，轉(zhuǎn)入2)。耦合的目標(biāo)的處理同一決策變量包含在不同目標(biāo)函數(shù)里，或一個(gè)目標(biāo)函數(shù)包含多個(gè)決策變量。一般思路是將目標(biāo)耦合轉(zhuǎn)化為約束耦合。舉例：min1 ( x)2 ( x)引入 x1 和 x2 ，將問(wèn)題轉(zhuǎn)化為min1 (

12、x1 )2 ( x2 )st.x1x2這樣就可以利用上一節(jié)的方法求解了。對(duì)偶分解的局限即使在強(qiáng)對(duì)偶條件下，對(duì)偶問(wèn)題的一個(gè)解只能提供原問(wèn)題的最優(yōu)值，而不一定能提供原問(wèn)題的最優(yōu)解。對(duì)于非最優(yōu)的對(duì)偶變量值，x* ( ,)arginfL ( x,)不一定是原問(wèn)題的x可行解。因此，如果不能容忍這種約束違背，需要一種恢復(fù)原始可行解的方法。當(dāng)對(duì)偶函數(shù)可微時(shí)， 原始解迭代將隨對(duì)偶變量收斂到最優(yōu)而收斂到最優(yōu)； 當(dāng)對(duì)偶函數(shù)不平滑時(shí)，原始解迭代往往不收斂。2.4擴(kuò)展的對(duì)偶理論 【 6】傳統(tǒng)的對(duì)偶理論對(duì)于非凸問(wèn)題，尤其是離散或混合整數(shù)的問(wèn)題，可能會(huì)導(dǎo)致對(duì)偶間隙不為 0。其 1m -懲罰函數(shù)為L(zhǎng)m (x,)f ( x)

13、T g( x)T| h(x) |其中| h(x) |(| h1 (x) |,.,| hp ( x) |)T , g( x)( g1( x),., gm ( x)，并定義( x)max0, ( x) ，m ,p 為懲罰因子。擴(kuò)展的對(duì)偶函數(shù)為q(,)min Lm ( x, , x X) 。擴(kuò)展的對(duì)偶問(wèn)題為max q(,)s.t0,02.4.1連續(xù)優(yōu)化問(wèn)題x X ，如果不存在這樣的方向定義1.4.1（約束品性條件）對(duì)于連續(xù)優(yōu)化問(wèn)題，點(diǎn)pn 使得連續(xù)有效不等式約束和連續(xù)等式約束沿該方向的的方向?qū)?shù)均為0，則稱(chēng)滿足約束品性條件。定義 1.4.2 （可行集的-擴(kuò)展）0 為一個(gè)標(biāo)量值， S x | x X

14、, min | y x | 。y S引理 1.4.1對(duì)任意常數(shù)0 ，存在一個(gè)有限的標(biāo)量值0 ，使得| g (x) |2| h( x) |2, x XS定理 1.4.1假設(shè) x*X 是連續(xù)優(yōu)化問(wèn)題 （ 1）的全局極小解， 且 x* 滿足約束品性條件，則1）存在有限的*0,*0，使得f ( x* ) min Lm ( x, * , * ),*, *x X2）對(duì)于擴(kuò)展的對(duì)偶問(wèn)題，對(duì)偶間隙為0，即 q*f ( x* ) 。離散優(yōu)化問(wèn)題此時(shí)，對(duì)應(yīng)問(wèn)題 （ 1）中的 X為有限的離散集， 假設(shè) f 有下界， 不要求 f,g,h 連續(xù)或可微。定理 1.4.2 假設(shè) x*X 是離散優(yōu)化問(wèn)題的全局極小解，則（注意

15、：這里不需要約束品性條件）1）存在有限的*0,*0，使得f ( x* ) min Lm ( x,* ,* ),* ,*x X2）對(duì)于擴(kuò)展的對(duì)偶問(wèn)題，對(duì)偶間隙為0，即 q*f ( x* ) 。2.4.3 混合優(yōu)化問(wèn)題此時(shí)優(yōu)化變量x 可表示成 x( y, z)YZ ，其中 y 為連續(xù)變量， z 為離散變量。定理 1.4.3 假設(shè) x*YZ 是混合優(yōu)化問(wèn)題的全局極小解，則1）存在有限的*0,*0，使得f ( x* ) minLm ( x,* ,* ),* ,*x Y Z2）對(duì)于擴(kuò)展的對(duì)偶問(wèn)題，對(duì)偶間隙為0，即 q*f ( x* ) 。2.4.4 存在問(wèn)題由于懲罰函數(shù)帶有絕對(duì)值符號(hào)或影射算子，使得求導(dǎo)

16、， 以及分解更困難， 目前還沒(méi)有得到分布式的求解方法。強(qiáng)對(duì)偶的特殊情形對(duì) K 個(gè)用戶， N 個(gè)載波的 OFDM 系統(tǒng)：maxf n ( xn )n（ 2-1）s.thn ( xn )P其中， xnK , fn :K, hn :KK 。定義 3.1（時(shí)間共享）假設(shè) x* 、 y*分別為 PPx 、 PP 時(shí)問(wèn)題（ 2-1）的最優(yōu)解，如nny果對(duì)0,1 ，存在一個(gè)可行解zn ，滿足Nn 1hn ( zn )Px(1 ) Py ,，NNNf n ( zn )n 1fn ( xn* ) (1)fn ( yn* )n 1n 1則稱(chēng)問(wèn)題（ 2-1）滿足時(shí)間共享?xiàng)l件。定理 3.1如果 xn* ( )arg

17、max L( xn, ) 在* 處連續(xù)，則對(duì)偶間隙為 0【】7。xn定理 3.2將問(wèn)題（ 2-1）的最優(yōu)值看作P 的函數(shù)，如果該最優(yōu)值是 P 的凹函數(shù)，則問(wèn)題（ 2-1）滿足時(shí)間共享?xiàng)l件，對(duì)偶間隙為【 】0 8 。定理 3.1的條件是定理3.2 條件的充分非必要條件。中證明在多載波系統(tǒng)中，對(duì)于(2-1)形式的優(yōu)化問(wèn)題，當(dāng)子載波數(shù)無(wú)限大時(shí)，定理【8】3.2 的條件總是滿足。在【 9】 中，仿真表明子載波數(shù)為8，就能滿足條件。4. 總結(jié)對(duì)偶間隙為0 的情況：1） 如果原問(wèn)題為凸問(wèn)題，且滿足2） 擬凸與偽凸的性質(zhì)；slater 條件；3） 對(duì)于非凸問(wèn)題，如果原問(wèn)題滿足時(shí)間共享?xiàng)l件；數(shù)值算法收斂性前面

18、部分已經(jīng)找到了保證強(qiáng)對(duì)偶性， 即局部最優(yōu)即為全局最優(yōu)的條件， 接下來(lái)的算法只要保證能找到一個(gè)局部最優(yōu)點(diǎn)就滿足要求了，對(duì)于迭代算法，則要求收斂值是局部最優(yōu)值。由于利用最優(yōu)性條件求解一個(gè)問(wèn)題時(shí)， 一般需要解非線性方程組， 這本身就是一個(gè)困難問(wèn)題，因此求解非線性規(guī)劃一般采取數(shù)值計(jì)算方法。5.1算法收斂基本問(wèn)題（迭代下降 算法）定義（算法）算法 A 是定義在空間X 上的點(diǎn)到集的映射，即對(duì)每一個(gè)點(diǎn)xX ，給定一個(gè)子集A( x)X 。定義（解集合） 一般把滿足某些條件的點(diǎn)集定義為解集合，當(dāng)?shù)c(diǎn)屬于這個(gè)集合時(shí)，停止迭代。例如，在無(wú)約束優(yōu)化問(wèn)題中，可以定義解集合為 x |f ( x) |0 ；在約束優(yōu)化問(wèn)題

19、中，可以定義為 x | x為 KT點(diǎn) 或 x | xS, f ( x)b，其中b 為某個(gè)可接受的目標(biāo)函數(shù)值。當(dāng)然，還可以有其他定義方法。定義（下降函數(shù)） 設(shè)X 為解集合， A 為 X 上的一個(gè)算法，( x) 是定義在 X上的連續(xù)實(shí)函數(shù)，若滿足以下條件：1且y A( x)時(shí)，( y)( x)；（嚴(yán)格下降） 當(dāng) x2） 當(dāng) x且 yA( x) 時(shí)，( y)( x) ；則稱(chēng)是關(guān)于解集合和算法 A 的下降函數(shù) 。一般地，對(duì)于問(wèn)題（1），通常取 |f ( x) | 或 f(x) 作為下降函數(shù)。定義 5.1.4（閉映射） 設(shè) X 和 Y 分別是空間p 和q 中的非空閉集。A : XY 為點(diǎn)到集的映射。如果

20、x( k)X , x( k)x,蘊(yùn)含 yA( x) ，則稱(chēng)映射A 在 xX 處是y(k )A( x( k) ), y( k )y閉的。如果 A 在集合 ZX 上每一點(diǎn)都是閉的，則稱(chēng)A 在集合 Z 上是閉的。定義 5.1.5 （合成映射） 設(shè) X ，Y 和 Z 分別是空間n ,p , q 中的非空閉集。 B : XY和C:YZ 為點(diǎn)到集的映射。合成映射 A=CB 定義為 A(x)C( y) ，它是點(diǎn)到y(tǒng) B (x )集的映射 A: XZ 。定理 5.1.1 設(shè)B: XY和C:YZ 是點(diǎn)到集映射， B 在點(diǎn) x 處是閉的， C 在 B(x) 上是閉的。 再設(shè)若 x( k)x 且 y( k)B(x(

21、k ) ) ，則存在收斂子序列 y( kj ) y(k ) ，那么，合成映射 A=CB 在 x 處是閉的。推論 1設(shè)B:XY和C:YZ 是點(diǎn)到集映射， B 在點(diǎn) x 處是閉的， C 在 B(x) 上是閉的， 且 Y 是緊的 ，則 A=CB 在 x 處是閉的。推論 2設(shè)B:XY是點(diǎn)到點(diǎn)映射， C :YZ 是點(diǎn)到集映射。如果B 在點(diǎn) x 處連續(xù) ，C 在 B(x) 上是閉的，則A=CB 在 x 處是閉的。定理 5.1.2（收斂定理 ）設(shè) A 為 X 上的一個(gè)算法，為解集合，給定初始點(diǎn)x(1)X ，進(jìn)行如下迭代：如果 x(k )，則停止迭代；否則，令x(k 1)A(x(k ) ) 。用 k+1 代替

22、 k，重復(fù)以上過(guò)程。這樣，產(chǎn)生的序列為 x(k ) 。又設(shè)1） x(k) 含于 X 的緊子集中；2）存在一個(gè)連續(xù)函數(shù)，它是關(guān)于3）映射 A 在的補(bǔ)集上是閉的。和 A 的下降函數(shù)；則 x(k ) 的任一收斂子序列的極限屬于。Note：收斂定理的三個(gè)條件缺一不可，尤其是第3 個(gè)條件， 要求算法在解集合的補(bǔ)集上是閉的，顯得特別重要，許多算法失效，往往歸因于這個(gè)條件不滿足。收斂準(zhǔn)則 ：運(yùn)用迭代下降算法，當(dāng) x 時(shí)才終止迭代，但是在許多實(shí)際情況中，程，需要無(wú)限次迭代。因此，為了解決實(shí)際問(wèn)題，需要規(guī)定一些實(shí)用的這是一個(gè)取極限的過(guò)收斂準(zhǔn)則 ，或稱(chēng) 停步準(zhǔn)則 。常用的收斂準(zhǔn)則有：自變量改變充分小時(shí)，即|x(k

23、 1)x( k )|或| x(k1)x( k) | x( k )|函數(shù)值下降量充分小時(shí)，即f (x(k )f ( x( k 1)f (x(k ) )f (x( k 1) )或| f ( x(k ) ) |無(wú)約束優(yōu)化中，當(dāng)梯度充分接近0 時(shí)，即 | f ( x( k) ) |其中， 為事先給定的充分小的正數(shù)。當(dāng)然，還可以根據(jù)收斂定理，參照上述準(zhǔn)則，定義新的收斂準(zhǔn)則。收斂速率 ：定義 5.1.5設(shè)序列 x( k )*lim| x( k 1)x* |的非負(fù)數(shù) p 收斂于 x ，定義滿足 0(k)*pk| xx|的上確界為序列x 的收斂級(jí) 。若序列的收斂級(jí)為p，則稱(chēng)序列是p 級(jí)收斂的。若在定義中，p1

24、且1 ，則稱(chēng)序列是以收斂比x 線性收斂 的；若在定義中，p1，或者 p 1且0 ，則稱(chēng)序列是 超線性收斂 的。在某種意義上講，p 越大，序列收斂越快。當(dāng)p 相同時(shí)，越小，序列收斂越快。非下降算法的收斂性調(diào)研。（下一步）（壓縮映射原理） ：5.2迭代步長(zhǎng)此處迭代步長(zhǎng)不包括用線搜的方法得到的步長(zhǎng)，而是迭代前就已經(jīng)確定的步長(zhǎng)。【 10】步長(zhǎng)大小規(guī)則：1） Constant step size:k2） Constant step length: k( k),| x( k 1)x(k ) |2| g|23） （square summable but not summable） k 0,2,k,如kk 1

25、k 1( t )a , a 0, b 0bt4） （ diminishing ） 和 無(wú) 限 ， 但 單 項(xiàng) 極 限 為0 ： k0,limk0,k， 如kk 1( t )a, a0t5） k0,limk 0,kkk15.3一階算法梯度算法對(duì)于光滑的凸問(wèn)題。迭代公式 為（負(fù)梯度方向） ：x( t 1)x(t )(t ) f (x(t ) )梯度算法是下降算法，即每一次迭代，目標(biāo)值都會(huì)下降。如果滿足以下條件即可收斂：1）梯度滿足 Lipschitz連續(xù)條件，即存在常數(shù)L 0，使得|f ( x)f ( y) |2L | x y |2, x, y 成立。2） 原問(wèn)題有有限的最優(yōu)值f *，最優(yōu)解為 x

26、*；3） 步長(zhǎng)足夠小。定理 .5.3.1 如果一個(gè)問(wèn)題滿足以上條件，設(shè) x(t ) 是由梯度迭代得到的序列，迭代步長(zhǎng)為( t ),01/ L ，則有 f ( x(t ) )f *1| x*x(0) |22。（固定步長(zhǎng)的情形）2t推論：對(duì)于精度，需要的迭代次數(shù)為O(1/) 。對(duì)于有約束的光滑凸問(wèn)題，可以使用影射梯度 （ Projection gradient ）算法：x(t 1)P x(t )(t ) f ( x(t ) )X其中， PX x 表示將 x 影射到約束集X 上。子梯度算法簡(jiǎn)介針對(duì)非光滑的凸問(wèn)題。與普通的梯度算法相比，子梯度算法可以直接用于不可微目標(biāo)函數(shù)，但不是下降算法10】。缺點(diǎn)

27、：子梯度算法比內(nèi)點(diǎn)算法或牛頓算法（無(wú)約束時(shí)）慢。屬于一階方法，性能很大程度上依賴(lài)問(wèn)題規(guī)模和條件。優(yōu)點(diǎn) ：適用范圍廣；內(nèi)存要求小；與原/對(duì)偶分解算法聯(lián)合，可能得到簡(jiǎn)單的分布式算法?；径x定義 5.3.2 （子梯度或次梯度， subgradient）如果向量g 滿足()( )T(),，yf xg yxyf則稱(chēng) g 為 f 在 x 處的 子梯度 。定理 5.3.3 如果 f 在 x 處可微， 則子梯度就等于梯度，即 gf (x) ；否則， g 可能不唯一。如圖，凸函數(shù) (藍(lán)線 )在 x0 處的子梯度（紅線的斜率）不唯一。圖3 子梯度示意圖定義（次微分 ， Subdifferential ） f 在

28、 x 處的所有子梯度組成的集合，記作f ( x) 。定理次微的性質(zhì)：1） 閉的凸集；2） 如果 f 是凸的，且在x 附近取值有限，則非空；a,b ， a,b 為單側(cè)導(dǎo)數(shù)。3） 如果 f 在 x 處可微，則f ( x)f ( x)一般情況下，我們只要找到一個(gè)滿足要求的子梯度即可。定理對(duì)偶函數(shù) q(,) 是和的凹函數(shù)，q(,) 在 ( ,) 處的一個(gè)子梯度為( f1 ( x* ( ,),., fm ( x* ( ,), h1 ( x* ( ,),., hp (x* ( ,)其中， x* (,)arg min L( x,) 。x算法迭代公式 ：x(t 1)x( t )( t ) g(t )對(duì)于有約束

29、的問(wèn)題，可以使用影射子梯度 算法：x( t 1)PX x(t )(t ) g(t ) 其中， PX x 表示將 x 影射到約束集X 上。對(duì)于對(duì)偶方法，有：x(k 1)x* ( k ) )( k 1) (k)k g (k ) ( x( k) ) (k)k g(x(k ) )收斂結(jié)果定理 5.3.6如果凸問(wèn)題滿足如下條件：1） 函數(shù) fLipschitz 連續(xù)，即存在L0 ，有 | f ( x)f ( y) |2 L | x y |2, x, y ；2） 函數(shù) f有有限的最優(yōu)值 f *，相應(yīng)最優(yōu)解為x* ；則有 min f ( x(k ) ) f * | x*x(0)|22t 2 L2。0 k t

30、2t推論：設(shè) fbest(k) 是前 k 次迭代得到的最優(yōu)值，則1） 對(duì)于步長(zhǎng)1） 2），有 lim( fbest(k)f * ), f *inf x f ( x)k2） 對(duì)于步長(zhǎng)( k )f*3） 4） 5），有 lim fbestk3） 如果 f 可微，則對(duì)于固定步長(zhǎng)，只要其足夠小，可以保證收斂，見(jiàn)梯度法。6. Fractional 規(guī)劃 【11】BifunctionParametric approach：Dinkelbach-type算法：能收斂。條件？同步 /異步分布式更新算法 【12】迭代： x :A( x)Jacobi 類(lèi)型： x 的所有部分可以在一次迭代中同時(shí)更新。即x(t1)A

31、(x(t) 。便于并行運(yùn)算。Gauss-Seidel 類(lèi)型： x 的組件部分更新，在計(jì)算某個(gè)部分時(shí)，可以利用其它部分的最新值。即 xi (t1)Ai ( x1 (t1),.,xi 1 (t1),xi (t),., xp (t ),i 。不便于并行運(yùn)算。7.1異步迭代算法異步算法：假設(shè)有n 個(gè)處理器/節(jié)點(diǎn)，將全局決策變量分成n 個(gè)部分，每個(gè)處理器/節(jié)點(diǎn)i 以自己的節(jié)奏，使用它能獲得的（不一定是最新的）來(lái)自其他處理器/節(jié)點(diǎn)j 關(guān)于x 的其它部分的值xj來(lái)，更新變量自己負(fù)責(zé)的x 的那部分xi 。（不需要等到接收到前一次迭代產(chǎn)生的所有消息。 ）優(yōu)點(diǎn)：降低了同步的開(kāi)銷(xiāo)；重啟方便；降低了瓶頸效應(yīng)； 某個(gè)節(jié)

32、點(diǎn)出錯(cuò)了， 只會(huì)影響與它強(qiáng)相關(guān)的部分節(jié)點(diǎn)， 即將錯(cuò)誤本地化。收斂加速，因?yàn)镚auss-Seidel 效應(yīng)，即新的信息被更快地包含進(jìn)更新公式里了。缺點(diǎn)：不能用數(shù)學(xué)表達(dá)式x(t1)f (x(t )一般描述：x(0)Xxi (t1)Ai (x1( 1i (t ),., xn ( ni(t ), t T,（ 7-1）xi (t), else其 中 ， t為時(shí)間索引或迭代索引， T表 示 xi 可 能 更 新 的 時(shí) 間 點(diǎn) 集 合 ，0ij (t )t , t0 。定 義 7.1.1（完全異步）T無(wú) 限 ， 且 如 果 tk 是 T的元素組成序列，則lim tj(tk ), j 。k定義 7.1.2

33、（部分異步） 存在常數(shù) B ，滿足：1） 對(duì)于每個(gè) t0 和每個(gè) i，集合 t, t1,.,tB 1 至少有一個(gè)元素屬于T（在B步內(nèi)至少更新一次） 。2） tBji(t)t ,i, j , tT3） ii(t )t ,i ,tT（自己節(jié)點(diǎn)的信息永遠(yuǎn)都是最新的）B 叫做異步測(cè)度 ，表征一個(gè)節(jié)點(diǎn)對(duì)來(lái)自其他節(jié)點(diǎn)的信息能允許的過(guò)時(shí)（outdated）程度。Jacobi 類(lèi)型的同步迭代是B=1 的特殊情形。對(duì)異步算法的收斂情況，可能有以下三種：在完全異步情況下收斂；在完全異步時(shí)不收斂，但在部分異步時(shí)對(duì)每個(gè)B 值，都收斂，在部分異步情況下，如果B 足夠小，能收斂；而 B 足夠大時(shí)，可能不收斂。7.1.1完

34、全異步pp命題 7.1.1（充分條件） XX in，假設(shè)對(duì)每個(gè) i 1,., p，存在一個(gè)屬i 1i 1于 X 的子集的序列 X i (k) ，使得：1） Xi (k 1)X i (k),k 0p2） X (k )Xi (k) 滿足 f ( x)X (k1), x Xi 13）序列 x(k) 的每個(gè)滿足 x(k)X (k),k 的極限點(diǎn)，是f 的一個(gè)不動(dòng)點(diǎn)；則，在完全異步，且 x(0) X (0)的情況下，由（ 7-1）得到的序列 x(k ) 的每個(gè)極限點(diǎn)都是 f 的一個(gè)不動(dòng)點(diǎn)。對(duì)于零時(shí)延的異步迭代，當(dāng)且僅當(dāng)存在一個(gè)Lyapunov 類(lèi)型（？）函數(shù)來(lái)驗(yàn)證，才能保證異步更新的收斂性。最大范數(shù)壓縮

35、 ：| x | max | xi|i , xini ,| |i 是ni 上的一個(gè)范數(shù)， wi是一個(gè)正的標(biāo)量。wi壓縮特征 ：如果映射 A 滿足，存在一個(gè)0,1) ，使得 | A(x) x* | x x* |, x X 成立，其中 x* 為 A 的一個(gè)不動(dòng)點(diǎn)，則稱(chēng)A 具有 壓縮特征 。給定一個(gè)向量 x(k)具有壓縮特征(Contraction Property)的迭代映射舉例：1） 線性迭代：A(x)M xb ，其中M 為 nn 的矩陣，且(| M|)1,| M|表示元素為M的元素的絕對(duì)值的矩陣，(| M|) 為| M|的頻譜半徑，即|M|的最大特征值。(| M |)1是異步收斂的充要條件。2）

36、 梯度迭代： A( x)xf ( x) ，f 為要優(yōu)化（最小化）的目標(biāo)函數(shù)，二階連續(xù)可微，其Hess 矩陣滿足有界和對(duì)角占優(yōu)條件， 即|ij2 f ( x) |ii2 f (x), i ,xX ，其中j i為正常數(shù)。 (與 5.3.1 中的條件等價(jià)嗎？前面是同步，這里是完全異步。)pn 為閉凸集，n 為3） 用于可變 (variational?) 不等式的影射算法：XXif : Xi 1給 定 函 數(shù) ， 尋 求 向 量 x*X 滿 足 f ( x* )T (x x* )0, x X 。 影 射 算 法 為 ：x(t 1) x( t )f ( x( t ) )，其中 為 X 上的正交影射。 如

37、果滿足映射 xxf (x)為最大范數(shù)壓縮映射 （如當(dāng) f 的雅各比矩陣滿足對(duì)角占優(yōu)條件），則完全異步可以保證收斂到 x*。4） 波形松弛方法單調(diào)映射 ：映射函數(shù) A :nn 連續(xù)單調(diào) （即有 xy 時(shí)，有 A( x)A( y) ），且有唯一的不動(dòng)點(diǎn) x* 。假設(shè)存在向量u,v ，滿足 u A(u) A(v)v ，()x|Ak( )x Ak() ，則由命題X kuv可知完全異步收斂，異步算法的收斂速率至少和相應(yīng)的同步算法一樣好。部分異步( )( (), ( 1),., (1)B來(lái)描述算法在 t 時(shí)刻的狀態(tài)。使用向量x tx tx tBXz t假設(shè)迭代映射連續(xù)，且不動(dòng)點(diǎn)集X *X 非空，所有 z*

38、( x* , x* ,., x* ), x*X 組成的集合為 Z*。命題 7.1.2假設(shè)存在一個(gè)正整數(shù)t * ，和一個(gè)連續(xù)函數(shù) d : X B0,) ，該函數(shù)具有以下特征：對(duì)每個(gè)不屬于Z* 的初始點(diǎn) z(0)，以及之后產(chǎn)生的序列（滿足部分異步條件），有 d (z(t * )d ( z(0), d (z(1)d( z(0) 。則由部分異步迭代產(chǎn)生的序列 z(t) 的每個(gè)極限點(diǎn)都屬于 Z* 。如果函數(shù) d 的形式為 d ( z) inf* | zz*| ，且算法 A 為線性迭代形式，則 d( z(t) 以zZ幾何級(jí) (geometric progression) 的速度收斂到 0。8. 要解決的問(wèn)

39、題(x, , ) 能否收斂到全局最優(yōu)？1） 需要保證對(duì)偶間隙為0；2） 需要保證迭代算法存在不動(dòng)點(diǎn)，且不動(dòng)點(diǎn)為局部最優(yōu)解；3） 然后來(lái)證明迭代算法收斂到不動(dòng)點(diǎn)。算法有兩種：x(t1)x* (t ),(t)1） (t1)A(t )，子梯度算法屬于此類(lèi)，此種方法屬于Jacobi 算法，屬于(t1)A(t )B=1 的異步迭代更新算法，其收斂性調(diào)研見(jiàn)7。x(t1)x* ( (t ), (t)2） (t1)A(t ),(t)，此種方法屬于 Gauss-seidel 算法。（猜想，收斂速率應(yīng)(t1)A(t 1), (t )該比 1）更快，因?yàn)樽羁斓厥褂昧俗钚碌男畔?。因?yàn)椤?2】中沒(méi)有異步迭代算法與G-S

40、算法的對(duì)應(yīng)，從（7-1）看出，異步迭代中，在 t+1步中使用的是t 步儲(chǔ)存的其他部分的值，從這個(gè)角度，異步迭代的定義好像是沒(méi)有包括G-S 算法的。不過(guò)，如果假設(shè)每個(gè)部分更新完后，立即就更新了其他節(jié)點(diǎn)/處理器存儲(chǔ)的它的值，則G-S 算法還是可以歸為異步迭代算法的。 為了確定，還需要再調(diào)研。 ）參考文獻(xiàn)【1】陳寶林，最優(yōu)化理論與算法（第2 版），清華大學(xué)出版社2】 D. P. Bertsekas, Nonlinear Programming , 2nd ed. Athena Scientific, 1999.3】【4】【5】S. Boyd and L. VandenbergheConvex Opt

41、imization ,2004 :Cambridge Univ. PressM. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, Layering as optimizationdecomposition: A mathematical theory of network architecture s, Proceedings of the IEEE, vol. 95, no. 1, pp. 255-312, January 2007.6】 Yixin Chen, A Duality Theory with Zero Duality

42、Gap for Nonlinear Programming7】 P. Hande, S. Zhang, and M. Chiang, Distributed rate allocation for inelastic flows,IEEE/ACM Transactions on Networking, vol. 15, no. 6, pp. 1240-1253, December 2007.【8】W. Yu and R. Lui,Dual Methods for Nonconvex Spectrum Optimization of MulticarrierSystems, IEEE Trans. Commun., vo