A review after graduate design about the scenario and particular solution where convex method is called for communication system

在无线网络的通信系统中，无线网络的功耗与速率的最大化管理都会归结为一种范数约束问题。 范数函数一般都是凸函数，对于原本数据集是凸集的问题，这种问题往往可以转化为凸问题，因而凸优化的求解方法被广泛使用。

由于网络规模的急速扩张，解问题也在不断进步，现有的研究工作还没有找到一个统一的求解框架来解决这种凸优化问题，因此目前的手段往往是针对一个特定的问题使用一种框架，未来的一大趋势便是找到一种统一的求解工具，为大规模的凸优化的问题找到一种普适性的解法。

这些范数的目标问题往往具备直接或者间接的凸性，而依据目前的研究现状来看，由于凸问题的求解工具与算法发展已经比较成熟，现有的解决办法往往是通过将问题的模型直接表示成凸问题的形式或者是将问题间接地转化成凸问题，比如说

1.通过将问题直接解耦，使得问题分解为两个子的凸问题进而便于问题的求解

2.或者利用凸松弛的方法，将原始问题松弛到一个凸的问题而且保证问题的最优解不变（这种方法往往将问题的约束变形成为范数的平方，作为罚函数作为目标函数的余项）。

现有的凸优化求解工具包已经发展相对成熟，SDPT3，SeDuMi都是基于内点法的凸优化求解工具包，针对规模有限的问题能够方便的求得解析解，Mosek是一种商业的工具包，相比于前两种工具包具备更快的求解性能(但是)，SCS( (alternative direction method of multipler)ADMM，一种交替方向的乘子分裂法的求解器)这种算法牺牲了问题求解的精度，但是大大加速了针对大规模问题求解的速度，这对于未来网络的密集型结构的资源管理具备很好的适用性。

在毕业设计中，我阅读了石远明老师在大规模波束成形的相关文章，通读了一种大规模凸问题的求解框架：

1.矩阵填充技术(Matrix Stuffing):将变量进行复制，填充到矩阵的特定位置。将问题转化为标准的凸规划形式，将原始变量在锥空间的约束转化到松弛变量在锥空间的约束，并且约束在不同的锥空间的笛卡尔乘积中，可以进行并行性提取。

2.齐次自对偶嵌入(Homogeneous self-dual embedding)：将原始问题与对偶问题填充到矩阵中，形成自对偶问题，能够提取出原始问题不可行的数学证明(原来的证明方法都是通过指示性的信标，不具备数学严谨性)，然后通过转化成为可行性问题，在利用ADMM求解器进行迭代求解，数据的维度上升至100w的数量级，迭代需要几个小时完成，以次完成资源管理问题的求解。

这种方法改进的一个方向是如何计算锥的投影使得投影的速度更加迅速，由于算法提供了可并行计算的可能，因此使用多台计算机进行并行计算，计算机之间进行数据通信的方式应该可以得到很好的加速效果。 另外一些基于非凸的求解方法正在兴起，它们能够通过数学的方法证明得到的解是最优的，因此也可以利用在凸问题中，并且具备更好的求解速度与精度。