在线咨询
中国工业与应用数学学会会刊
主管:中华人民共和国教育部
主办:西安交通大学
ISSN 1005-3085  CN 61-1269/O1

工程数学学报 ›› 2022, Vol. 39 ›› Issue (2): 237-264.doi: 10.3969/j.issn.1005-3085.2022.02.006

• • 上一篇    下一篇

一种超松弛原始对偶不动点算法及其应用

黄文丽1,   唐玉超1,   文  萌2   

  1. 1. 南昌大学数学系,南昌 330031
    2. 西安工程大学理学院,西安 710048
  • 出版日期:2022-04-15 发布日期:2022-06-15
  • 通讯作者: 唐玉超 E-mail: hhaaoo1331@163.com
  • 基金资助:
    国家自然科学基金 (12061045; 12001416; 11661056);南昌大学研究生创新专项基金 (CX2019056).

Over-relaxed Primal-dual Fixed Point Algorithm with Applications

HUANG Wenli1,    TANG Yuchao1,   WEN Meng2   

  1. 1. Department of Mathematics, Nanchang University, Nanchang 330031
    2. School of Science, Xi'an Polytechnic University, Xi'an 710048
  • Online:2022-04-15 Published:2022-06-15
  • Contact: Y. Tang. E-mail address: hhaaoo1331@163.com
  • Supported by:
    The National Natural Science Foundation of China (12061045; 12001416; 11661056); the Graduate Innovation Foundation of Nanchang University (CX2019056).

摘要:

近年来,关于两个凸函数和的优化问题受到极大关注,其中一凸函数可微且其梯度满足 Lipschitz 连续性,另一凸函数包含有界线性算子。提出一种超松弛原始对偶不动点算法求解这一类问题,相比于原始对偶不动点算法,所提算法扩展了松弛参数的选择范围。通过定义合适的范数,运用非扩张算子不动点理论,证明所提迭代算法的收敛性,并证明算法的遍历收敛率。在对目标函数一些强的条件下,证明算法具有全局线性收敛率。最后,为验证算法的有效性和优越性,将所提算法运用于求解全变分图像复原模型,数值结果表明,选择松弛参数大于 $1$ (即超松弛) 的原始对偶不动点算法比松弛参数小于 $1$ 时算法收敛更快。

关键词: 原始对偶方法, 不动点算法, 邻近算子, 超松弛

Abstract:

The optimization problem about the sum of two convex functions has been received much attention in recent years, in which one of them is differentiable with Lipschitz continuous gradient, and the other one contains a bounded linear operator. In this paper, an over-relaxed primal-dual fixed point algorithm is proposed to solve such problem. Compared with the original primal-dual fixed point algorithm, the proposed algorithm expands the selection range of relaxation parameters. By defining a suitable norm and using the fixed point theory of nonexpansive operators, we prove the convergence of the proposed iterative algorithm and together with the ergodic convergence rate. Under some strong conditions of the objective function, we prove that the algorithm has a global linear convergence rate. Finally, we apply the proposed algorithm to solve the total variation image restoration model to verify the validity of the proposed algorithm. Numerical results show that the primal-dual fixed point algorithm with the relaxation parameter larger than one (i.e., over-relaxation) converges faster than the relaxation parameter less than one.

Key words: primal-dual method, fixed point algorithm, proximity operator, over-relaxed

中图分类号: