一类带偶次惩罚范数的非凸函数及周期ADMM算法的收敛性分析

Convergence Analysis of a Class of Nonconvex Functions with Even-Powered Penalty Norms and the Periodic ADMM Algorithm

摘要: 在机器学习以及其它相关领域中，针对非凸函数的优化问题，目前存在的算法理论上对非凸函数的收敛和全局稳定性无法得到有效保证。本文提出将Lp范数(p为偶数)引入到非凸函数中，并在此基础上设计一种周期交替方向乘子(Periodic Alternating Direction Method of Multipliers, PADMM)的优化算法，用于此类非凸函数收敛性分析。我们证明在惩罚参数足够大的情况下，带偶次惩罚范数的非凸函数必收敛，并且收敛到全局最小值。此外，PADMM算法不对变量更新的先后顺序作特殊要求，这一特性大大增强了PADMM算法在处理各类非凸函数优化问题时的普适性。

Abstract: In machine learning and other related fields, for the optimization problem of non-convex functions, the existing algorithms cannot effectively guarantee the convergence and global stability of non-convex functions in theory. In this paper, the Lp norm (p is even) is introduced into the non-convex function, and on this basis, an optimization algorithm of Periodic Alternating Direction Method of Multipliers (PADMM) is designed for the convergence analysis of such non-convex functions. We prove that when the penalty parameter is large enough, the nonconvex function with even penalty norm will converge and converge to the global minimum. In addition, the PADMM algorithm does not impose special requirements on the order of variable updating, which greatly enhances the universality of the PADMM algorithm in dealing with various non-convex function optimization problems.

1. 引言

非凸函数优化问题在多个科学与工程领域都有着广泛的应用，[1]中给出非凸函数在机器学习、人工智能等领域的应用。[2]提出大部分非凸优化问题，由于具有局部极值点多、曲率变化复杂、数据维数庞大等特点，使得其求解难度尤为突出。这就要求研究者必须从非凸函数模型和求解算法方面设计出更为泛化且鲁棒的优化策略。

近年来，研究者提出了一系列用于分析非凸优化问题的算法。如[3]-[7]中的随机梯度下降及其变体、动量法、信赖域法、拟牛顿法、基于概率和迭代全局搜索技术等。这些算法均适应于处理大规模的非凸优化问题，在特定的条件下可提高局部收敛速度和准确性。然而这些算法普遍面临参数调整的挑战、可能会陷入局部最优、在处理大规模或复杂问题时收敛速度慢，及对问题特性敏感，导致实际性能与理论预期存在差距。[8]中交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)是在20世纪70年代初提出的用于解决非线性椭圆型偏微分方程的算法，此后ADMM逐渐被应用于更广泛的优化领域，尤其是那些具有可分离结构的非凸优化问题。ADMM算法相对于传统的原对偶型算法(如[9] [10]中的对偶上升算法或乘数法)收敛速度更快，也特别适合并行实现。然而在某些问题中ADMM的迭代解可能出现振荡，即在一组解附近来回波动，而非直接向最优解收敛，这可能需要额外的技术来稳定迭代过程，尽管有大量的研究文献将ADMM算法应用于非凸优化问题的实践案例，但对该算法在非凸优化情境下的理论理解和分析仍有较大的局限性。例如，对于大部分的收敛性分析只能针对某些特殊结构的非凸优化问题。[11]表明只有目标函数和约束条件满足一定的附加条件时，ADMM算法才会线性收敛。[12]研究发现对于多块可分离非凸优化问题和某些病态问题，原始ADMM算法可能会发散。因此大部分的研究为了保证非凸问题的收敛性，需要对非凸问题的目标函数和约束条件做出限制，这就可能导致对原始的优化问题产生破坏。[13]提出了多块ADMM算法，其将复杂的优化问题分解成多个相对独立的子问题，每个子问题所涉及的变量块较少，可进行单独求解多块ADMM算法。在大规模优化问题和分布式计算环境下有明显的优势。[14] [15]提出了全局优化ADMM算法，其在原始的ADMM算法的基础上引入新的算法设计和分析方法，如光滑技术、正则化技术等，确保非凸函数的全局收敛性。然而以往文献中的ADMM算法及其变体对非凸优化问题的收敛性分析非常有限，主要体现在：收敛性条件严格、全局最优解的不确定性、参数调优困难、理论分析缺失。[16] [17]提出在进行全局收敛性分析时，对于任何已知的方法，都需要对算法所产生的序列设定一些无法直接通过计算过程来检验的条件。

虽然对于非凸优化问题一般没有全局最优解的有效求法，[18]中提出可以通过增加适当的惩罚项改变搜索空间的几何特征，使得一些连续的非凸函数收敛到全局最优解，本文受[18]的启发在非凸函数的变体中添加了惩罚项。[19] [20]提出了Lasso和Ridge正则化方法，其在处理非凸函数时可以约束模型复杂度，生成稀疏解并且可提升优化过程的稳定性和有效性。[21]针对非凸优化问题提出了使用非凸惩罚项和范数进行优化的方法，使得非凸函数的收敛性较好，但是难以找到全局最优解，可能会陷入局部最优解。[22]提出了一种非凸鲁棒主成分分析法，其在特定条件下可能发现一个局部极小点，这个局部极小点比使用传统的凸优化方法找到的局部极小点表现得更好，更加的接近全局极小值点。然而这些方法一般不能保证全局最优性。

本文在[19] [20]的基础上提出了将Lp范数(p为偶数)引入到非凸函数中作为惩罚项，通过设计PADMM算法进行非凸优化函数的理论分析，通过理论分析证明我们提出的方法在惩罚参数足够大的情况下，非凸函数必定会收敛，并且收敛到全局极值点。

2. 周期交替方向乘子法

考虑以下非凸问题：

$\begin{array}{l}\underset{x}{\min }{h}_1\left(x\right)+h_2\left(x\right)+\cdots +h_K\left(x\right)+g\left(x\right)\\ \text{s}\text{.t}\text{.}x\in X\end{array}$ (1)

其中$h_i\left(x\right)$ 可以是光滑凸函数也可以是光滑非凸函数，$g\left(x\right)$ 是非光滑凸函数，X为闭凸集。

在实际问题分析中，(1)中的$h_i\left(x\right)$ 需要进行单独处理。为了便于分析，可在(1)的基础上引入一组新的变量$\left(x_1,x_2,\cdots ,x_K\right)$ ，则(1)可重新表述为(2)：

$\begin{array}{l}\underset{x_0}{\min }{h}_1\left(x_1\right)+h_2\left(x_2\right)+\cdots +h_K\left(x_K\right)+g\left(x_0\right)\\ \text{s}\text{.t}\text{.}{x}_k=x_0,\forall k=1,2,\cdots ,K\\ x_0\in X\end{array}$ (2)

(2)中所有子问题共享变量$x_0$ ，每个子问题负责优化自身的局部目标函数$h_K\left(x_K\right)$ ，所有子问题的解满足一致性条件$x_k=x_0$ 。通过每个局部函数的最优达到整体最优。在重新引入变量$\left(x_1,x_2,\cdots ,x_K\right)$ 后问题的维数增加到了K，(2)和(1)相比较增大了问题求解的迭代次数，但(2)确保了每个局部函数$h_K\left(x_K\right)$ 的独立性，即每个分布式节点可以独立地处理各自的变量$x_k$ 。

(2)的拉格朗日函数可由(3)给出：

$Ĺ\left(\left\{x_k\right\},x_0;\mu \right)={\displaystyle {\sum }_{k=1}^K{h}_k\left(x_k\right)}+g\left(x_0\right)+{\displaystyle {\sum }_{k=1}^K\langle {\mu }_k\cdot \left(x_k-x_0\right)\rangle }$ (3)

在(2)的基础上添加惩罚项${\displaystyle {\sum }_{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k-x_0\Vert }_p^p}$ ，(2)的增广拉格朗日函数由(4)给出：

$L\left(\left\{x_k\right\},x_0;\mu \right)=Ĺ\left(\left\{x_k\right\},x_0;\mu \right)+{\displaystyle {\sum }_{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k-x_0\Vert }_p^p}$ (4)

其中：$\mu =\left({\mu }_1,{\mu }_2,\cdots ,{\mu }_k\right)\in R^k$ 是拉格朗日乘子，${\xi }_k\in R$ 是惩罚参数，$p\in R$ 且p为偶数，${\Vert x\Vert }_p={\left({\displaystyle {\sum }_{i=1}^n{\left|x_i\right|}^p}\right)}^{\frac{1}{p}}$ 。

3. 非凸PADMM算法

为了使原始变量和对偶变量的更新次序有更大的选择性，本节提出一种灵活的PADMM算法。设$x_0,\cdots ,x_K$ 的索引为$k=0,\cdots ,K$ ，令$D^T=\left(0,1,2,\cdots ,K\right)$ 为第T次更新的变量集。

PADMM算法如下：

首先令$D^1=\left(0,1,2,\cdots ,K\right)$ ，$T=1,2,\cdots$ 。在初次更新时所有的变量均参与更新。

如果$T+1\ge 2$ ，任选$D^T\subseteq \left(0,1,2,\cdots ,K\right)$ 。在第二次之后的更新是从$x_0,\cdots ,x_K$ 中任选几个变量进行更新，即不必对全部变量进行更新，对变量的更新顺序也没有要求。

当$k=0$ 时，$x_0$ 的第$T+1$ 次迭代$x_0^{T+1}$ 计算方式由(5)给出：

$x_0^{T+1}=\arg {\min }_{x_0\in X}L\left(\left\{x_k^T\right\},x_0;{\mu }^T\right)$ (5)

否则：

$x_0^{T+1}=x_0^T$ (6)

当$k\ne 0$ 时，$x_k$ 的第$T+1$ 次迭代$x_k^{T+1}$ 计算方式由(7)给出：

$x_k^{T+1}=\arg {\min }_{x_k}{g}_k\left(x_k\right)+\langle {\mu }_k^T,x_k-x_0^{T+1}\rangle +\frac{{\xi }_k}{p}{\Vert x_k-x_0^{T+1}\Vert }_p^p$ (7)

第k个拉格朗日乘子${\mu }_k$ 第$T+1$ 次更新迭代在$x_0^{T+1}$ 和$x_k^{T+1}$ 的基础上得到，${\mu }_k^{T+1}$ 的计算方式由(8)给出：

${\mu }_k^{T+1}={\mu }_k^T+{\xi }_k{\left(\left|x_k^{T+1}-x_0^{T+1}\right|\right)}^{p-1}$ (8)

否则：

$x_k^{T+1}=x_k^{T+1}$ ，${\mu }_k^{T+1}={\mu }_k^T$ (9)

假定存在一个正周期M，我们规定${\displaystyle {\cup }_{i=1}^M{D}^{T+i}}=\left(0,1,2,\cdots ,K\right)$ ，即在一个周期内每个变量至少更新一次。

上述变量更新的迭代计算中，我们规定${\mu }_k^{T+1}={\mu }_k^T+{\xi }_k{\left(\left|x_k^{T+1}-x_0^{T+1}\right|\right)}^{p-1}$ ，其余变量都是通过极小化目标函数得到的。

4. 收敛性分析

为了对PADMM算法进行理论分析，我们给出下面假设。

假设1) $h_k\left(x\right)$ 满足利普希茨条件条件即存在$L_k$ 使得(10)成立。

$\Vert \nabla h_k\left(x_k\right)-\nabla h_k\left(y_k\right)\Vert \le L_k\Vert x_k-y_k\Vert$ (10)

假设2) $f\left(x\right)$ 在定义域中存在下界。

$f\left(x\right)>-\infty$ (11)

假设3) 对于所有的迭代次数k，(7)为模数为$m_k\left({\xi }_k\right)$ 的强凸函数，并且对于所有的迭代次数k有${\xi }_k{m}_k\left({\xi }_k\right)>p{L}_k^2$ 。

令$T_k$ 表示在更新迭代$T+1$ 之前，$x_k$ 最后一次被更新的迭代索引。即：

$T\left(k\right)=\max \left(a|a\le T,k\in D^a\right)$ ，$T\left(0\right)=\max \left(a|a\le T,0\in D^a\right)$ 。$k=1,2,\cdots ,K$

令：${\widehat{x}}_0^{T+1}=\arg {\min }_{x_0\in X}L\left(\left\{x_k^T\right\},x_0;{\mu }^T\right)$

${\widehat{x}}_k^{T+1}=\arg \underset{x_k}{\min }{g}_k\left(x_k\right)+\langle {\mu }_k^T,x_k-{\widehat{x}}_0^{T+1}\rangle +\frac{{\xi }_k}{p}{\Vert x_k-{\widehat{x}}_0^{T+1}\Vert }_p^p$

${\widehat{\mu }}_k^{T+1}={\mu }_k^T+{\xi }_k\left({\tilde{x}}_k^{T+1}-{\widehat{x}}_0^{T+1}\right)$

