凸优化——ADMM

发表于 更新于 分类于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 7 分钟

概念

罚函数法

将约束优化问题转化为无约束优化问题。

为保证解的逼近质量，无约束优化问题的目标函数为原约束优化问题的目标函数加上与约束函数有关的惩罚项，对于可行域外的点，惩罚项为正，即对该点进行惩罚；对于可行域内的点，惩罚项为0，即不做任何惩罚。

惩罚项会促使无约束优化问题的解落在可行域内。

罚函数的罚因子的初值不应过小，否则不可行点处的函数下降可能抵消了罚函数对约束违反的惩罚。

应用举例：

1. LASSO问题求解

求解LASSO问题的最终目标是为了解决基追踪（BP）问题：

是一个欠定方程组。BP问题是一个等式约束的非光滑优化问题，使用二次罚函数作用于等式约束，则有

令,则容易看出使用作为二次罚因子时，BP问题的罚函数子问题就等价于LASSO问题。

当趋于0时，LASSO问题的解收敛到BP问题的解。

增广拉格朗日函数法

增广拉格朗日函数法的每一步构造一个增广拉格朗日函数，而该函数的构造依赖于拉格朗日函数和约束的二次罚函数。

对于等式约束优化问题，增广拉格朗日函数定义为：

交替方向乘子法

将目标函数分成彼此分离的两块，但是变量被线性约束结合在一起。

对于如下的凸问题：

首先写出其增广拉格朗日函数：

其中是二次罚项的系数，为拉格朗日乘子。

求解过程：

其中为步长（update rate），通常取值为。

2-D DOA增广拉格朗日函数推导

考虑以下凸问题,

考虑几个约束项：

  1. 稀疏性：即同一距离单元中，散射体的数量有限。
  2. 紧密型：散射面是光滑连续的
  3. 分段常数：每个散射面的散射系数是一个恒定的常数
  4. 低能量：频谱能量有限
  5. 可行域有限

根据以上约束，对凸问题增加惩罚项。

则目标函数可以修改为：

逐项分析：

第一项为数据拟合项

第二项为惩罚项1，为投影矩阵

第三项和第四项为惩罚项2，其中与为逐像素的差分矩阵（分别沿x方向与y方向）

第五项为二次罚项，其保证了目标函数的严格凸性，以确保解的唯一性

，, 三者皆为惩罚项的系数。

考虑使用ADMM方法求解上述凸问题。首先，引入辅助变量​,则上述凸问题可以改写为

构造增广拉格朗日函数如下：

令 , , , 代入上式，可得

根据完全平方公式

该增广拉格朗日函数可以进一步化简为

使用ADMM求解上述增广拉格朗日函数,每次固定待更新变量外的所有变量，对变量进行更新，具体如下：

初始化：

迭代：