检索结果-内蒙古大学图书馆

A HYBRID ALTERNATING MINIMIZATION ALGORITHM FOR structured convex optimization PROBLEMS WITH APPLICATION IN POISSONIAN IMAGE PROCESSING

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT optimization 2023年第7期19卷 5078-5098页

作者： Chen, Hong-Mei Xu, Hai-Wen Yang, Jun-Feng Nanjing Univ Dept Math Nanjing 210093 Jiangsu Peoples R China Civil Aviat Flight Univ China Sch Sci Guanghan 618307 Sichuan Peoples R China

Motivated by applications in image processing, we consider a class of structured convex optimization problems in which the objective function is the sum of two component functions with favorable structures, and, furthermore, both of which are composed with linear operators. In particular, to recover images degraded by Poisson noise, the famous Kullback-Leibler divergence can be adopted in data fitting, in which case one component function is separable, strongly convex and easy to minimize. The other component function usually allows an easily computable proximal operator. We then propose, analyze and test a hybrid algorithm particularly tailored for the underlying model structures, which can be viewed as a combination of the famous alternating minimization algorithm of Tseng and the alternating direction method of multipliers. Under mild conditions, global iterate convergence as well as ergodic O(1/N) sublinear convergence rate results measured by the function value residual and constraint violation of a reformulated constrained optimization problem are established, where N denotes the iteration counter. The proposed algorithm is applied to fractional-order total variation regularized image denoising and deblurring problems, where the noise obeys Poisson distribution. Our experimental results demonstrate the effectiveness of the proposed algorithm.

关键词： structured convex optimization alternating minimization alternating direction method of multipliers Poisson noise fractional-order total variation denoising deblurring

来源：评论

学校读者我要写书评

暂无评论

A Modified Primal-Dual Algorithm for structured convex optimization with a Lipschitzian Term

引用

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA 2024年 1-21页

作者： Yin, Chao Xu, Hai-Wen Yang, Jun-Feng Hohai Univ Dept Math Nanjing 210024 Peoples R China Civil Aviat Flight Univ China Sch Sci Guanghan 618307 Sichuan Peoples R China Nanjing Univ Sch Math Nanjing 210008 Peoples R China