${\tilde{x}}_k^{T+1}=\arg \underset{x_k}{\min }{g}_k\left(x_k\right)+\langle {\mu }_k^T,x_k-x_0^T\rangle +\frac{{\xi }_k}{p}{\Vert x_k-x_0^T\Vert }_p^p$

${\tilde{\mu }}_k^{T+1}={\mu }_k^T+{\xi }_k\left({\tilde{x}}_k^{T+1}-x_0^T\right)$

下面证明对偶变量的连续变化量的大小上限是由原变量的变化量大小决定的。

定理1：在假设1)、2)、3)成立的情况下$\forall k=1,2,\cdots ,K$ 有以下的条件成立。

$L_k^2{\Vert x_k^{T+1}-x_k^T\Vert }^2\ge {\Vert {\mu }_k^{T+1}-{\mu }_k^T\Vert }^2$ (12)

$L_k^2{\Vert {\widehat{x}}_k^{T+1}-x_k^T\Vert }^2\ge {\Vert {\widehat{\mu }}_k^{T+1}-{\mu }_k^T\Vert }^2$ (13)

$L_k^2{\Vert {\tilde{x}}_k^{T+1}-x_k^T\Vert }^2\ge {\Vert {\tilde{\mu }}_k^{T+1}-{\mu }_k^T\Vert }^2$ (14)

证明：在此只对(12)展开证明，(13)、(14)同理可得。

$\forall k\in D^{T+1}$ 从$x_k$ 开始更新迭代，我们可以得到：

$\nabla h_k\left(x_k^{T+1}\right)+{\mu }_k^T+{\xi }_k{\left(\left|x_k^{T+1}-x_0^{T+1}\right|\right)}^{p-1}=0$

又因为${\mu }_k^{T+1}={\mu }_k^T+{\xi }_k{\left(x_k^{T+1}-x_0^{T+1}\right)}^{p-1}$ ，可得：

$\nabla h_k\left(x_k^{T+1}\right)=-{\mu }_k^{T+1}$

由假设1)可得：

$\Vert {\mu }_k^{T+1}-{\mu }_k^T\Vert =\Vert {\mu }_k^{T+1}-{\mu }_k^{T\left(k\right)}\Vert =\Vert \nabla h_k\left(x_k^{T+1}\right)-\nabla h_k\left(x_k^{T\left(k\right)}\right)\Vert$

由利普希茨连续条件可得：

$\Vert \nabla h_k\left(x_k^{T+1}\right)-\nabla h_k\left(x_k^{T\left(k\right)}\right)\Vert \le L_k\Vert x_k^{T+1}-x_k^{T\left(k\right)}\Vert =L_k\Vert x_k^{T+1}-x_k^T\Vert$

即：

$\Vert {\mu }_k^{T+1}-{\mu }_k^T\Vert \le L_k\Vert x_k^{T+1}-x_k^T\Vert$

证毕。

定理2：对于PADMM算法可以得到以下结论：

$\begin{array}{l}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^{T+1}\right)-L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\\ \le {\displaystyle \sum }_{k\in D^{T+1}}\left(\frac{L_k^2}{{\xi }_k}-\frac{m_k\left({\xi }_k\right)}{p}\right){\Vert x_k^{T+1}-x_k^T\Vert }^2-\frac{m}{p}\left(x_0^{T+1}-x_0^T\right)\end{array}$

证明：

$\begin{array}{l}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^{T+1}\right)-L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\\ ={\displaystyle \sum _{k=1}^K{h}_k\left(x_k^{T+1}\right)}+g\left(x_0^{T+1}\right)+{\displaystyle \sum _{k=1}^K\langle {\mu }^{T+1}\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }+{\displaystyle \sum _{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k^{T+1}-x_0^{T+1}\Vert }_p^p}\\ -\left({\displaystyle \sum _{k=1}^K{h}_k\left(x_k^T\right)}+g\left(x_0^T\right)\right)-\left({\displaystyle \sum _{k=1}^K\langle {\mu }^T\cdot \left(x_k^T-x_0^T\right)\rangle }+{\displaystyle \sum _{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k^T-x_0^T\Vert }_p^p}\right)\\ =\left({\displaystyle \sum _{k=1}^K{h}_k\left(x_k^{T+1}\right)}+g\left(x_0^{T+1}\right)+{\displaystyle \sum _{k=1}^K\langle {\mu }^{T+1}\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }\right)+\left({\displaystyle \sum _{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k^{T+1}-x_0^{T+1}\Vert }_p^p}\right)\\ -\left({\displaystyle \sum _{k=1}^K{h}_k\left(x_k^{T+1}\right)}+g\left(x_0^{T+1}\right)\right)-\left({\displaystyle \sum _{k=1}^K\langle {\mu }^T\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }+{\displaystyle \sum _{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k^{T+1}-x_0^{T+1}\Vert }_p^p}\right)\end{array}$

