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

primal-dual BLOCK-PROXIMAL SPLITTING FOR A CLASS OF NON-CONVEX PROBLEMS

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2020年 52卷 509-552页

作者： Mazurenko, Stanislav Jauhiainen, Jyrki Valkonen, Tuomo Masaryk Univ Loschmidt Labs Brno Czech Republic Univ Eastern Finland Kuopio Finland Escuela Politec Nacl ModeMat Quito Ecuador Univ Helsinki Dept Math & Stat Helsinki Finland

We develop block structure-adapted primal-dual algorithms for non-convex non-smooth optimisation problems, whose objectives can be written as compositions G(x) + F(K(x)) of non-smooth block-separable convex functions G and F with a nonlinear Lipschitz-differentiable operator K. Our methods are refinements of the nonlinear primal-dual proximal splitting method for such problems without the block structure, which itself is based on the primal-dual proximal splitting method of Chambolle and Pock for convex problems. We propose individual step length parameters and acceleration rules for each of the primal and dual blocks of the problem. This allows them to convergence faster by adapting to the structure of the problem. For the squared distance of the iterates to a critical point, we show local O(1/N), O(1/N-2), and linear rates under varying conditions and choices of the step length parameters. Finally, we demonstrate the performance of the methods for the practical inverse problems of diffusion tensor imaging and electrical impedance tomography.

关键词： primal-dual algorithms convex optimization non-smooth optimization step length

来源：评论

学校读者我要写书评

暂无评论

Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization

引用

MATHEMATICAL PROGRAMMING 2019年第1-2期176卷 207-245页

作者： Hajinezhad, Davood Hong, Mingyi SAS Inst Cary NC USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA

In this paper, we propose a perturbed proximal primal-dual algorithm (PProx-PDA) for an important class of linearly constrained optimization problems, whose objective is the sum of smooth (possibly nonconvex) and convex (possibly nonsmooth) functions. This family of problems can be used to model many statistical and engineering applications, such as high-dimensional subspace estimation and the distributed machine learning. The proposed method is of the Uzawa type, in which a primal gradient descent step is performed followed by an (approximate) dual gradient ascent step. One distinctive feature of the proposed algorithm is that the primal and dual steps are both perturbed appropriately using past iterates so that a number of asymptotic convergence and rate of convergence results (to first-order stationary solutions) can be obtained. Finally, we conduct extensive numerical experiments to validate the effectiveness of the proposed algorithm.

关键词： Nonconvex optimization Nonsmooth optimization primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

WARPd: A Linearly Convergent First-Order primal-dual Algorithm for Inverse Problems with Approximate Sharpness Conditions*

引用

SIAM JOURNAL ON IMAGING SCIENCES 2022年第3期15卷 1539-1575页

作者： Colbrook, Matthew J. Ecole Normale Super Ctr Sci Donnees Paris France

Sharpness conditions directly control the recovery performance of restart schemes for first-order optimization methods without the need for restrictive assumptions such as strong convexity. However, they are challenging to apply in the presence of noise or approximate model classes (e.g., approximate sparsity). We provide a first-order method: weighted, accelerated, and restarted primal-dual (WARPd), based on primal-dual iterations and a novel restart-reweight scheme. Under a generic approximate sharpness condition, WARPd achieves stable linear convergence to the desired vector. Many problems of interest fit into this framework. For example, we analyze sparse recovery in com parallel to Bx parallel to l1 under constraints (l1-analysis problems for general B), and mixed regularization problems. We show how several quantities controlling recovery performance also provide explicit approximate sharpness constants. Numerical experiments show that WARPd compares favorably with specialized state-of-the-art methods and is ideally suited for solving large-scale problems. We also present a noise-blind variant based on a square-root LASSO decoder. Finally, we show how to unroll WARPd as neural networks. This approximation theory result provides lower bounds for stable and accurate neural networks for inverse problems and sheds light on architecture choices. Code and a gallery of examples are available online as a MATLAB package.

关键词： approximate sharpness error bounds accelerated methods primal-dual algorithms restart com-pressed sensing matrix completion total variation minimization image reconstruction neural networks

来源：评论

学校读者我要写书评

暂无评论

CONVERGENCE RATE ANALYSIS OF primal-dual SPLITTING SCHEMES

引用

SIAM JOURNAL ON OPTIMIZATION 2015年第3期25卷 1912-1943页

作者： Davis, Damek Univ Calif Los Angeles Dept Math Los Angeles CA 90025 USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14850 USA

