Approximate ADMM for Non-Convex Optimization Problems

1) $\mathbb{R}$^n₁为n₁维欧氏空间，$\mathbb{R}$^n₂为n₂维欧氏空间.

2) $\mathbb{R}$^m×n₁是m×n₁维实矩阵空间，$\mathbb{R}$^m×n₂是m×n₂维实矩阵空间.

3) [·]₊是约束P上的投影算子，满足$[\boldsymbol{x}]_{+}=\operatorname{argmin}_{\bar{\boldsymbol{x}} \in P}\|\boldsymbol{x}-\bar{\boldsymbol{x}}\|$，特别的，[x]₊的第i个坐标分量满足

4) 令${\mathit{\pmb{ω}}}=(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}, {\mathit{\pmb{λ}}}), {\mathit{\pmb{ω}}}^t=\left(\boldsymbol{x}^t, \boldsymbol{y}^t, \boldsymbol{z}^t, {\mathit{\pmb{λ}}}^t\right), \widetilde{{\mathit{\pmb{ω}}}}=(\boldsymbol{x}, \boldsymbol{y}, \tilde{\boldsymbol{y}}, \boldsymbol{z}, {\mathit{\pmb{λ}}}), \widetilde{{\mathit{\pmb{ω}}}}^t=\left(\boldsymbol{x}^t, \boldsymbol{y}^t, \boldsymbol{y}^{t-1}, \boldsymbol{z}^t, {\mathit{\pmb{λ}}}^t\right)$.

原问题(1)的KKT条件如下

其中：λ^*，μ^*，ν^*，λ^*为乘子；μ_i^*和ν_i^*表示第i个分量. 令X^*×Y^*为满足KKT条件的所有(x^*，y^*)所构成的集合，称X^*×Y^*为原问题(1)的稳定解集，并令W={(x，y，λ)|(x，y)，λ为一对原始对偶解}.

(Ⅰ) $\boldsymbol{B B}^{\mathrm{T}} \succcurlyeq \mu_0 \boldsymbol{I}$，其中μ₀>0，即B是列满秩的.

(Ⅱ) f(x)是可微的，且满足Lipschitz可微条件

则可得，存在γ < 0，使得

(Ⅲ) g(y)是强凸的，强凸系数为m，即

(Ⅳ) g(y)是可微的，且满足Lipschitz可微条件

(Ⅴ) 存在常数$\tilde{\sigma}>0$，使得

(Ⅵ) 函数g(y)是强制的，即

接下来介绍近似的交替方向乘子法(P-ADMM)，问题(1)的增广拉格朗日函数为

其中常数α>0. 经典的ADMM算法处理以下两个子问题：对于固定的y，λ，在有界约束P上极小化L(x，y，λ)；对于固定的x，λ，极小化L(x，y，λ). 最后，利用原始残差Ax + By = b更新乘子λ. 由于有界约束的特殊性，在求解有界非凸子问题上采用梯度投影，且考虑到f(x)是非凸的，通过引入一个指数平均(或平滑)方案来生成一个额外的序列{z^t}，并在增广的拉格朗日函数中插入一个额外的以z^t为中心的二次近似项，在保证非凸子问题凸化的同时也能够使得原始迭代点x^t不会偏离稳定迭代点太多.

注1   该算法与传统的ADMM相比的优势在于，传统的ADMM处理有界约束上的非凸子问题是十分困难的，一方面是子问题的非凸性，另一方面则是有界约束的限制，而采用梯度投影、引入近似二次项则可以简化子问题的求解，很好地处理了非凸性和有界约束，使得算法更加简便，降低了运算成本.

注2   与文献[15]算法相比，P-ADMM是投影算法和ADMM的结合，主要用于解决有界约束上的可分离的非凸优化问题，而文献[15]中的算法主要用于解决有界约束上的单块非凸优化模型，是本文模型的一种特殊情况，因此P-ADMM的应用性更加广泛.

注3   与文献[16]中算法APGMM相比，P-ADMM在解决有界约束上的非凸子问题时不是直接采用的梯度投影，而是在原本的增广拉格朗日函数上引入了近似二次项，近似二次项的引入在保证非凸子问题凸化的同时也加快了算法收敛的速度(见数值实验).

为了更加方便分析P-ADMM的收敛性，首先给出一些关键的引理.

引理1   若假设(Ⅰ)，(Ⅳ)成立，那么可得

证   首先，通过假设(Ⅰ)可得

利用算法关于y在t+1步迭代式的一阶最优性条件可得

再通过算法关于λ在t+1步的迭代式可得$\nabla g$(y^t+1)=-〈 B，λ^t+1〉，同理可得

