迭代收敛调研

1、认知无线网络行为分析与网络效能研究973 项目；认知无线网络的全局性能优化；迭代收敛的全局最优性调研；简介本文档主要分两大部分：第一部分， 2,3 节主要是问题是否存在全局最优解，以及局部最优解为全局最优解的条件，涉及到凸优化和对偶分解的基本理论。第二部分，迭代算法能收敛到最优的条件。基本概念与定理2.1全局最优与局部最优min f ( x)x S（ 1）S gi (x)0, i 1,2,., m; hj (x) 0, j 1,2,., p; xX 其中，X为n的一个紧子集1【1】。定义 1.1.1 （全局最优解）如果存在一个点x*S ，使得 f ( x* ) f (x), xS 成立，则称

2、x* 为问题（ 1）的全局最优解，f (x*) 为全局最优值。定义 1.1.2（局部最优解）如果存在xS 的邻域 W ，使得对所有 xSW 都有不等式 f ( x )f ( x) 成立，则 x 为问题（ 1）的局部最优解。【 2】图1 一维变量情形时，无约束优化问题的极值示例图局部最优条件：定 义1.1.3 （可行方向）设集合Sn,xcl S d是 非零向 量，若 存在，使得,有界闭集即为紧集。xd S,(0,) ，则称 d 为集合S 在 x 的可行方向 。定义 1.1.4（下降方向 ） f(x) 为定义在n上的实函数， x*n ，d 为非零向量，若存在0 ，使得 f ( xd)f ( x),