$\begin{array}{l}+\left({\displaystyle \sum _{k=1}^K{h}_k\left(x_k^{T+1}\right)}+g\left(x_0^{T+1}\right)+{\displaystyle \sum _{k=1}^K\langle {\mu }^{T+1}\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }\right)+\left({\displaystyle \sum _{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k^{T+1}-x_0^{T+1}\Vert }_p^p}\right)\\ -\left({\displaystyle \sum _{k=1}^K{h}_k\left(x_k^{T+1}\right)}+g\left(x_0^{T+1}\right)\right)-\left({\displaystyle \sum _{k=1}^K\langle {\mu }^{T+1}\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }+{\displaystyle \sum _{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k^{T+1}-x_0^{T+1}\Vert }_p^p}\right)\\ =\left(L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^{T+1}\right)-L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right)\right)\\ +\left(L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right)-L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\right)\end{array}$

因为：

$\begin{array}{l}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^{T+1}\right)-L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right)\\ ={\displaystyle \sum _{k=1}^K\langle {\mu }^{T+1}\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }-{\displaystyle \sum _{k=1}^K\langle {\mu }^T\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }\\ ={\displaystyle \sum _{k=1}^K\langle \left({\mu }^{T+1}-{\mu }^T\right)\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }\end{array}$

又因为：

$x_k^{T+1}-x_0^{T+1}={\left(\left|\frac{{\mu }^{T+1}-{\mu }^T}{{\xi }_k}\right|\right)}^{\frac{1}{p-1}}$

所以：

$L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^{T+1}\right)-L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right)={\displaystyle \sum }_{k\in D^{T+1}}\frac{1}{{\xi }_k^{p-1}}{\left(\left|{\mu }^{T+1}-{\mu }^T\right|\right)}^{\frac{p}{p-1}}$

又因为：

$\begin{array}{l}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right)-L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\\ =L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right)-L\left(\left\{x_k^T\right\},x_0^{T+1};{\mu }^T\right)+L\left(\left\{x_k^T\right\},x_0^{T+1};{\mu }^T\right)-L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\end{array}$

所以：

$\begin{array}{l}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right)-L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\\ \le {\displaystyle \sum }_{k=1}^K\left(\langle {\nabla }_{x_k}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right),\left(x_k^{T+1}-x_0^T\right)\rangle -\frac{m_k\left({\xi }_k\right)}{p}{\Vert x_k^{T+1}-x_k^T\Vert }_p^p\right)\\ +\langle {\tau }_{x_0}^{T+1},\left(x_0^{T+1}-x_0^T\right)\rangle -\frac{m}{p}{\Vert x_0^{T+1}-x_0^T\Vert }_p^p\end{array}$

令${\tau }_{x_0}^{T+1}\in {\partial }_{x_0}\left(L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\right)$ 是$x_0$ 的次导数，$\sigma =\{\begin{array}{l}1,0\in D^{T+1}\\ 0,0\notin D^{T+1}\end{array}$ ，$m={\displaystyle {\sum }_{k=1}^K{\xi }_k}$ 。

由凸函数的性质可得：

$\begin{array}{l}{\displaystyle \sum }_{k=1}^K\left(\langle {\nabla }_{x_k}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right),\left(x_k^{T+1}-x_0^T\right)\rangle -\frac{m_k\left({\xi }_k\right)}{p}{\Vert x_k^{T+1}-x_k^T\Vert }_p^p\right)+\langle {\tau }_{x_0}^{T+1},\left(x_0^{T+1}-x_0^T\right)\rangle -{\Vert x_0^{T+1}-x_0^T\Vert }_p^p\\ ={\displaystyle \sum }_{k\in D^{T+1}}(\left(\langle {\nabla }_{x_k}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^T\right),\left(x_k^{T+1}-x_0^T\right)\rangle -\frac{m_k\left({\xi }_k\right)}{p}{\Vert x_k^{T+1}-x_k^T\Vert }_p^p\right)\\ +\sigma \left(\langle {\tau }_{x_0}^{T+1},\left(x_0^{T+1}-x_0^T\right)\rangle \frac{m}{p}{\Vert x_0^{T+1}-x_0^T\Vert }_p^p\right))\\ \le -{\displaystyle \sum }_{k\in D^{T+1}}\frac{m_k\left({\xi }_k\right)}{p}{\Vert x_k^{T+1}-x_k^T\Vert }_p^p-\sigma \frac{m}{p}{\Vert x_0^{T+1}-x_0^T\Vert }_p^p\end{array}$