primal-dual splitting schemes are a class of powerful algorithms that solve complicated monotone inclusions and convex optimization problems that are built from many simpler pieces. They decompose problems that are built from sums, linear compositions, and infimal convolutions of simple functions so that each simple term is processed individually via proximal mappings, gradient mappings, and multiplications by the linear maps. This leads to easily implementable and highly parallelizable or distributed algorithms, which often obtain nearly state-of-the-art performance. In this paper, we analyze a monotone inclusion problem that captures a large class of primal-dual splittings as a special case. We introduce a unifying scheme and use some abstract analysis of the algorithm to prove convergence rates of the proximal point algorithm, forward-backward splitting, Peaceman-Rachford splitting, and forward-backward-forward splitting applied to the model problem. Our ergodic convergence rates are deduced under variable metrics, stepsizes, and relaxation parameters. Our nonergodic convergence rates are the first shown in the literature. Finally, we apply our results to a large class of primal-dual algorithms that are a special case of our scheme and deduce their convergence rates.

关键词： primal-dual algorithms convergence rates proximal point algorithm forward-backward splitting forward-backward-forward splitting nonexpansive operator Douglas-Rachford splitting Peaceman-Rachford splitting averaged operator fixed-point algorithm

来源：评论

学校读者我要写书评

暂无评论

Practical Acceleration of the Condat-Vu Algorithm

引用

SIAM JOURNAL ON IMAGING SCIENCES 2024年第4期17卷 2076-2109页

作者： Driggs, Derek Ehrhardt, Matthias J. Schonlieb, Carola-Bibiane Tang, Junqi Univ Cambridge Dept Appl Math & Theoret Phys Cambridge CB3 0WA England Univ Bath Dept Math Sci Bath BA2 7AY England Univ Birmingham Sch Math Birmingham B15 2TT England

The Condat-Vu algorithm is a widely used primal-dual method for optimizing composite objectives of three functions. Several algorithms for optimizing composite objectives of two functions are special cases of Condat-Vu, including proximal gradient descent (PGD). It is well known that PGD exhibits suboptimal performance, and a simple adjustment to PGD can accelerate its convergence rate from O(1/T) to O(1/T-2) on convex objectives, and this accelerated rate is optimal. In this work, we show that a simple adjustment to the Condat-Vu algorithm allows it to recover accelerated PGD (APGD) as a special case, instead of PGD. We prove that this accelerated Condat-Vu algorithm achieves optimal convergence rates and significantly outperforms the traditional Condat-Vu algorithm in regimes where the Condat-Vu algorithm approximates the dynamics of PGD. We demonstrate the effectiveness of our approach in various applications in machine learning and computational imaging.

关键词： saddle-point problems primal-dual algorithms optimal methods convex optimization

来源：评论

学校读者我要写书评

暂无评论

A dual approach for optimal algorithms in distributed optimization over networks

引用

OPTIMIZATION METHODS & SOFTWARE 2021年第1期36卷 171-210页

作者： Uribe, Cesar A. Lee, Soomin Gasnikov, Alexander Nedic, Angelia MIT Lab Informat & Decis Syst 77 Massachusetts Ave Cambridge MA 02139 USA MIT Inst Data Syst & Soc 77 Massachusetts Ave Cambridge MA 02139 USA Yahoo Res Sunnyvale CA USA Moscow Inst Phys & Technol Dept Math Fdn Control Dolgoprudnyi Russia Inst Informat Transmiss Dolgoprudnyi Russia Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ USA

We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum of functions over in a network. We provide complexity bounds for four different cases, namely: each function is strongly convex and smooth, each function is either strongly convex or smooth, and when it is convex but neither strongly convex nor smooth. Our approach is based on the dual of an appropriately formulated primal problem, which includes a graph that models the communication restrictions. We propose distributed algorithms that achieve the same optimal rates as their centralized counterparts (up to constant and logarithmic factors), with an additional optimal cost related to the spectral properties of the network. Initially, we focus on functions for which we can explicitly minimize its Legendre-Fenchel conjugate, i.e. admissible or dual friendly functions. Then, we study distributed optimization algorithms for non-dual friendly functions, as well as a method to improve the dependency on the parameters of the functions involved. Numerical analysis of the proposed algorithms is also provided.

关键词： Distributed optimization optimal rates optimization over networks convex optimization primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating k-forest with resource augmentation: A primal-dual approach

引用

THEORETICAL COMPUTER SCIENCE 2019年 788卷 12-20页

作者： Angel, Eric Nguyen Kim Thang Singh, Shikha Univ Evry Val Essonne IBISC Evry France Wellesley Coll Wellesley MA 02181 USA

