迭代收敛调研

《迭代收敛调研》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、973-认知无线网络项目认知无线网络行为分析与网络效能研究V1.0.0(2011-04-26)973项目；认知无线网络的全局性能优化；迭代收敛的全局最优性调研；973-认知无线网络项目简介本文档主要分两大部分：Ø第一部分，2,3节主要是问题是否存在全局最优解，以及局部最优解为全局最优解的条件，涉及到凸优化和对偶分解的基本理论。Ø第二部分，迭代算法能收敛到最优的条件。1.基本概念与定理1.1全局最优与局部最优（1）其中，X为的一个紧子集有界闭集即为紧集。【1】。定义1.1.1（全局最优解）如果存在一个点，使得成立，则称为问题（1）的全局最优解，为全局最优值。定义1.1.2（局部

2、最优解）如果存在的邻域W，使得对所有都有不等式成立，则为问题（1）的局部最优解。图1一维变量情形时，无约束优化问题的极值示例图【2】局部最优条件：定义1.1.3（可行方向）设集合是非零向量，若存在，使得973-认知无线网络项目，则称为集合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（

3、一阶充分条件）为S在处的所有非0可行方向。定义1.1.5（有效约束），即等号成立的不等式约束。定理1.1.5（二阶必要条件）如果，则局部最优=>（Hess矩阵半正定）。定理1.1.6（二阶充分条件）如果，则（Hess矩阵正定）=>局部最优。全局最优存在条件：1）f连续，且S为紧集；973-认知无线网络项目1）S为闭集，且f连续，且coercive?，即时。1.1凸优化（凸集、凸函数的定义与性质，此处省略）定理2.2.1凸规划的局部极小点就是全局极小点，且极小点的集合为凸集。如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点是唯一的。定义2.2.1（拟凸函数quasi

4、-convex）设S是中的一个非空凸集，f是定义在S上的实函数。若对任意的及每一个数，有，则称f为拟凸函数。（更直观的定义，满足为凸集【3】）定理2.2.2若是凸集S上的拟凸函数，是在S上的严格局部极小点，则也是在S上的全局极小点。定义2.2.2（伪凸函数pseudo-convex）设S是中的非空开凸集，是定义在S上的可微实函数，如果对任意两点，有蕴含，则称是伪凸函数。定理2.2.3若是开凸集S上的伪凸函数，且对某个有，则是在S上的全局极小点。图2凸、拟凸、伪凸关系图1.2对偶分解理论这里的对偶指拉格朗日对偶。对偶是约束优化中一个很重要的概念，它为很多约束分解方案（如可分离规

5、划），以及得到空间分解算法（如分支定界）的下界，提供了理论基础。973-认知无线网络项目1.1.1拉格朗日对偶【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条件，则满足强

6、对偶。定义2.3.6（KKT条件）假设目标函数和约束函数均可微，且满足强对偶，为原始问题和对偶问题的最优解对，则1）（2）在处的偏导为0；2）互补松弛：3）原问题和对偶问题的约束：。定理2.3.4对于凸问题，KKT条件是充要条件（即2.3.6的反向也成立）。1.1.2分解分解的基本思想【5】：基于目标函数和约束的特定结构，将问题分解为一个主问题和一系列更易求解的子问题。这些子问题可以独立求解，但是一般需要协调器（主问题）来保证局部决策能收敛到全局最优。对偶分解的基本思想是利用对偶函数的结构来提高计算效率或得到分布式算法。价格机制解释：将耦合的约束看作公共资源，将对偶变量看作是

7、公共资源的价格，对于供给方，如果资源紧张时，提高价格，在资源充裕的时候，降低价格；对于需求方，根据当前价格最大化自身净效益，来请求资源。这样就可以达到需求近似与供给对齐。973-认知无线网络项目1.1.1.1耦合的约束的处理举例：约束中变量是耦合的。1）引入对偶变量，将约束松弛，得到：这样就成了一个可分离问题。2）对于给定的，可以并行求解得到使、最小的、，记为、。3）使用影射子梯度算法，更新4）如果满足迭代停止条件，则终止；否则，转入2)。1.1.1.2耦合的目标的处理同一决策变量包含在不同目标函数里，