3、(0,) ，则称 d 为 f(x) 在 x 处的下降方向 。推论 1.1.1：如果f (x* )T d0，则 d 为 f(x) 在 x* 处的一个下降方向。记 D d | d 0, x*cl S,0,使得(0, ), x*d SF d | f (x* )T d 0定理1.1.3（一阶必要条件 ）假设 f在 x* 处可微，如果 x*是（ 1）的局部最优解，则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,., ，即等号成立的不等式约束。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* 局部最优 =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* 局部最优。全局最优存在条件：1） f 连续，且S 为紧集；2） S 为闭集，且f 连续，且coercive?，即 | x |时 f ( x)。2.2凸优化（凸集、凸函数的定义与性质，此处省略）定理凸规划的局部极小点就是全局极小点，且极小点的集合为凸集。如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点是唯一的。定义 2.2.1（拟凸函数quasi-convex ）设 S 是n 中的一个非空凸集，f 是定义在S 上的实函数。若对任 意 的 x(1) ,x(2)S及 每一 个 数(0

6、,1)， 有(1)( 1 x )(2 )ax x f(1)为拟(凸函数)。（更直观的定义，f ( x) fmx(，则称) ,f满足 xS | f ( x), 为凸集3 ）【 】定理 2.2.2若 f ( x) 是凸集 S 上的拟凸函数， x 是 f (x) 在 S 上的严格局部极小点，则 x也是 f ( x) 在 S 上的全局极小点。定义 2.2.2（伪凸函数 pseudo-convex）设 S 是n 中的非空开凸集， f (x) 是定义在 S 上的 可 微 实 函 数 ， 如 果 对 任 意 两 点 x(1) ,x(2)S ， 有 (x( 1 ) x ( 2)T)f (x ( 2)0蕴 含f

7、 (x( 1 ) f (x( 2 )，则称 f (x) 是伪凸函数 。)定理若 f (x) 是开凸集S 上的伪凸函数， 且对某个 xS 有f ( x)0 ，则 x 是(x) 在 S 上的全局极小点。凸拟凸伪凸图2 凸、拟凸、伪凸关系图2.3对偶分解理论这里的对偶指拉格朗日对偶。对偶是约束优化中一个很重要的概念，它为很多约束分解方案（如可分离规划） ，以及得到空间分解算法（如分支定界）的下界，提供了理论基础。【 4】2.3.1 拉格朗日对偶1）。定义 2.3.1（原始问题）问题（定义 2.3.2（拉格朗日函数）( ,)()()( )（ 2）L xf xi gixi hixi定义 2.3.3（对偶

8、函数）g(, )minL( x,)xX定义 2.3.4（对偶问题）max g(,)0,定理 2.3.1对偶函数是和的凹函数， 即对偶问题为凸问题。如果 f ( x) 严格凸， 则对偶函数连续可微。假设原始问题的最优解为x*，最优值为 p*，对偶问题的最优解为* ,*，最优值为 d *定理 2.3.2（弱对偶） d*p*定理 2.3.3（强对偶） d*p*，即对偶间隙为0。定义 2.3.5（ slater 条件）原始问题存在严格可行点。定理 2.3.3如果原问题为凸问题，且满足slater 条件，则满足强对偶。定义 2.3.6（ KKT 条件）假设目标函数和约束函数均可微，且满足强对偶， (x*

9、 ,*, *)为原始问题和对偶问题的最优解对，则*处的偏导为0；*)*)*)01）（ 2）在 xf (xigi ( xihi (xii2）互补松弛： i gi ( x)0,i3）原问题和对偶问题的约束：gi ( x) 0,i1,., m; hi(x* )0, i1,., p;0 。定理 2.3.4对于凸问题， KKT条件是充要条件（即2.3.6 的反向也成立） 。分解【5】分解的基本思想 ：基于目标函数和约束的特定结构，将问题分解为一个主问题和一系列更易求解的子问题。 这些子问题可以独立求解，但是一般需要协调器（主问题）来保证局部决策能收敛到全局最优。对偶分解的基本思想是利用对偶函数的结构来提

10、高计算效率或得到分布式算法。价格机制解释：将耦合的约束看作公共资源， 将对偶变量看作是公共资源的价格， 对于供给方， 如果资源紧张时，提高价格，在资源充裕的时候，降低价格；对于需求方，根据当前价格最大化自身净效益，来请求资源。这样就可以达到需求近似与供给对齐。耦合的约束的处理举例：min1 (x1)2 ( x2 )st. x1x2xtot约束中变量是耦合的。1）引入对偶变量，将约束松弛，得到：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 ( )这样就成了一个可分离问题。2）对于给定的，可以并行求解得到使1( x1 )x1 、 2 (x2 )x2 最小的 x1 、 x2 ，记为 x1* ( ) 、 x*2 ( ) 。3）使用影射子梯度算法，更新(t 1)(t )(t ) (xtotx1* ( )x*2 ( )4）如果满足迭代停止条件，则终止；否则，转入2)。耦合的目标的处理同一决策变量包含在不同目标函数里，或一个目标函数包含多个决策变量。一般思路是将目标耦合转化为约束耦合。举例：min1 ( x)2 ( x)引入 x1 和 x2 ，将问题转化为min1 (

12、x1 )2 ( x2 )st.x1x2这样就可以利用上一节的方法求解了。对偶分解的局限即使在强对偶条件下，对偶问题的一个解只能提供原问题的最优值，而不一定能提供原问题的最优解。对于非最优的对偶变量值，x* ( ,)arginfL ( x,)不一定是原问题的x可行解。因此，如果不能容忍这种约束违背，需要一种恢复原始可行解的方法。当对偶函数可微时， 原始解迭代将随对偶变量收敛到最优而收敛到最优； 当对偶函数不平滑时，原始解迭代往往不收敛。2.4扩展的对偶理论 【 6】传统的对偶理论对于非凸问题，尤其是离散或混合整数的问题，可能会导致对偶间隙不为 0。其 1m -惩罚函数为Lm (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 为惩罚因子。扩展的对偶函数为q(,)min Lm ( x, , x X) 。扩展的对偶问题为max q(,)s.t0,02.4.1连续优化问题x X ，如果不存在这样的方向定义1.4.1（约束品性条件）对于连续优化问题，点pn 使得连续有效不等式约束和连续等式约束沿该方向的的方向导数均为0，则称满足约束品性条件。定义 1.4.2 （可行集的-扩展）0 为一个标量值， S x | x X

14、, min | y x | 。y S引理 1.4.1对任意常数0 ，存在一个有限的标量值0 ，使得| g (x) |2| h( x) |2, x XS定理 1.4.1假设 x*X 是连续优化问题 （ 1）的全局极小解， 且 x* 满足约束品性条件，则1）存在有限的*0,*0，使得f ( x* ) min Lm ( x, * , * ),*, *x X2）对于扩展的对偶问题，对偶间隙为0，即 q*f ( x* ) 。离散优化问题此时，对应问题 （ 1）中的 X为有限的离散集， 假设 f 有下界， 不要求 f,g,h 连续或可微。定理 1.4.2 假设 x*X 是离散优化问题的全局极小解，则（注意

15、：这里不需要约束品性条件）1）存在有限的*0,*0，使得f ( x* ) min Lm ( x,* ,* ),* ,*x X2）对于扩展的对偶问题，对偶间隙为0，即 q*f ( x* ) 。2.4.3 混合优化问题此时优化变量x 可表示成 x( y, z)YZ ，其中 y 为连续变量， z 为离散变量。定理 1.4.3 假设 x*YZ 是混合优化问题的全局极小解，则1）存在有限的*0,*0，使得f ( x* ) minLm ( x,* ,* ),* ,*x Y Z2）对于扩展的对偶问题，对偶间隙为0，即 q*f ( x* ) 。2.4.4 存在问题由于惩罚函数带有绝对值符号或影射算子，使得求导

16、， 以及分解更困难， 目前还没有得到分布式的求解方法。强对偶的特殊情形对 K 个用户， N 个载波的 OFDM 系统：maxf n ( xn )n（ 2-1）s.thn ( xn )P其中， xnK , fn :K, hn :KK 。定义 3.1（时间共享）假设 x* 、 y*分别为 PPx 、 PP 时问题（ 2-1）的最优解，如nny果对0,1 ，存在一个可行解zn ，满足Nn 1hn ( zn )Px(1 ) Py ,，NNNf n ( zn )n 1fn ( xn* ) (1)fn ( yn* )n 1n 1则称问题（ 2-1）满足时间共享条件。定理 3.1如果 xn* ( )arg

17、max L( xn, ) 在* 处连续，则对偶间隙为 0【】7。xn定理 3.2将问题（ 2-1）的最优值看作P 的函数，如果该最优值是 P 的凹函数，则问题（ 2-1）满足时间共享条件，对偶间隙为【 】0 8 。定理 3.1的条件是定理3.2 条件的充分非必要条件。中证明在多载波系统中，对于(2-1)形式的优化问题，当子载波数无限大时，定理【8】3.2 的条件总是满足。在【 9】 中，仿真表明子载波数为8，就能满足条件。4. 总结对偶间隙为0 的情况：1） 如果原问题为凸问题，且满足2） 拟凸与伪凸的性质；slater 条件；3） 对于非凸问题，如果原问题满足时间共享条件；数值算法收敛性前面

18、部分已经找到了保证强对偶性， 即局部最优即为全局最优的条件， 接下来的算法只要保证能找到一个局部最优点就满足要求了，对于迭代算法，则要求收敛值是局部最优值。由于利用最优性条件求解一个问题时， 一般需要解非线性方程组， 这本身就是一个困难问题，因此求解非线性规划一般采取数值计算方法。5.1算法收敛基本问题（迭代下降 算法）定义（算法）算法 A 是定义在空间X 上的点到集的映射，即对每一个点xX ，给定一个子集A( x)X 。定义（解集合） 一般把满足某些条件的点集定义为解集合，当迭代点属于这个集合时，停止迭代。例如，在无约束优化问题中，可以定义解集合为 x |f ( x) |0 ；在约束优化问题

19、中，可以定义为 x | x为 KT点 或 x | xS, f ( x)b，其中b 为某个可接受的目标函数值。当然，还可以有其他定义方法。定义（下降函数） 设X 为解集合， A 为 X 上的一个算法，( x) 是定义在 X上的连续实函数，若满足以下条件：1且y A( x)时，( y)( x)；（严格下降） 当 x2） 当 x且 yA( x) 时，( y)( x) ；则称是关于解集合和算法 A 的下降函数 。一般地，对于问题（1），通常取 |f ( x) | 或 f(x) 作为下降函数。定义 5.1.4（闭映射） 设 X 和 Y 分别是空间p 和q 中的非空闭集。A : XY 为点到集的映射。如果

20、x( k)X , x( k)x,蕴含 yA( x) ，则称映射A 在 xX 处是y(k )A( x( k) ), y( k )y闭的。如果 A 在集合 ZX 上每一点都是闭的，则称A 在集合 Z 上是闭的。定义 5.1.5 （合成映射） 设 X ，Y 和 Z 分别是空间n ,p , q 中的非空闭集。 B : XY和C:YZ 为点到集的映射。合成映射 A=CB 定义为 A(x)C( y) ，它是点到y B (x )集的映射 A: XZ 。定理 5.1.1 设B: XY和C:YZ 是点到集映射， B 在点 x 处是闭的， C 在 B(x) 上是闭的。 再设若 x( k)x 且 y( k)B(x(

21、k ) ) ，则存在收敛子序列 y( kj ) y(k ) ，那么，合成映射 A=CB 在 x 处是闭的。推论 1设B:XY和C:YZ 是点到集映射， B 在点 x 处是闭的， C 在 B(x) 上是闭的， 且 Y 是紧的 ，则 A=CB 在 x 处是闭的。推论 2设B:XY是点到点映射， C :YZ 是点到集映射。如果B 在点 x 处连续 ，C 在 B(x) 上是闭的，则A=CB 在 x 处是闭的。定理 5.1.2（收敛定理 ）设 A 为 X 上的一个算法，为解集合，给定初始点x(1)X ，进行如下迭代：如果 x(k )，则停止迭代；否则，令x(k 1)A(x(k ) ) 。用 k+1 代替

22、 k，重复以上过程。这样，产生的序列为 x(k ) 。又设1） x(k) 含于 X 的紧子集中；2）存在一个连续函数，它是关于3）映射 A 在的补集上是闭的。和 A 的下降函数；则 x(k ) 的任一收敛子序列的极限属于。Note：收敛定理的三个条件缺一不可，尤其是第3 个条件， 要求算法在解集合的补集上是闭的，显得特别重要，许多算法失效，往往归因于这个条件不满足。收敛准则 ：运用迭代下降算法，当 x 时才终止迭代，但是在许多实际情况中，程，需要无限次迭代。因此，为了解决实际问题，需要规定一些实用的这是一个取极限的过收敛准则 ，或称 停步准则 。常用的收敛准则有：自变量改变充分小时，即|x(k

23、 1)x( k )|或| x(k1)x( k) | x( k )|函数值下降量充分小时，即f (x(k )f ( x( k 1)f (x(k ) )f (x( k 1) )或| f ( x(k ) ) |无约束优化中，当梯度充分接近0 时，即 | f ( x( k) ) |其中， 为事先给定的充分小的正数。当然，还可以根据收敛定理，参照上述准则，定义新的收敛准则。收敛速率 ：定义 5.1.5设序列 x( k )*lim| x( k 1)x* |的非负数 p 收敛于 x ，定义满足 0(k)*pk| xx|的上确界为序列x 的收敛级 。若序列的收敛级为p，则称序列是p 级收敛的。若在定义中，p1

24、且1 ，则称序列是以收敛比x 线性收敛 的；若在定义中，p1，或者 p 1且0 ，则称序列是 超线性收敛 的。在某种意义上讲，p 越大，序列收敛越快。当p 相同时，越小，序列收敛越快。非下降算法的收敛性调研。（下一步）（压缩映射原理） ：5.2迭代步长此处迭代步长不包括用线搜的方法得到的步长，而是迭代前就已经确定的步长。【 10】步长大小规则：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 ） 和 无 限 ， 但 单 项 极 限 为0 ： k0,limk0,k， 如kk 1( t )a, a0t5） k0,limk 0,kkk15.3一阶算法梯度算法对于光滑的凸问题。迭代公式 为（负梯度方向） ：x( t 1)x(t )(t ) f (x(t ) )梯度算法是下降算法，即每一次迭代，目标值都会下降。如果满足以下条件即可收敛：1）梯度满足 Lipschitz连续条件，即存在常数L 0，使得|f ( x)f ( y) |2L | x y |2, x, y 成立。2） 原问题有有限的最优值f *，最优解为 x

26、*；3） 步长足够小。定理 .5.3.1 如果一个问题满足以上条件，设 x(t ) 是由梯度迭代得到的序列，迭代步长为( t ),01/ L ，则有 f ( x(t ) )f *1| x*x(0) |22。（固定步长的情形）2t推论：对于精度，需要的迭代次数为O(1/) 。对于有约束的光滑凸问题，可以使用影射梯度 （ Projection gradient ）算法：x(t 1)P x(t )(t ) f ( x(t ) )X其中， PX x 表示将 x 影射到约束集X 上。子梯度算法简介针对非光滑的凸问题。与普通的梯度算法相比，子梯度算法可以直接用于不可微目标函数，但不是下降算法10】。缺点

27、：子梯度算法比内点算法或牛顿算法（无约束时）慢。属于一阶方法，性能很大程度上依赖问题规模和条件。优点 ：适用范围广；内存要求小；与原/对偶分解算法联合，可能得到简单的分布式算法。基本定义定义 5.3.2 （子梯度或次梯度， subgradient）如果向量g 满足()( )T(),，yf xg yxyf则称 g 为 f 在 x 处的 子梯度 。定理 5.3.3 如果 f 在 x 处可微， 则子梯度就等于梯度，即 gf (x) ；否则， g 可能不唯一。如图，凸函数 (蓝线 )在 x0 处的子梯度（红线的斜率）不唯一。图3 子梯度示意图定义（次微分 ， Subdifferential ） f 在

28、 x 处的所有子梯度组成的集合，记作f ( x) 。定理次微的性质：1） 闭的凸集；2） 如果 f 是凸的，且在x 附近取值有限，则非空；a,b ， a,b 为单侧导数。3） 如果 f 在 x 处可微，则f ( x)f ( x)一般情况下，我们只要找到一个满足要求的子梯度即可。定理对偶函数 q(,) 是和的凹函数，q(,) 在 ( ,) 处的一个子梯度为( f1 ( x* ( ,),., fm ( x* ( ,), h1 ( x* ( ,),., hp (x* ( ,)其中， x* (,)arg min L( x,) 。x算法迭代公式 ：x(t 1)x( t )( t ) g(t )对于有约束

29、的问题，可以使用影射子梯度 算法：x( t 1)PX x(t )(t ) g(t ) 其中， PX x 表示将 x 影射到约束集X 上。对于对偶方法，有：x(k 1)x* ( k ) )( k 1) (k)k g (k ) ( x( k) ) (k)k g(x(k ) )收敛结果定理 5.3.6如果凸问题满足如下条件：1） 函数 fLipschitz 连续，即存在L0 ，有 | f ( x)f ( y) |2 L | x y |2, x, y ；2） 函数 f有有限的最优值 f *，相应最优解为x* ；则有 min f ( x(k ) ) f * | x*x(0)|22t 2 L2。0 k t

30、2t推论：设 fbest(k) 是前 k 次迭代得到的最优值，则1） 对于步长1） 2），有 lim( fbest(k)f * ), f *inf x f ( x)k2） 对于步长( k )f*3） 4） 5），有 lim fbestk3） 如果 f 可微，则对于固定步长，只要其足够小，可以保证收敛，见梯度法。6. Fractional 规划 【11】BifunctionParametric approach：Dinkelbach-type算法：能收敛。条件？同步 /异步分布式更新算法 【12】迭代： x :A( x)Jacobi 类型： x 的所有部分可以在一次迭代中同时更新。即x(t1)A

31、(x(t) 。便于并行运算。Gauss-Seidel 类型： x 的组件部分更新，在计算某个部分时，可以利用其它部分的最新值。即 xi (t1)Ai ( x1 (t1),.,xi 1 (t1),xi (t),., xp (t ),i 。不便于并行运算。7.1异步迭代算法异步算法：假设有n 个处理器/节点，将全局决策变量分成n 个部分，每个处理器/节点i 以自己的节奏，使用它能获得的（不一定是最新的）来自其他处理器/节点j 关于x 的其它部分的值xj来，更新变量自己负责的x 的那部分xi 。（不需要等到接收到前一次迭代产生的所有消息。 ）优点：降低了同步的开销；重启方便；降低了瓶颈效应； 某个节

32、点出错了， 只会影响与它强相关的部分节点， 即将错误本地化。收敛加速，因为Gauss-Seidel 效应，即新的信息被更快地包含进更新公式里了。缺点：不能用数学表达式x(t1)f (x(t )一般描述：x(0)Xxi (t1)Ai (x1( 1i (t ),., xn ( ni(t ), t T,（ 7-1）xi (t), else其 中 ， t为时间索引或迭代索引， T表 示 xi 可 能 更 新 的 时 间 点 集 合 ，0ij (t )t , t0 。定 义 7.1.1（完全异步）T无 限 ， 且 如 果 tk 是 T的元素组成序列，则lim tj(tk ), j 。k定义 7.1.2

33、（部分异步） 存在常数 B ，满足：1） 对于每个 t0 和每个 i，集合 t, t1,.,tB 1 至少有一个元素属于T（在B步内至少更新一次） 。2） tBji(t)t ,i, j , tT3） ii(t )t ,i ,tT（自己节点的信息永远都是最新的）B 叫做异步测度 ，表征一个节点对来自其他节点的信息能允许的过时（outdated）程度。Jacobi 类型的同步迭代是B=1 的特殊情形。对异步算法的收敛情况，可能有以下三种：在完全异步情况下收敛；在完全异步时不收敛，但在部分异步时对每个B 值，都收敛，在部分异步情况下，如果B 足够小，能收敛；而 B 足够大时，可能不收敛。7.1.1完

34、全异步pp命题 7.1.1（充分条件） XX in，假设对每个 i 1,., p，存在一个属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) 的每个满足 x(k)X (k),k 的极限点，是f 的一个不动点；则，在完全异步，且 x(0) X (0)的情况下，由（ 7-1）得到的序列 x(k ) 的每个极限点都是 f 的一个不动点。对于零时延的异步迭代，当且仅当存在一个Lyapunov 类型（？）函数来验证，才能保证异步更新的收敛性。最大范数压缩

35、 ：| x | max | xi|i , xini ,| |i 是ni 上的一个范数， wi是一个正的标量。wi压缩特征 ：如果映射 A 满足，存在一个0,1) ，使得 | A(x) x* | x x* |, x X 成立，其中 x* 为 A 的一个不动点，则称A 具有 压缩特征 。给定一个向量 x(k)具有压缩特征(Contraction Property)的迭代映射举例：1） 线性迭代：A(x)M xb ，其中M 为 nn 的矩阵，且(| M|)1,| M|表示元素为M的元素的绝对值的矩阵，(| M|) 为| M|的频谱半径，即|M|的最大特征值。(| M |)1是异步收敛的充要条件。2）

36、 梯度迭代： A( x)xf ( x) ，f 为要优化（最小化）的目标函数，二阶连续可微，其Hess 矩阵满足有界和对角占优条件， 即|ij2 f ( x) |ii2 f (x), i ,xX ，其中j i为正常数。 (与 5.3.1 中的条件等价吗？前面是同步，这里是完全异步。)pn 为闭凸集，n 为3） 用于可变 (variational?) 不等式的影射算法：XXif : Xi 1给 定 函 数 ， 寻 求 向 量 x*X 满 足 f ( x* )T (x x* )0, x X 。 影 射 算 法 为 ：x(t 1) x( t )f ( x( t ) )，其中 为 X 上的正交影射。 如

37、果满足映射 xxf (x)为最大范数压缩映射 （如当 f 的雅各比矩阵满足对角占优条件），则完全异步可以保证收敛到 x*。4） 波形松弛方法单调映射 ：映射函数 A :nn 连续单调 （即有 xy 时，有 A( x)A( y) ），且有唯一的不动点 x* 。假设存在向量u,v ，满足 u A(u) A(v)v ，()x|Ak( )x Ak() ，则由命题X kuv可知完全异步收敛，异步算法的收敛速率至少和相应的同步算法一样好。部分异步( )( (), ( 1),., (1)B来描述算法在 t 时刻的状态。使用向量x tx tx tBXz t假设迭代映射连续，且不动点集X *X 非空，所有 z*

38、( x* , x* ,., x* ), x*X 组成的集合为 Z*。命题 7.1.2假设存在一个正整数t * ，和一个连续函数 d : X B0,) ，该函数具有以下特征：对每个不属于Z* 的初始点 z(0)，以及之后产生的序列（满足部分异步条件），有 d (z(t * )d ( z(0), d (z(1)d( z(0) 。则由部分异步迭代产生的序列 z(t) 的每个极限点都属于 Z* 。如果函数 d 的形式为 d ( z) inf* | zz*| ，且算法 A 为线性迭代形式，则 d( z(t) 以zZ几何级 (geometric progression) 的速度收敛到 0。8. 要解决的问

39、题(x, , ) 能否收敛到全局最优？1） 需要保证对偶间隙为0；2） 需要保证迭代算法存在不动点，且不动点为局部最优解；3） 然后来证明迭代算法收敛到不动点。算法有两种：x(t1)x* (t ),(t)1） (t1)A(t )，子梯度算法属于此类，此种方法属于Jacobi 算法，属于(t1)A(t )B=1 的异步迭代更新算法，其收敛性调研见7。x(t1)x* ( (t ), (t)2） (t1)A(t ),(t)，此种方法属于 Gauss-seidel 算法。（猜想，收敛速率应(t1)A(t 1), (t )该比 1）更快，因为最快地使用了最新的信息。因为【12】中没有异步迭代算法与G-S

40、算法的对应，从（7-1）看出，异步迭代中，在 t+1步中使用的是t 步储存的其他部分的值，从这个角度，异步迭代的定义好像是没有包括G-S 算法的。不过，如果假设每个部分更新完后，立即就更新了其他节点/处理器存储的它的值，则G-S 算法还是可以归为异步迭代算法的。 为了确定，还需要再调研。 ）参考文献【1】陈宝林，最优化理论与算法（第2 版），清华大学出版社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