In this paper, we study the k-forest problem in the model of resource augmentation. In the k-forest problem, given an edge-weighted graph G (V, E), a parameter k, and a set of m demand pairs subset of V x V, the objective is to construct a minimum-cost subgraph that connects at least k demands. The problem is hard to approximate-the best-known approximation ratio is O(min{root vertical bar V vertical bar, root K}). Furthermore, k-forest is as hard to approximate as the notoriously-hard densest k-subgraph problem. While the k-forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are not connected. In particular, the objective of the k-forest problem can be viewed as to remove at most m - k demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the k-forest problem that, for every E > 0, removes at most m - k demands and has cost no more than O(1/epsilon(2)) times the cost of an optimal algorithm that removes at most (1 - epsilon)(m - k) demands. (C) 2018 Elsevier B.V. All rights reserved.

关键词： primal-dual algorithms Resource augmentation k-forest problem Approximation algorithms LP duality algorithms Optimization problems Prize-collecting generalized Steiner tree problem

来源：评论

学校读者我要写书评

暂无评论

Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient

引用

MATHEMATICAL PROGRAMMING 2024年 1-39页

作者： Latafat, Puya Themelis, Andreas Stella, Lorenzo Patrinos, Panagiotis Katholieke Univ Leuven Dept Elect Engn ESAT STADIUS Kasteelpk Arenberg 10 B-3001 Leuven Belgium Kyushu Univ Fac Informat Sci & Elect Engn ISEE 744 MotookaNishi Ku Fukuoka 8190395 Japan Amazon Web Serv Berlin Germany

Backtracking linesearch is the de facto approach for minimizing continuously differentiable functions with locally Lipschitz gradient. In recent years, it has been shown that in the convex setting it is possible to avoid linesearch altogether, and to allow the stepsize to adapt based on a local smoothness estimate without any backtracks or evaluations of the function value. In this work we propose an adaptive proximal gradient method, adaPGM, that uses novel estimates of the local smoothness modulus which leads to less conservative stepsize updates and that can additionally cope with nonsmooth terms. This idea is extended to the primal-dual setting where an adaptive three-term primal-dual algorithm, adaPDM, is proposed which can be viewed as an extension of the PDHG method. Moreover, in this setting the "essentially" fully adaptive variant adaPDM+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {adaPDM}<^>{\textsf {+}}$$\end{document} is proposed that avoids evaluating the linear operator norm by invoking a backtracking procedure, that, remarkably, does not require extra gradient evaluations. Numerical simulations demonstrate the effectiveness of the proposed algorithms compared to the state of the art.

关键词： Convex minimization Proximal gradient method primal-dual algorithms Locally Lipschitz gradient Linesearch-free adaptive stepsizes

来源：评论

学校读者我要写书评

暂无评论

FEASIBILITY ISSUES IN A primal dual INTERIOR-POINT METHOD FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1990年第2期49卷 145-162页

作者： LUSTIG, IJ 1. Program in Statistics and Operations Research Department of Civil Engineering and Operations Research School of Engineering and Applied Science Princeton University 08544 Princeton NJ USA

A new method for obtaining an initial feasible interior-point solution to a linear program is presented. This method avoids the use of a "big-M", and is shown to work well on a standard set of test problems. Conditions are developed for obtaining a near-optimal solution that is feasible for an associated problem, and details of the computational testing are presented. Other issues related to obtaining and maintaining accurate feasible solutions to linear programs with an interior-point method are discussed. These issues are important to consider when solving problems that have no primal or dual interior-point feasible solutions.

关键词： LINEAR PROGRAMMING INTERIOR-POINT METHODS primal-dual algorithms FEASIBILITY

来源：评论

学校读者我要写书评

暂无评论

A Weighted Difference of Anisotropic and Isotropic Total Variation for Relaxed Mumford--Shah Color and Multiphase Image Segmentation

引用

SIAM JOURNAL ON IMAGING SCIENCES 2021年第3期14卷 1078-1113页

作者： Bui, Kevin Park, Fredrick Lou, Yifei Xin, Jack Univ Calif Irvine Dept Math Irvine CA 92697 USA Whittier Coll Dept Math & Comp Sci Whittier CA 90602 USA Univ Texas Dallas Dept Math Sci Richardson TX 75080 USA

In a class of piecewise-constant image segmentation models, we propose to incorporate a weighted difference of anisotropic and isotropic total variation (AITV) to regularize the partition boundaries in an image. In particular, we replace the total variation regularization in the Chan--Vese segmentation model and a fuzzy region competition model by the proposed AITV. To deal with the nonconvex nature of AITV, we apply the difference-of-convex algorithm (DCA), in which the subproblems can be minimized by the primal-dual hybrid gradient method with linesearch. The convergence of the DCA scheme is analyzed. In addition, a generalization to color image segmentation is discussed. In the numerical experiments, we compare the proposed models with the classic convex approaches and the two-stage segmentation methods (smoothing and then thresholding) on various images, showing that our models are effective in image segmentation and robust with respect to impulsive noises.

关键词： (multiphase) image segmentation alternating minimization total variation difference-of-convex algorithm primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：