通过假设(Ⅳ)可知，函数g(x)是梯度Lipschitz连续的，则

结合(2)，(3)式可得$\left\|\boldsymbol{\lambda}^{t+1}-\boldsymbol{\lambda}^t\right\|^2 \leqslant \frac{L_2^2}{\mu_0}\left\|\boldsymbol{y}^{t+1}-\boldsymbol{y}^t\right\|^2$，故引理1成立.

引理2   若假设(Ⅱ)成立，且p+γ>0，令函数

则下列结论成立：

1) 函数K(x，y，z，λ)关于x是强凸的，且强凸系数为γ_k=p+γ，即

2) 函数K(x，y，z，λ)关于x是梯度Lipschitz连续的，且Lipschitz系数为L_k=p+γ+ασ₁²，即

其中σ₁为矩阵A的最大奇异值.

证   对函数K(x，y，z，λ)关于x求梯度，则

由假设(Ⅱ)知

同理可得

则引理2成立.

接下来，构造辅助函数

其中η>0，证明函数列$ M\left(\widetilde{\boldsymbol{\omega}}^t\right)$的单调递减性和有界性.

引理3   若假设(Ⅰ)，(Ⅲ)和(Ⅳ)成立，$\widetilde{\boldsymbol{\omega}}^t=\left(\boldsymbol{x}^t, \boldsymbol{y}^t, \boldsymbol{y}^{t-1}, \boldsymbol{z}^t, \boldsymbol{\lambda}^t\right)$为P-ADMM所生成的点列，那么对任意的t，若$2 c<\frac{1}{L_k}, \alpha>\max \left\{\frac{2 L_2^2}{\mu_0(m-2 \eta)}, \frac{1}{\mu_0 \tilde{\sigma}}\right\}>0$，有

注4   当矩阵B为对称矩阵，即B^T= B，且满足$2 c<\frac{1}{L_k}, \alpha>\max \left\{\eta+\sqrt{\frac{2 L_2^2}{\mu_0}+\eta^2}, \frac{1}{\mu_0 \tilde{\sigma}}\right\}>0$时，将假设(Ⅲ)中函数g(y)的强凸性弱化成凸性，仍然能够保证辅助函数列$M\left(\widetilde{\boldsymbol{\omega}}^t\right)$的单调递减性.

证   由算法关于x在t+1步的迭代式及投影定理，可得

则有

通过引理2的结论1)，利用函数K(x，y，z，λ)关于x的凸性，有

结合(4)，(5)式和引理2的结论2)以及$2 c<\frac{1}{L_k}$，可得

通过算法关于z在t+1步的迭代式得到

由假设(Ⅲ)可知

利用算法关于y在t+1步迭代式的一阶最优性条件得

再利用算法关于λ在t+2步的迭代式可得

结合(8)，(9)式可得

最后，通过算法关于λ在t+1步的迭代式可得

再由引理1可得

将(6)，(7)，(10)，(11)式相加，则有

故引理3成立.

引理4   若假设(Ⅰ)和(Ⅳ)成立，$\widetilde{\boldsymbol{\omega}}^t=\left(\boldsymbol{x}^t, \boldsymbol{y}^t, \boldsymbol{y}^{t-1}, \boldsymbol{z}^t, \boldsymbol{\lambda}^t\right)$，序列$\left\{\widetilde{\boldsymbol{\omega}}^t\right\}$由P-ADMM产生，若α>$\max \left\{\frac{2 L_2^2}{\mu_0(m-2 \eta)}, \frac{1}{\mu_0 \tilde{\sigma}}\right\}>0$，那么$\left\{\widetilde{\boldsymbol{\omega}}^t\right\}$是有界的，且函数列$\left\{M\left(\widetilde{\boldsymbol{\omega}}^t\right)\right\}$有下界.

证   首先，通过完全平方可得

再利用假设(Ⅰ)和(Ⅳ)，可得

因此

将(13)式代入(12)式可得

由引理3可知，函数列$M\left(\widetilde{\boldsymbol{\omega}}^t\right)$是单调递减的，则有

由于函数f(x)是有界闭集P上的可微函数，则函数f(x)是有界的，由于$\alpha>\max \left\{\frac{2 L_2^2}{\mu_0(m-2 \eta)}, \frac{1}{\mu_0 \tilde{\sigma}}\right\}>0$，结合(14)，(15)式可知，序列$\left\{\boldsymbol{x}^t\right\}, \left\{\left\|\nabla g\left(\boldsymbol{y}^t\right)\right\|\right\} \text { 和 }\left\{\left\|\boldsymbol{y}^t-\boldsymbol{y}^{t-1}\right\|\right\}$都是有界的，通过(13)式进一步可知函数列{λ^t}也是有界的. 由假设(Ⅵ)可知$\inf\limits_{\boldsymbol{y}} g(\boldsymbol{y})>-\infty$，则序列{y^t}是有界的. 因此，序列$\widetilde{\boldsymbol{\omega}}^t$是有界的. 由假设(Ⅵ)和(14)式有$M\left(\widetilde{\boldsymbol{\omega}}^t\right)>-\infty$. 综上所述，序列$\left\{M\left(\widetilde{\boldsymbol{\omega}}^t\right)\right\}$是有下界的.

将P-ADMM的迭代点$\boldsymbol{x}^t, \boldsymbol{y}^t, \boldsymbol{z}^t, \boldsymbol{\lambda}^t$记为$\hat{\boldsymbol{x}}, \hat{\boldsymbol{y}}, \hat{\boldsymbol{z}}, \hat{\boldsymbol{\lambda}}$，并将算法中x，y，z，λ的更新变量定义为$\hat{\boldsymbol{x}}^{+}, \hat{\boldsymbol{y}}^{+}, \hat{\boldsymbol{y}}^{+}, \hat{\boldsymbol{\lambda}}^{+}$，则

下面的引理说明，若算法停止，则可以找到一对原始对偶解.

引理5   若

那么$(\hat{\boldsymbol{x}}, \hat{\boldsymbol{y}}, \hat{\boldsymbol{\lambda}}) \in W$是原问题的一对解.

证   由(16)式以及$(\hat{\boldsymbol{x}}, \hat{\boldsymbol{y}}, \hat{\boldsymbol{z}}, \hat{\boldsymbol{\lambda}})=\left(\hat{\boldsymbol{x}}^{+}, \hat{\boldsymbol{y}}^{+}, \hat{\boldsymbol{z}}^{+}, \hat{\boldsymbol{\lambda}}^{+}\right)$，可得到以下等式

进一步简化得到

由于$\hat{\boldsymbol{x}} \in P$，则有如下等式成立

则$(\hat{\boldsymbol{x}}, \hat{\boldsymbol{y}}, \hat{\boldsymbol{\lambda}})$满足原问题(1)的KKT条件，即有$(\hat{\boldsymbol{x}}, \hat{\boldsymbol{y}}, \hat{\boldsymbol{\lambda}})$∈W为原问题的一对解.

推论1   若假设(Ⅰ)，(Ⅲ)和(Ⅳ)成立，对于任意ε>0，存在δ(ε)>0，且$(\hat{\boldsymbol{x}}, \hat{\boldsymbol{y}}, \hat{\boldsymbol{z}}, \hat{\boldsymbol{\lambda}}), \left(\hat{\boldsymbol{x}}^{+}, \hat{\boldsymbol{y}}^{+}, \left.\hat{\boldsymbol{z}}^{+}, \hat{\boldsymbol{\lambda}}^{+}\right)\right.$为P-ADMM产生的相邻两个迭代点，满足

我们可得

证   反证，假设存在序列$\left\{\hat{\boldsymbol{x}}^k\right\}, \left\{\hat{\boldsymbol{y}}^k\right\}, \left\{\hat{\boldsymbol{z}}^k\right\}, \left\{\hat{\boldsymbol{\lambda}}^k\right\}$满足对于某个ε₀>0和任意的δ>0，当

成立时，即

则有

通过引理4可知，由算法P-ADMM产生的迭代序列是有界的，则存在子列$\left\{\hat{\boldsymbol{x}}^{k_i}\right\}, \left\{\hat{\boldsymbol{y}}^{k_i}\right\}, \left\{\hat{\boldsymbol{z}}^{k_i}\right\}, \left\{\hat{\boldsymbol{\lambda}}^{k_i}\right\}$满足

进而可以得到

则有

由引理5可得$(\overline{\boldsymbol{x}}, \overline{\boldsymbol{y}}, \bar{\boldsymbol{\lambda}}) \in W$，即

则有

通过(17)式可得

则有

这与(18)式矛盾，则推论1成立.

定理1   若假设(Ⅰ)，(Ⅲ)和(Ⅳ)成立，序列{ ω^t}为P-ADMM所产生，则下列结论成立

1) $\lim\limits_{t \rightarrow \infty}\left(\left\|\boldsymbol{x}^t-\boldsymbol{x}^{t+1}\right\|+\left\|\boldsymbol{y}^t-\boldsymbol{y}^{t+1}\right\|+\left\|\boldsymbol{z}^t-\boldsymbol{z}^{t+1}\right\|+\left\|\boldsymbol{\lambda}^t-\boldsymbol{\lambda}^{t+1}\right\|\right)=0$