This paper focuses on solving structured convex optimization problems that consist of a smooth term with a Lipschitzian gradient, and two nonsmooth terms. One of the nonsmooth functions is composed with a linear operator, and both nonsmooth functions are proximal-friendly. To solve these problems, we propose a modified primal-dual algorithm, denoted by MPD3O, that combines ideas from the primal-dual splitting algorithm PD3O and the balanced augmented Lagrangian method. MPD3O does not require knowledge of the spectral norm of the linear operator and solves the primal and dual problems simultaneously without iteratively solving subproblems or linear system of equations. We establish global pointwise convergence using the Krasnoselskii-Mann theorem, as well as ergodic and nonergodic O(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(1/k)$$\end{document} sublinear convergence rate results, where k denotes the iteration number. Finally, we conduct numerical experiments on the constrained LASSO problem to demonstrate the efficiency of the proposed algorithm.

关键词： structured convex optimization Primal-dual algorithm Three operator splitting Balanced augmented Lagrangian method Constrained LASSO problem

来源：评论

学校读者我要写书评

暂无评论

TARGET DETECTON AND TRACKING VIA structured convex optimization

TARGET DETECTON AND TRACKING VIA STRUCTURED CONVEX OPTIMIZAT...

引用

IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Ge, Feng-Xiang Chen, Ying Li, Weichang Beijing Normal Univ Coll Informat Sci & Technol Beijing Peoples R China Aramco Serv Co Aramco Res Ctr Houston Houston TX 77096 USA

ISBN: (纸本)9781509041176

Moving target detection and tracking in reverberation environment is an important yet challenging problem in many applications such as speech, sonar, radar and seismic signal processing. Extending the early work of online subspace and sparse filtering [1], this paper presents an approach based on structured convex optimization. Exploiting potentially coherent structure of reverberation background, we represent the beamspace image data as the sum of a low-rank and a sparse matrix, where reverberation assumes low-rank structure and moving target signal is modeled as sparse. Detection and tracking is then formulated as a structured convex optimization problem, and solved via an accelerated proximal gradient (APG) algorithm. The performance of proposed algorithm is demonstrated using experimental results.

关键词： target detection and tracking reverberation low-rank sparse structured convex optimization accelerated proximal gradient

来源：评论

学校读者我要写书评

暂无评论

A Golden Ratio Primal-Dual Algorithm for structured convex optimization

引用

JOURNAL OF SCIENTIFIC COMPUTING 2021年第2期87卷 47-47页

作者： Chang, Xiaokai Yang, Junfeng Lanzhou Univ Technol Sch Sci Lanzhou Gansu Peoples R China Nanjing Univ Dept Math Nanjing Peoples R China

We design, analyze and test a golden ratio primal-dual algorithm (GRPDA) for solving structured convex optimization problem, where the objective function is the sum of two closed proper convex functions, one of which involves a composition with a linear transform. GRPDA preserves all the favorable features of the classical primal-dual algorithm (PDA), i.e., the primal and the dual variables are updated in a Gauss-Seidel manner, and the per iteration cost is dominated by the evaluation of the proximal point mappings of the two component functions and two matrix-vector multiplications. Compared with the classical PDA, which takes an extrapolation step, the novelty of GRPDA is that it is constructed based on a convex combination of essentially the whole iteration trajectory. We show that GRPDA converges within a broader range of parameters than the classical PDA, provided that the reciprocal of the convex combination parameter is bounded above by the golden ratio, which explains the name of the algorithm. An O(1/N) ergodic convergence rate result is also established based on the primal-dual gap function, where N denotes the number of iterations. When either the primal or the dual problem is strongly convex, an accelerated GRPDA is constructed to improve the ergodic convergence rate from O(1/N) to O(1/N-2). Moreover, we show for regularized least-squares and linear equality constrained problems that the reciprocal of the convex combination parameter can be extended from the golden ratio to 2 and meanwhile a relaxation step can be taken. Our preliminary numerical results on LASSO, nonnegative least-squares and minimax matrix game problems, with comparisons to some state-of-the-art relative algorithms, demonstrate the efficiency of the proposed algorithms.

关键词： structured convex optimization Saddle point problem Primal-dual algorithm Golden ratio Acceleration Convergence rate Fixed point iteration

来源：评论

学校读者我要写书评

暂无评论

Target detecton and tracking via structured convex optimization

Target detecton and tracking via structured convex optimizat...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Feng-Xiang Ge Ying Chen Weichang Li College of Information Science and Technology Beijing Normal University China Aramco Research Center - Houston Aramco Service Company United States of America

ISBN: (纸本)9781509041183

关键词： target detection and tracking reverberation low-rank sparse structured convex optimization accelerated proximal gradient Reverberation convex function tracking Sparse matrix moving target detection

来源：评论

学校读者我要写书评

暂无评论

New results on subgradient methods for strongly convex optimization problems with a unified analysis

引用

COMPUTATIONAL optimization AND APPLICATIONS 2016年第1期65卷 127-172页

作者： Ito, Masaru Tokyo Inst Technol Dept Math & Comp Sci Meguro Ku 2-12-1-W8-41 Oh Okayama Tokyo 1528552 Japan

We develop subgradient- and gradient-based methods for minimizing strongly convex functions under a notion which generalizes the standard Euclidean strong convexity. We propose a unifying framework for subgradient methods which yields two kinds of methods, namely, the proximal gradient method (PGM) and the conditional gradient method (CGM), unifying several existing methods. The unifying framework provides tools to analyze the convergence of PGMs and CGMs for non-smooth, (weakly) smooth, and further for structured problems such as the inexact oracle models. The proposed subgradient methods yield optimal PGMs for several classes of problems and yield optimal and nearly optimal CGMs for smooth and weakly smooth problems, respectively.

关键词： Non-smooth/smooth convex optimization structured convex optimization Subgradient/gradient-based proximal method Conditional gradient method Complexity theory Strongly convex functions Weakly smooth functions

来源：评论

学校读者我要写书评

暂无评论

Optimal subgradient methods: computational properties for large-scale linear inverse problems

引用

optimization AND ENGINEERING 2018年第4期19卷 815-844页

作者： Ahookhosh, Masoud Univ Vienna Fac Math Oskar Morgenstern Pl 1 A-1090 Vienna Austria

This paper studies the computational properties of the optimal subgradient algorithm (OSGA) for applications of linear inverse problems involving high-dimensional data. First, such convex problems are formulated as a class of convex problems with multi-term composite objective functions involving linear mappings. Next, an efficient procedure for computing the first-order oracle for such problems is provided and OSGA is equipped with some prox-functions such that the OSGA subproblem is solved in a closed form. Further, a comprehensive comparison among the most popular first-order methods is given. Then, several Nesterov-type optimal methods (originally proposed for smooth problems) are adapted to solve nonsmooth problems by simply passing a subgradient instead of the gradient, where the results of these subgradient methods are competitive and totally interesting for solving nonsmooth problems. Finally, numerical results with several inverse problems (deblurring with isotropic total variation, elastic net, and l(1)-minimization) show the efficiency of OSGA and the adapted Nesterov-type optimal methods for large-scale problems. For the deblurring problem, the efficiency measures of the improvement on the signl-to-noise ratio and the peak signal-to-noise ratio are used. The software package implementing OSGA is publicly available.

关键词： structured convex optimization Linear inverse problems Sparse nonsmooth optimization First-order information Subgradient methods Optimal complexity High-dimensional data

来源：评论

学校读者我要写书评

暂无评论

AN INEXACT ACCELERATED PROXIMAL GRADIENT METHOD FOR LARGE SCALE LINEARLY CONSTRAINED convex SDP

引用

SIAM JOURNAL ON optimization 2012年第3期22卷 1042-1064页

作者： Jiang, Kaifeng Sun, Defeng Toh, Kim-Chuan Natl Univ Singapore Dept Math Singapore 119076 Singapore Natl Univ Singapore Risk Management Inst Singapore 119076 Singapore Singapore MIT Alliance Singapore 117576 Singapore

The accelerated proximal gradient (APG) method, first proposed by Nesterov for minimizing smooth convex functions, later extended by Beck and Teboulle to composite convex objective functions, and studied in a unifying manner by Tseng, has proven to be highly efficient in solving some classes of large scale structured convex optimization (possibly nonsmooth) problems, including nuclear norm minimization problems in matrix completion and l(1) minimization problems in compressed sensing. The method has superior worst-case iteration complexity over the classical projected gradient method and usually has good practical performance on problems with appropriate structures. In this paper, we extend the APG method to the inexact setting, where the subproblem in each iteration is solved only approximately, and show that it enjoys the same worst-case iteration complexity as the exact counterpart if the subproblems are progressively solved to sufficient accuracy. We apply our inexact APG method to solve large scale convex quadratic semidefinite programming (QSDP) problems of the form min{1/2 < x, Q(x)> + < c, x > vertical bar A(x) = b, x >= 0}, where Q, A are given linear maps and b, c are given data. The subproblem in each iteration is solved by a semismooth Newton-CG (SSNCG) method with warm-start using the iterate from the previous iteration. Our APG-SSNCG method is demonstrated to be efficient for QSDP problems whose positive semidefinite linear maps Q are highly ill-conditioned or rank deficient.

关键词： inexact accelerated proximal gradient convex quadratic SDP semismooth Newton-CG structured convex optimization

来源：评论

学校读者我要写书评

暂无评论

GRPDA Revisited: Relaxed Condition and Connection to Chambolle-Pock's Primal-Dual Algorithm

引用

JOURNAL OF SCIENTIFIC COMPUTING 2022年第3期93卷 1-18页

作者： Chang, Xiaokai Yang, Junfeng Lanzhou Univ Technol Sch Sci Lanzhou Gansu Peoples R China Nanjing Univ Dept Math Nanjing Peoples R China

Recently, a golden ratio primal-dual algorithm (GRPDA) was proposed by Chang and Yang for solving structured convex optimization problems. It is a new adaptation of the classical Arrow-Hurwicz method by using a convex combination step, instead of the widely adopted extrapolation technique. The convex combination step is determined by a parameter psi, which, to guarantee global convergence, is restricted to (1, (1 + root 5)/2]. In this paper, by carrying out a refined analysis, we expand this region to (1, 1 + root 3). Moreover, we establish ergodic sublinear convergence rate results based on function value residual and constraint violation of an equivalently reformulated constrained optimization problem, rather than the previously adopted so-called primal-dual gap function that could vanish at nonstationary points. For linear equality constrained and regularized least-squares problems, we further show that GRPDA and Chambolle-Pock's primal-dual algorithm are equivalent provided that some parameters are chosen properly. Finally, experimental results on the LASSO and the basis pursuit problems are presented to demonstrate the performance of GRPDA with psi being chosen in the expanded region.

关键词： structured convex optimization Primal-dual algorithm Golden ratio convex combination Ergodic sublinear convergence rate

来源：评论

学校读者我要写书评

暂无评论

A family of subgradient-based methods for convex optimization problems in a unifying framework

引用

optimization METHODS & SOFTWARE 2016年第5期31卷 952-982页

作者： Ito, Masaru Fukuda, Mituhiro Nihon Univ Dept Math Coll Sci & Technol Chiyoda Ku 1-8-14 Kanda Surugadai Tokyo 1018308 Japan Tokyo Inst Technol Dept Math & Comp Sci Meguro Ku 2-12-1-W8-41 Oh Okayama Tokyo 1528552 Japan

We propose a new family of subgradient- and gradient-based methods which converges with optimal complexity for convex optimization problems whose feasible region is simple enough. This includes cases where the objective function is non-smooth, smooth, have composite/saddle structure, or are given by an inexact oracle model. We unified the way of constructing the subproblems which are necessary to be solved at each iteration of these methods. This permitted us to analyse the convergence of these methods in a unified way compared to previous results which required different approaches for each method/algorithm. Our contribution rely on two well-known methods in non-smooth convex optimization: the mirror-descent method (MDM) by Nemirovski-Yudin and the dual-averaging method by Nesterov. Therefore, our family of methods includes them and many other methods as particular cases. For instance, the proposed family of classical gradient methods and its accelerations generalize Devolder et al.'s, Nesterov's primal/dual gradient methods, and Tseng's accelerated proximal gradient methods. Also our family of methods can partially become special cases of other universal methods, too. As an additional contribution, the novel extended MDM removes the compactness assumption of the feasible region and the fixation of the total number of iterations which is required by the original MDM in order to attain the optimal complexity.

关键词： non-smooth smooth convex optimization structured convex optimization subgradient gradient-based proximal method mirror-descent method dual-averaging method complexity bounds 90C25 68Q25 49M37

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：