综上可得：

$\begin{array}{l}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^{T+1}\right)-L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\\ \le -{\displaystyle \sum }_{k\in D^{T+1}}\frac{m_k\left({\xi }_k\right)}{p}{\Vert x_k^{T+1}-x_k^T\Vert }^p-\sigma \frac{m}{p}{\Vert x_k^{T+1}-x_k^T\Vert }_p^p+{\displaystyle \sum }_{k\in D^{T+1}}\frac{1}{{\xi }_k}{\Vert x_0^{T+1}-x_0^T\Vert }_p^p\\ \le {\displaystyle \sum }_{k\in D^{T+1}}\left(\frac{L_k^2}{{\xi }_k}-\frac{m_k\left({\xi }_k\right)}{p}\right){\Vert x_k^{T+1}-x_k^T\Vert }_p^p-\sigma \frac{m}{p}{\Vert x_0^{T+1}-x_0^T\Vert }_p^p\end{array}$

证毕。

由定理2可知当$\frac{L_k^2}{{\xi }_k}-\frac{m_k\left({\xi }_k\right)}{P}\le 0$ ，即$p{L}_k^2\le {\xi }_k{m}_k\left({\xi }_k\right)$ 时，${\displaystyle {\sum }_{k\in D^{T+1}}\left(\frac{L_k^2}{{\xi }_k}-\frac{m_k\left({\xi }_k\right)}{p}\right){\Vert x_k^{T+1}-x_k^T\Vert }_p^p}-\sigma \frac{m}{p}{\Vert x_0^{T+1}-x_0^T\Vert }_p^p$ ，也就是说当选取较大的惩罚参数${\xi }_k$ 时，即可保证增广拉格朗日函数是递减的。

下面证明构造的增广拉格朗日函数是收敛的。

定理3：对于增广拉格朗日函数有以下的极限存在：

$\underset{T\to \infty }{\lim }L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\ge -\infty$

证明：

$\begin{array}{l}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^{T+1}\right)\\ ={\displaystyle \sum _{k=1}^K{h}_k\left(x_k^{T+1}\right)}+g\left(x_0^{T+1}\right)+{\displaystyle \sum _{k=1}^K\langle {\mu }_k^{T+1}\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle }+{\displaystyle \sum _{k=1}^K\frac{{\xi }_k}{p}{\Vert x_k^{T+1}-x_0^{T+1}\Vert }_p^p}\\ =g\left(x_0^{T+1}\right)+{\displaystyle \sum _{k=1}^K\left(h_k\left(x_k^{T+1}\right)+\langle {\mu }_k^{T+1}\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle +\frac{{\xi }_k}{p}{\Vert x_k^{T+1}-x_0^{T+1}\Vert }_p^p\right)}\end{array}$

又由定理1可知：

$\nabla h_k\left(x_k^{T+1}\right)=-{\mu }_k^{T+1}$

所以有：

$\begin{array}{l}g\left(x_0^{T+1}\right)+{\displaystyle \sum }_{k=1}^K\left(h_k\left(x_k^{T+1}\right)+\langle {\mu }_k^{T+1}\cdot \left(x_k^{T+1}-x_0^{T+1}\right)\rangle +\frac{{\xi }_k}{p}{\Vert x_k^{T+1}-x_0^{T+1}\Vert }_p^p\right)\\ =g\left(x_0^{T+1}\right)+{\displaystyle \sum }_{k=1}^K\left(h_k\left(x_k^{T+1}\right)+\langle \nabla h_k\left(x_k^{T+1}\right)\cdot \left(x_0^{T+1}-x_k^{T+1}\right)\rangle +\frac{{\xi }_k}{p}{\Vert x_k^{T+1}{x}_0^{T+1}\Vert }_p^p\right)\\ \ge g\left(x_0^{T+1}\right)+{\displaystyle \sum }_{k=1}^K{h}_k\left(x_0^{T+1}\right)=f\left(x_0^{T+1}\right)\end{array}$

由假设可知$f\left(x_0^{T+1}\right)\ge -\infty$ ，即${\lim }_{T\to \infty }L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\ge -\infty$ 。所以构造的增广拉格朗日函数是收敛的。

证毕。

下面证明算法收敛于平稳解集合。

定理4：根据PADMM算法可知，对于所有的$k=1,2,\cdots ,K$ 有：

${\lim }_{T\to \infty }\Vert x_k^{T+1}-x_0^{T+1}\Vert =0$ 成立。

证明：根据定理2有：

$\begin{array}{l}L\left(\left\{x_k^{T+1}\right\},x_0^{T+1};{\mu }^{T+1}\right)-L\left(\left\{x_k^T\right\},x_0^T;{\mu }^T\right)\\ \le {\displaystyle \sum _{k\in D^{T+i}}\left(\frac{L_k^2}{{\xi }_k}-\frac{m_k\left({\xi }_k\right)}{p}\right){\Vert x_k^{T+1}-x_k^T\Vert }_p^p}-\sigma \frac{m}{p}{\Vert x_0^{T+1}-x_0^T\Vert }_p^p\\ ={\displaystyle \sum _{i=1}^M{\displaystyle \sum _{k\in D^{T+i}}\left(\frac{L_k^2}{{\xi }_k}-\frac{m_k\left({\xi }_k\right)}{p}\right){\Vert x_k^{T+1}-x_k^T\Vert }_p^p}}-\frac{m}{p}\Vert x_0^{T+1}-x_0^T\Vert \end{array}$

如果$k\ne 0$ ，$k\notin D^{T+i}$ ，则有$x_k^{T+i}-x_k^{T+i-1}$ ，利用k在$\left[T,T+M\right]$ 至少更新一次以及定理3，对于$k=1,2,\cdots ,K$ 可得：

$\Vert x_0^{T+1}-x_0^{T\left(k\right)}\Vert \to 0,\Vert x_k^{T+1}-x_k^{T\left(k\right)}\Vert \to 0$

由定理1可知对于$k=1,2,\cdots ,K$ 有$\Vert {\mu }_k^{T+1}-{\mu }_k^{T\left(k\right)}\Vert \to 0$ ，根据PADMM算法的迭代步骤，当$\Vert {\mu }_k^{T+1}-{\mu }_k^{T\left(k\right)}\Vert \to 0$ 时，可得$\Vert x_k^{T+1}-x_0^{T+1}\Vert \to 0$ 。

证毕。

定理5：假设$\left(\left\{x_k^{*}\right\},x_0^{*},x_k^{*}\right)$ 是PADMM算法的全局极限点，那么有以下式子成立：

$\nabla h_k\left(x_k^{*}\right)+x_k^{*}=0$

$x_0^{*}\in \arg \underset{x\in X}{\min }g\left(x\right)+{\displaystyle \sum }_{k=1}^K\langle x_0^{*},x_k^{*}-x\rangle$

$x_k^{*}=x_0^{*}$

$\forall k=1,2,\cdots ,K$

证明：对于$k\in D^{T+1}$ ，$k\ne 0$ 有：

$\nabla h_k\left(x_k^{T+1}\right)+{\mu }_k^T+{\xi }_k\left(x_k^{T+1}-x_0^{T+1}\right)=0$

假设$0\in D^{T+1}$ ，令${\theta }^{T+1}\in \partial g\left(x_0^{T+1}\right)$ ，可得：

$\langle \left(x-x_0^{T+1}\right)\cdot \left({\theta }^{T+1}-{\displaystyle \sum }_{k=1}^K\left({\mu }_k^T-{\xi }_k\left(x_0^{T+1}-x_0^T\right)\right)\right)\rangle \ge 0$

因为：

$g\left(x\right)-g\left(x_0^{T+1}\right)={\theta }^{T+1}\left(x-x_0^{T+1}\right)$

所以：

$\begin{array}{l}\langle \left(x-x_0^{T+1}\right),\left({\theta }^{T+1}-{\displaystyle \sum }_{k=1}^K\left({\mu }_k^T-{\xi }_k\left(x_0^{T+1}-x_0^T\right)\right)\right)\rangle \\ =g\left(x\right)-g\left(x_0^{T+1}\right)+\langle \left(x-x_0^{T+1}\right),{\displaystyle \sum }_{k=1}^K\left({\xi }_k\left(x_0^{T+1}-x_0^T\right)-{\mu }_k^T\right)\rangle \end{array}$

