论文标题
多块nonconvex非平滑近端ADMM：kurdyka-łojasiewicz属性下的收敛和费率
Multi-Block Nonconvex Nonsmooth Proximal ADMM: Convergence and Rates under Kurdyka-Łojasiewicz Property
论文作者
论文摘要
在本文中，我们考虑了乘数（GADMM）算法的多块通用交替方向方法，用于最大程度地减少线性约束的可分离的非convex，并可能是非滑动优化问题。 GADMM通过在每个原始更新中加入近端项和双重更新中的过度删除参数来概括经典的ADMM。我们证明序列的任何极限点都是关键点。通过引入修改后的增强拉格朗日，我们表明，GADMM生成的序列是有界的，并且连续项方法的差异为零。在强大的{kł}属性下，我们表明gadmm序列具有有限的长度并收敛到固定点，并且我们驱动其收敛速率。给定适当的低症连续函数$ f：\ mathbb r^n \ to \ mathbb r $和一个关键点$ x^*\ in \ mathbb r^n $，{kł}属性断言，存在一个连续的凹面单调增加的函数$ x^*$ψ$ acts of $ x^*$ ITS，因此$ψ'（f（x）-f（x^*））\ cdot {\ rm dist}（0，\ partial f（x））\ ge 1 $。当$ψ（s）= s^{1-θ} $带有$θ\在[0,1] $中，这相当于$ | f（x）-f（x^*）|^θ{\ rm dist}（0，\ partial f（x））我们表明，如果$θ= 0 $，则GADMM生成的序列会收敛于有限数量的迭代。如果$θ\ in（0,1/2] $，则收敛速率为$ cq^{k} $其中$ c> 0 $，$ q \ in（0,1）$，而$ k \ in \ in \ mathbb n $是迭代号码。 $ r =（1-θ）/（2θ-1）$。
In this paper, we consider a multi-block generalized alternating direction method of multiplier (GADMM) algorithm for minimizing a linearly constrained separable nonconvex and possibly nonsmooth optimization problem. The GADMM generalizes the classical ADMM by including proximal terms in each primal updates and an over-relaxation parameter in the dual update. We prove that any limit point of the sequence is a critical point. By introducing a modified augmented Lagrangian we show that the sequence generated by the GADMM is bounded and the norm of the difference of consecutive terms approaches to zero. Under the powerful {KŁ} properties we show that the GADMM sequence has a finite length and converges to a stationary point, and we drive its convergence rate. Given a proper lower-semicontinuous function $f:\mathbb R^n\to\mathbb R$ and a critical point $x^*\in\mathbb R^n$, the {KŁ} property asserts that there exists a continuous concave monotonically increasing function $ψ$ such that around $x^*$ it holds $ψ'(f(x)-f(x^*))\cdot{\rm dist}(0,\partial f(x))\ge 1$ . When $ψ(s)=s^{1-θ}$ with $θ\in[0,1]$ this is equivalent to $|f(x)-f(x^*)|^θ{\rm dist}(0,\partial f(x))^{-1}$ to remain bounded around $x^*$. We show that if $θ=0$, the sequence generated by GADMM converges in a finite numbers of iterations. If $θ\in(0,1/2]$, then the rate of convergence is $cQ^{k}$ where $c>0$, $Q\in(0,1)$, and $k\in\mathbb N$ is the iteration number. If $θ\in(1/2,1]$ then the rate $\mathcal O(1/k^{r})$ where $r=(1-θ)/(2θ-1)$ will be achieved.
