迭代收敛调研.doc

973-认知无线网络项目

MACROBUTTONMTEditEquationSection2EquationChapter1Section1SEQMTEqn\r\h\*MERGEFORMATSEQMTSec\r1\h\*MERGEFORMATSEQMTChap\r1\h\*MERGEFORMAT认知无线网络行为分析与网络效能研究
V1.0.0(2011-04-26)
973项目；
认知无线网络的全局性能优化；
迭代收敛的全局最优性调研；

简介
本文档主要分两大部分：
第一部分，2,3节主要是问题是否存在全局最优解，以及局部最优解为全局最优解的条件，涉及到凸优化和对偶分解的基本理论。
第二部分，迭代算法能收敛到最优的条件。
基本概念与定理
全局最优与局部最优
（1）
其中，X为的一个紧子集有界闭集即为紧集。
REF_Ref308102185\n\h\*MERGEFORMAT【1】。
定义1.1.1（全局最优解）如果存在一个点，使得成立，则称为问题（1）的全局最优解，为全局最优值。
定义1.1.2（局部最优解）如果存在的邻域W，使得对所有都有不等式成立，则为问题（1）的局部最优解。

图SEQ图\*ARABIC1一维变量情形时，无约束优化问题的极值示例图REF_Ref308102214\n\h\*MERGEFORMAT【2】
局部最优条件：
定义1.1.3（可行方向）设集合是非零向量，若存在，使得，则称为集合S在的可行方向。
定义1.1.4（下降方向）f(x)为定义在上的实函数，，d为非零向量，若存在，使得，则称d为f(x)在x处的下降方向。
推论1.1.1：如果，则d为f(x)在处的一个下降方向。
记

定理1.1.3（一阶必要条件）假设f在处可微，如果是（1）的局部最优解，则（即处的可行方向一定不是下降方向）
如果，则；
如果S为凸集，则。
定理1.1.4（一阶充分条件）为S在处的所有非0可行方向。
定义1.1.5（有效约束），即等号成立的不等式约束。
定理1.1.5（二阶必要条件）

如果，则局部最优=>（Hess矩阵半正定）。
定理1.1.6（二阶充分条件）

如果，则（Hess矩阵正定）=>局部最优。

全局最优存在条件：
f连续，且S为紧集；
S为闭集，且f连续，且coercive?，即时。
凸优化
（凸集、凸函数的定义与性质，此处省略）

定理2.2.1凸规划的局部极小点就是全局极小点，且极小点的集合为凸集。如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点是唯一的。

定义2.2.1（拟凸函数quasi-convex）设S是中的一个非空凸集，f是定义在S上的实函数。若对任意的及每一个数，有，则称f为拟凸函数。（更直观的定义，满足为凸集REF_Ref308102249\n\h\*MERGEFORMAT【3】）
定理2.2.2若是凸集S上的拟凸函数，是在S上的严格局部极小点，则也是在S上的全局极小点。

定义2.2.2（伪凸函数pseudo-convex）设S是中的非空开凸集，是定义在S上的可微实函数，如果对任意两点，有蕴含，则称是伪凸函数。
定理2.2.3若是开凸集S上的伪凸函数，且对某个有，则是在S上的全局极小点。

图SEQ图\*ARABIC2凸、拟凸、伪凸关系图
对偶分解理论
这里的对偶指拉格朗日对偶。
对偶是约束优化中一个很重要的概念，它为很多约束分解方案（如可分离规划），以及得到空间分解算法（如分支定界）的下界，提供了理论基础。
拉格朗日对偶REF_Ref308102323\n\h\*MERGEFORMAT【4】
定义2.3.1（原始问题）问题（1）。
定义2.3.2（拉格朗日函数）（2）
定义2.3.3（对偶函数）
定义2.3.4（对偶问题）
定理2.3.1对偶函数是和的凹函数，即对偶问题为凸问题。如果严格凸，则对偶函数连续可微。
假设原始问题的最优解为，最优值为，对偶问题的最优解为，最优值为
定理2.3.2（弱对偶）
定理2.3.3（强对偶），即对偶间隙为0。
定义2.3.5（slater条件）原始问题存在严格可行点。
定理2.3.3如果原问题为凸问题，且满足slater条件，则满足强对偶。
定义2.3.6（KKT条件）假设目标函数和约束函数均可微，且满足强对偶，为原始问题和对偶问题的最优解对，则
1）（2）在处的偏导为0；
2）互补松弛：
3）原问题和对偶问题的约束：。
定理2.3.4对于凸问题，KKT条件是充要条件（即2.3.6的反向也成立）。

分解
分解的基本思想REF_Ref308102447\n\h\*MERGEFORMAT【5】：基于目标函数和约束的特定结构，将问题分解为一个主问题