English

运筹学学报

• 运筹学 • 上一篇    下一篇

最小化三个凸函数之和的一个简单原始-对偶算法

王硕1 朱志斌1,*  张本鑫2   

  1. 1. 桂林电子科 技大学 数学与计算科学学院, 广西高校数据分析与计算重点实验室, 广西桂林 541004; 2. 桂林电子科技大学 电子工程与自动化学院, 广西自动检测技术与仪器重点实验室, 广西桂林 541004
  • 收稿日期:2018-01-08 出版日期:2018-06-15 发布日期:2018-06-15
  • 通讯作者: 朱志斌 E-mail: zhuzb@guet.edu.cn
  • 基金资助:

    国家自然科学基金(Nos. 11361018,11461015), 广西自然科学基金(No. 2014GXNSFFA118001), 广西密码学与信息安全重点实验室基金(No. GCIS201624), 广西自动检测技术与仪器重点实验室基金(No. YQ18107), 广西研究生教育创新计划项目(No. YCSW2018141)

A simple primal-dual algorithm for minimization of the sum of three convex functions

WANG Shuo1  ZHU Zhibin1,*  ZHANG Benxin2   

  1. 1. School of Mathematics and Computing Science, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guilin~541004, Guangxi, China; 2. School of Electronic Engineering and Automation, Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guilin University of Electronic Technology, Guilin~541004, Guangxi, China
  • Received:2018-01-08 Online:2018-06-15 Published:2018-06-15

PDF

271

摘要：

提出一个简单的原始-对偶算法求解三个凸函数之和的最小化问题, 其中目标函数包含有梯度李普希兹连续的光滑函数, 非光滑函数和含有复合算子的非光滑函数. 在新方法中, 对偶变量迭代使用预估-矫正的方案. 分析了算法的收敛性和收敛速率. 最后, 数值实验说明了算法的有效性.

关键词: 原始-对偶方法, 鞍点问题, 全变分, 图像重建

Abstract:

In this study, we propose a simple primal-dual algorithm for minimization of a sum of three convex separable functions, which are involved a smooth function with Lipschitz continuous gradient, a nonsmooth function and a linear composite nonsmooth function. A predictor-corrector scheme to the dual variable is used in our algorithm. Convergence and convergence rate are also discussed. In the end, numerical results illustrate the efficiency of this method.

Key words: primal-dual method, saddle-point problem, total variation, image reconstruction