#### 期刊菜单

Inertial Proximal Alternating Minimization Algorithm for a Class of Nonconvex and Nonsmooth Problems
DOI: 10.12677/AAM.2019.87142, PDF, HTML, XML, 下载: 1,023  浏览: 4,951  国家自然科学基金支持

Abstract: In this paper, we propose an inertial proximal alternating minimization algorithm for a class of nonconvex and nonsmooth problems. We show the global convergence by constructing a new merit function H with guaranteed descent property. If H satisfies the Kurdyka-Lojasiewicz property, we determine the strongly convergence of the whole sequence.

1. 引言

$\underset{x,y}{\mathrm{min}}\text{\hspace{0.17em}}L\left(x,y\right)=f\left(x\right)+g\left(y\right)+R\left(x,y\right)$ (1)

$\left\{\begin{array}{l}{x}^{k+1}\in \mathrm{arg}\mathrm{min}\left\{L\left(x,{y}^{k}\right):x\in {ℝ}^{n}\right\},\\ {y}^{k\text{+}1}\in \mathrm{arg}\mathrm{min}\left\{L\left({x}^{k+1},y\right):y\in {ℝ}^{m}\right\}\end{array}$ (2)

$\left\{\begin{array}{l}{x}^{k+1}\in \text{arg}\underset{x}{\mathrm{min}}\left\{L\left(x,{y}^{k}\right)+\frac{{c}_{k}}{2}{‖x-{x}^{k}‖}^{2}\right\},\\ {y}^{k+1}\in \text{arg}\underset{y}{\mathrm{min}}\left\{L\left({x}^{k+1},y\right)+\frac{{d}_{k}}{2}{‖y-{y}^{k}‖}^{2}\right\}\end{array}$

2. 预备知识

$\eta \in \left(0,+\infty \right]$ ，记 ${\Phi }_{\eta }$ 为满足如下条件的凹可微函数 $\phi :\left[0,\eta \right)\to \left[0,+\infty \right)$ 的集合

(i) $\phi =0$

(ii) $\phi$$\left(0,\eta \right)$ 上连续；

(iii) ${\phi }^{\prime }\left(s\right)>0$$\forall s\in \left(0,\eta \right)$

(i) 设 $\stackrel{¯}{u}\in \text{dom}\text{\hspace{0.17em}}\partial \sigma :=\left\{u\in {ℝ}^{d}:\partial \sigma \left(u\right)\ne \varnothing \right\}$ ，若存在 $\eta \in \left(0,+\infty \right]$$\stackrel{¯}{u}$ 的一个邻域U及 $\phi \in {\Phi }_{\eta }$

${\phi }^{\prime }\left(\sigma \left(u\right)-\sigma \left(\stackrel{¯}{u}\right)\right)\text{dist}\left(0,\partial \sigma \left(u\right)\right)\ge 1$$\forall u\in U\cap \left[\sigma \left(\stackrel{¯}{u}\right)<\sigma \left(u\right)<\sigma \left(\stackrel{¯}{u}\right)+\eta \right]$

(ii) 若 $\sigma$$\text{dom}\text{\hspace{0.17em}}\partial \sigma$ 中的每一点都满足KL性质，则称 $\sigma$ 为KL函数。

${\phi }^{\prime }\left(\sigma \left(u\right)-\sigma \left(\stackrel{¯}{u}\right)\right)\text{dist}\left(0,\partial \sigma \left(u\right)\right)\ge 1$$\forall \left\{u\in {ℝ}^{d}:d\left(u,\Omega \right)<\epsilon \right\}\cap \left\{\sigma \left(\stackrel{¯}{u}\right)<\sigma \left(u\right)<\sigma \left(\stackrel{¯}{u}\right)+\eta \right\}$

$|h\left(y\right)-h\left(x\right)-〈\nabla h\left(x\right),y-x〉|\le \frac{h}{2}{‖y-x‖}^{2}$

3. 算法及假设条件

(ii) 对任意固定的y， ${\nabla }_{x}R\left(x,y\right)$ 关于x是Lipschitz连续的， ${L}_{1}\left(y\right)$ 为Lipschitz常数，即

$‖{\nabla }_{x}R\left({x}_{1},y\right)-{\nabla }_{x}R\left({x}_{2},y\right)‖\le {L}_{1}\left(y\right)‖{x}_{1}-{x}_{2}‖,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall {x}_{1},{x}_{2}\in {ℝ}^{n}$

(iii) 对任意固定的x， ${\nabla }_{y}R\left(x,y\right)$ 关于y是Lipschitz连续的，为Lipschitz常数，即

(iv) 存在，使得

(v)的有界子集上Lipschitz连续，即对任意有界集，使得，有

(3)

(4)

(5)

4. 收敛性分析

4.1. 充分下降性

(6)

(7)

(8)

(9)

4.2. 次微分的范数估计

(10)

。更进一步，存在常数，使得

4.3. 收敛结论

(i)是非空紧的连通集，且

(ii)

(iii) 当且仅当时，

(iv)

(v) H在上恒为常数。

(ii) 对任意，则存在一个子序列，有。由f的下半连续性，有

，有

(11)

，对(11)式中的取上极限，得。因此，。同样地，。根据R的连续性， 。故

(iii) 由引理5及的定义，结论得证。

(iv) 由引理4及引理5知。则()，再由的闭性，有，即

(v) 记，(h为常数)。对任意，则存在一个子序列，使得。再根据(iii)证明过程中所得。于是，，即H在上恒为常数。

(i)

(ii)序列收敛到L的一个稳定点

Case1. 存在一个正整数，使得。由注2知，则。于是，定理得证。

Case2. 对所有，有。根据极限的定义，由，则对给定，使得当时，有。由定理1(i)，即对给定，使得当时，有。于是，对给定，有

(i) 由引理1，则，有

(12)

。利用注2，结合(12)式，有

(13)

(ii) 由(i)可知为柯西序列，故收敛。由定理1，可知收敛到L的一个稳定点。

5. 数值试验

(14)

Table 1. Numerical result

Figure 1. The trend of objective function varies with iterations

NOTES

*通讯作者。

 [1] Bertsekas, D.P. and Tsitsiklis, J.N. (1989) Parallel and Distributed Computation: Numerical Methods (Vol. 23). Prentice Hall, Englewood Cliffs, NJ. [2] Auslender, A. (1992) Asymptotic Properties of the Fenchel Dual Functional and Applications to Decomposition Problems. Journal of Optimization Theory and Applications, 73, 427-449. https://doi.org/10.1007/BF00940050 [3] Alvarez, F. (2000) On the Minimizing Property of a Second Order Dis-sipative System in Hilbert Spaces. SIAM Journal on Control and Optimization, 38, 1102-1119. https://doi.org/10.1137/S0363012998335802 [4] Ochs, P., Chen, Y., Brox, T. and & Pock, T. (2014) iPiano: In-ertial Proximal Algorithm for Nonconvex Optimization. SIAM Journal on Imaging Sciences, 7, 1388-1419. https://doi.org/10.1137/130942954 [5] Ochs, P., Brox, T. and Pock, T. (2015) iPiasco: Inertial Proximal Algo-rithm for Strongly Convex Optimization. Journal of Mathematical Imaging and Vision, 53, 171-181. https://doi.org/10.1007/s10851-015-0565-0 [6] Boţ, R.I., Csetnek, E.R. and Hendrich, C. (2015) Inertial Doug-las-Rachford Splitting for Monotone Inclusion Problems. Applied Mathematics and Computation, 256, 472-487. https://doi.org/10.1016/j.amc.2015.01.017 [7] Bot, R.I. and Csetnek, E.R. (2014) An Inertial Alternating Direction Method of Multipliers. Mathematics, ArXiv preprint arXiv: 1404.4582. [8] Nesterov, Y. (2013) Introductory Lectures on Convex Optimization: A Basic Course (Vol. 87). Springer Science & Business Media, Berlin, Heidelberg. [9] Bolte, J., Sabach, S. and Teboulle, M. (2014) Proximal Alternating Linearized Minimization for Nonconvex and Nonsmooth Problems. Mathematical Programming, 146, 459-494. https://doi.org/10.1007/s10107-013-0701-9 [10] Xu, Z., Chang, X., Xu, F. and Zhang, H. (2012) L1/2 Regularization: A Thresholding Representation Theory and a Fast Solver. IEEE Transactions on Neural Networks and Learning Systems, 23, 1013-1027. https://doi.org/10.1109/TNNLS.2012.2197412