2) $\lim\limits_{t \rightarrow \infty}\left\|x^{t+1}-z^t\right\|=0$

3) $\lim\limits_{t \rightarrow \infty} \operatorname{dist}\left(z^t, X^*\right)=0, \lim\limits_{t \rightarrow \infty} \operatorname{dist}\left(\left(\boldsymbol{x}^t, \boldsymbol{y}^t\right), X^* \times Y^*\right)=0, \lim\limits_{t \rightarrow \infty} \operatorname{dist}\left(\left(\boldsymbol{x}^t, \boldsymbol{y}^t, \boldsymbol{\lambda}^t\right), W\right)=0$

证   1)由引理3可知

由引理4知函数列$\left\{M\left(\boldsymbol{\omega}^t\right)\right\}$有下界，则极数$\sum_{t=1}^{\infty} M\left(\boldsymbol{x}^t, \boldsymbol{y}^t, \boldsymbol{y}^{t-1}, \boldsymbol{z}^t, \boldsymbol{\lambda}^t\right)-M\left(\boldsymbol{x}^{t+1}, \boldsymbol{y}^{t+1}, \boldsymbol{y}^t, \boldsymbol{z}^{t+1}, \boldsymbol{\lambda}^{t+1}\right)$是收敛的，因此

进而可得到

通过定理1可知

则可得

结论1)成立.

2) 由于

结合z的第t+1次迭代式z^t+1= z^t+β(x^t+1- z^t)可得

则结论2)成立.

3) 由1)，2)两个结论可得

结合推论1有

则结论3)成立.

本文考虑用P-ADMM解决一类非凸的船舶分布式能源管理问题，在文献[17]中，考虑具有多个代理的船舶动力系统，且各代理根据各自的需求、供给相互协调. 首先将船舶能量管理问题以多智能体系统的形式重新制定，然后利用交替方向乘子法(ADMM)寻找模型中满足共识要求的最经济的工作点，本文考虑如下可分非凸光滑的能量成本函数

其中

F(x)为能量成本函数，x_i为共识变量，D为该问题的维度，问题(19)可等价转化成如下问题

问题(20)所对应的增广拉格朗日函数为

利用P-ADMM求解问题(20).

本文实验在配置英特尔Core i5-6200U 2.30 GHz处理器、4.00 GB内存和Windows 10(64位)操作系统的计算机上进行，其中t为迭代步数. 算法的参数设置如下：p=8 000，$c=\frac{1}{5000}$，D=50，α=100，y⁰，z⁰，λ⁰都是维数50的零向量，x⁰∈$\mathbb{R}$⁵⁰为均匀分布在[-5.12，5.12]上的向量，终止条件

图 1展示了在P-ADMM算法下船舶电力系统能量成本的走势情况，其中G(x^t)+H(y^t)为成本函数，t为迭代步. 通过图 1可以看出，能量成本值从开始的下降逐渐趋于稳定，最后达到收敛. 同时，观察发现选择较大的β，会使收敛速度加快，即算法可以在更小的迭代步数下完成收敛，减少了算法迭代的次数.

图 2和图 3分别展示了在参数β=0.2的条件下‖ x^t- y^t‖和‖ x^t+1- z^t‖的下降情况，进一步验证了算法P-ADMM解决问题(20)的可行性. 从图 2，3中可知，‖ x^t- y^t‖和‖ x^t+1- z^t‖一开始下降得非常快，再逐渐趋于平稳并达到收敛.

图 4是基于问题(20)将P-ADMM和APGMM^[17]在参数β=0.8的条件下进行了比较. 从图 4中可以看到算法P-ADMM相对于算法APGMM在下降趋势和收敛步数上都具有较大的优势. APGMM算法开始迭代是波动的、不稳定的. 考虑到目标函数的非凸性，我们在运行算法时，选取α=100，α=1 000两种情况进行比较. 由图 4可知算法P-ADMM的下降速度快，能够在更小的迭代步达到收敛.

本文在梯度投影算法和ADMM基础上，针对可分结构的非凸优化问题，提出了一种新的P-ADMM，该算法具有良好的收敛性，简化了子问题的求解，降低了运算成本，且近似二次项的引入在保证算法的收敛性的同时也能够提升算法的收敛速度. 该算法在一类非凸的船舶能源管理问题中也得到了有效应用. P-ADMM在梯度投影时，选取的步长是满足条件的定值，但如何优化梯度投影的步长以提高算法速率需要进一步的研究.