根据PADMM算法迭代的规则，当$k\ne 0$ 时对于所有的T有：

$\nabla h_k\left(x_k^{\phi \left(k\right)}\right)+{\mu }_k^{\phi \left(k\right)}=0,\phi \left(k\right)\in \left[T,T+M\right]$

对于$\phi \left(0\right)\in \left[T,T+M\right]$ ，可得：

$g\left(x\right)-g\left(x_0^{\phi \left(0\right)}\right)+\langle \left(x-x_0^{\phi \left(0\right)}\right),{\displaystyle \sum }_{k=1}^K\left({\xi }_k\left(x_0^{\phi \left(0\right)}-x_0^{\phi \left(0\right)-1}\right)-{\mu }_k^{\phi \left(0\right)-1}\right)\rangle \ge 0$

根据定理4，可得：

$\Vert x_k^{\phi \left(k\right)}-x_k^{T+1}\Vert \to 0,\Vert x_0^{\phi \left(0\right)}-x_0^{T+1}\Vert \to 0$

$\Vert {\mu }_k^{T+1}-{\mu }_k^{\phi \left(k\right)}\Vert \to 0,\Vert {\mu }_k^{T+1}-{\mu }_k^{\phi \left(0\right)-1}\Vert \to 0$

又因为：

$\Vert x_k^{T+1}-x_k^T\Vert \to 0,x_0^{T+1}\to x_0^{*},x_k^{T+1}\to x_k^{*},{\mu }_k^{T+1}\to {\mu }_k^{*}$ ,

对$\nabla h_k\left(x_k^{\phi \left(k\right)}\right)+{\mu }_k^{\phi \left(k\right)}=0$ 求极限得：

$\nabla h_k\left(x_k^{*}\right)+x_k^{*}=0$

对$g\left(x\right)-g\left(x_0^{\phi \left(0\right)}\right)+\langle \left(x-x_0^{\phi \left(0\right)}\right)+{\displaystyle {\sum }_{k=1}^K\left({\xi }_k\left(x_0^{\phi \left(0\right)}-x_0^{\phi \left(0\right)-1}\right)-{\mu }_k^{\phi \left(0\right)-1}\right)}\rangle \ge 0$ 求极限可得：

$g\left(x\right)-g\left(x_0^{*}\right)+{\displaystyle \sum }_{k=1}^K\langle x-x_0^{*},-{\mu }_k^{*}\rangle \ge 0$

由于$\Vert {\mu }_k^{T+1}-{\mu }_k^T\Vert \to 0$ 对所有的k都成立，可得：

$x_k^{*}=x_0^{*}$

证毕。

5. PADMM算法实例应用

下面我们用PADMM算法求解以下非凸函数的最优值。

$\begin{array}{l}\underset{x}{\min }f\left(x\right)=\sin x+\sin 3x\\ \text{s}\text{.t}-2\pi \le x\le 2\pi \end{array}$

图1为函数$f\left(x\right)=\sin x+\sin 3x$ 的走势图，从图中可以看出$f\left(x\right)$ 是一个非凸函数，在定义域内函数有增有减。$f\left(x\right)$ 的最小值是−1.56。图2是PADMM算法的部分迭代过程图，可以看出迭代点沿着函数负梯度的方向下降，并且在极值点附近迭代步长逐渐减小。从图3中可以看出$f\left(x\right)$ 随着迭代次数的增加，函数值逐渐稳定到−1.56，对比图1和图3可以看出PADMM算法可有效的解决非凸函数优化问题。

Figure 1. Trend graph of $f\left(x\right)$

图1. $f\left(x\right)$ 走势图

Figure 2. Local iterative graph

图2. 局部迭代图

Figure 3. Iteration convergence diagram

图3. 迭代收敛图

6. 结论

本文提出了一类带偶次惩罚范数的非凸函数和PADMM算法，证明了在惩罚参数足够大的情况下，带偶次惩罚范数的非凸函数在PADMM算法的求解中是收敛的。并且非凸函数的解收敛于平稳集，在存在极小值的情况下带偶次惩罚范数的非凸函数会收敛到全局极小值。PADMM算法在求解非凸问题时不用考虑参数更新的顺序，这样可加速函数求解的收敛速度，同时更有普适性。

我们只考虑了偶次范数情况，对于一般的范数并没有进行理论分析，未来的一个研究方向是将偶次范数推广到整个实数空间中。