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

Regularized Jacobi-type ADMM-methods for a class of separable convex optimization problems in Hilbert spaces

COMPUTATIONAL optimization AND APPLICATIONS 2019年第3期73卷 755-790页

作者： Boergens, Eike Kanzow, Christian Univ Wurzburg Inst Math Campus Hubland NordEmil Fischer Str 30 D-97074 Wurzburg Germany

We consider a regularized version of a Jacobi-type alternating direction method of multipliers (ADMM) for the solution of a class of separable convex optimization problems in a Hilbert space. The analysis shows that this method is equivalent to the standard proximal-point method applied in a Hilbert space with a transformed scalar product. The method therefore inherits the known convergence results from the proximal-point method and allows suitable modifications to get a strongly convergent variant. Some additional properties are also shown by exploiting the particular structure of the ADMM-type solution method. Applications and numerical results are provided for the domain decomposition method and potential (generalized) Nash equilibrium problems in a Hilbert space setting.

关键词： Alternating direction method of multipliers Hilbert space Proximal-point method separable convex optimization Global convergence

来源：评论

学校读者我要写书评

暂无评论

A partially proximal S-ADMM for separable convex optimization with linear constraints

引用

APPLIED NUMERICAL MATHEMATICS 2021年 160卷 65-83页

作者： Shen, Yuan Zuo, Yannian Yu, Aolin Nanjing Univ Finance & Econ Sch Appl Math Nanjing 210023 Peoples R China

A classical approach to solving two-block separable convex optimization could be the symmetric alternating direction method of multipliers (S-ADMM). However, its convergence may not be guaranteed for a general multi-block case without additional assumptions. Bai et al. proposed a variant of S-ADMM entitled the generalized symmetric ADMM (GS-ADMM), in which the variables are regrouped into two groups firstly. The two groups of variables are updated in a Gauss-Seidel scheme, while the variables within each group are updated in a Jacobi scheme and the Lagrangian multipliers are updated two times. In order to derive its convergence property, the authors add a special proximal term to each subproblem. In this paper, inspired by the partial PPA block-wise ADMM (PPBADMM) [32] proposed by Shen et al., we propose a partially proximal S-ADMM (PPSADMM). In PPSADMM, the special proximal term is only added to the subproblems in the first group as PPBADMM. We perform an extension step on all variables with a fixed step size at the end of each iteration. Without stringent assumptions, we establish the global convergence result and the O(1/t) convergence rate in the ergodic sense for PPSADMM. Its numerical performance is justified on two types of problems. (C) 2020 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： separable convex optimization Multiple blocks Symmetric alternating direction method of multipliers Proximal point algorithm

来源：评论

学校读者我要写书评

暂无评论

Path-following gradient-based decomposition algorithms for separable convex optimization

引用

JOURNAL OF GLOBAL optimization 2014年第1期59卷 59-80页

作者： Quoc Tran Dinh Necoara, Ion Diehl, Moritz Katholieke Univ Leuven Optimizat Engn Ctr OPTEC Louvain Belgium Katholieke Univ Leuven Dept Elect Engn Louvain Belgium Univ Politehn Bucuresti Automat Control & Syst Engn Dept Bucharest 060042 Romania Vietnam Natl Univ Dept Math Mech Informat Hanoi Vietnam

A new decomposition optimization algorithm, called path-following gradient-based decomposition, is proposed to solve separable convex optimization problems. Unlike path-following Newton methods considered in the literature, this algorithm does not require any smoothness assumption on the objective function. This allows us to handle more general classes of problems arising in many real applications than in the path-following Newton methods. The new algorithm is a combination of three techniques, namely smoothing, Lagrangian decomposition and path-following gradient framework. The algorithm decomposes the original problem into smaller subproblems by using dual decomposition and smoothing via self-concordant barriers, updates the dual variables using a path-following gradient method and allows one to solve the subproblems in parallel. Moreover, compared to augmented Lagrangian approaches, our algorithmic parameters are updated automatically without any tuning strategy. We prove the global convergence of the new algorithm and analyze its convergence rate. Then, we modify the proposed algorithm by applying Nesterov's accelerating scheme to get a new variant which has a better convergence rate than the first algorithm. Finally, we present preliminary numerical tests that confirm the theoretical development.

关键词： Path-following gradient method Dual fast gradient algorithm separable convex optimization Smoothing technique Self-concordant barrier Parallel implementation

来源：评论

学校读者我要写书评

暂无评论

Inexact alternating direction methods of multipliers for separable convex optimization

引用

COMPUTATIONAL optimization AND APPLICATIONS 2019年第1期73卷 201-235页

作者： Hager, William W. Zhang, Hongchao Univ Florida Dept Math POB 118105 Gainesville FL 32611 USA Louisiana State Univ Dept Math Baton Rouge LA 70803 USA

Inexact alternating direction multiplier methods (ADMMs) are developed for solving general separable convex optimization problems with a linear constraint and with an objective that is the sum of smooth and nonsmooth terms. The approach involves linearized subproblems, a back substitution step, and either gradient or accelerated gradient techniques. Global convergence is established. The methods are particularly useful when the ADMM subproblems do not have closed form solution or when the solution of the subproblems is expensive. Numerical experiments based on image reconstruction problems show the effectiveness of the proposed methods.

关键词： separable convex optimization Alternating direction method of multipliers Multiple blocks Inexact ADMM Global convergence

来源：评论

学校读者我要写书评

暂无评论

Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems

引用

COMPUTATIONAL optimization AND APPLICATIONS 2013年第1期55卷 75-111页

作者： Quoc Tran Dinh Savorgnan, Carlo Diehl, Moritz Katholieke Univ Leuven Dept Elect Engn ESAT SCD B-3001 Heverlee Belgium Katholieke Univ Leuven Optimizat Engn Ctr OPTEC B-3001 Heverlee Belgium Vietnam Natl Univ Hanoi Vietnam

A new algorithm for solving large-scale convex optimization problems with a separable objective function is proposed. The basic idea is to combine three techniques: Lagrangian dual decomposition, excessive gap and smoothing. The main advantage of this algorithm is that it automatically and simultaneously updates the smoothness parameters which significantly improves its performance. The convergence of the algorithm is proved under weak conditions imposed on the original problem. The rate of convergence is , where k is the iteration counter. In the second part of the paper, the proposed algorithm is coupled with a dual scheme to construct a switching variant in a dual decomposition framework. We discuss implementation issues and make a theoretical comparison. Numerical examples confirm the theoretical results.

关键词： Excessive gap Smoothing technique Lagrangian decomposition Proximal mappings Large-scale problem separable convex optimization Distributed optimization

来源：评论

学校读者我要写书评

暂无评论

Polynomial methods for separable convex optimization in unimodular linear spaces with applications

引用

SIAM JOURNAL ON COMPUTING 1997年第4期26卷 1245-1275页

作者： Karzanov, AV McCormick, ST UNIV BRITISH COLUMBIA FAC COMMERCE & BUSINESS ADMVANCOUVERBC V6T 1Z2CANADA

We consider the problem of minimizing a separable convex objective function over the linear space given by a system Mt = a with M a totally unimodular matrix. In particular, this generalizes the usual minimum linear cost circulation and cocirculation problems in a network and the problems of determining the Euclidean distance from a point to the perfect bipartite matching polytope and the feasible flows polyhedron. We first show that the idea of minimum mean cycle canceling originally worked out for linear cost circulations by Goldberg and Tarjan [J. Assoc. Comput. Mach., 36 (1989), pp. 873-886.] and extended to some other problems [T. R. Ervolina and S. T. McCormick, Discrete Appl. Math, 46 (1993), pp. 133-165], [A. Frank and A. V. Karzanov, Technical Report RR 895-M, Laboratoire ARTEMIS IMAG, Universite Joseph Fourier, Grenoble, France, 1992], [T. Ibaraki, A. V. Karzanov, and H. Nagamochi, private communication, 1993], [M. Hadjiat, Technical Report, Groupe Intelligence Artificielle, Faculte des Sciences de Luminy, Marseille, France, 1994] can be generalized to give a combinatorial method with geometric convergence for our problem. We also generalize the computationally more efficient cancel-and-tighten method. We then consider objective functions that are piecewise linear, pure and piecewise quadratic, or piecewise mixed linear and quadratic, and we show how both methods can be implemented to find exact solutions in polynomial time (strongly polynomial in the piecewise linear case). These implementations are then further specialized for finding circulations and cocirculations in a network. We finish by showing how to extend our methods to find optimal integer solutions, to linear spaces of larger fractionality, and to the case when the objective functions are given by approximate oracles.

关键词： separable convex optimization unimodular linear spaces min mean canceling network flows

来源：评论

学校读者我要写书评

暂无评论

A golden ratio proximal alternating direction method of multipliers for separable convex optimization

引用

JOURNAL OF GLOBAL optimization 2023年第2-4期87卷 581-602页

作者： Chen, Hongmei Gu, Guoyong Yang, Junfeng Nanjing Univ Dept Math Nanjing 210093 Jiangsu Peoples R China

separable convex optimization problems often arise from large scale applications, and alternating direction method of multipliers (ADMM), due to its ability to utilize the separable structure of the objective function, has become an extremely popular approach for solving this class of problems. However, the convergence of the primal iterates generated by ADMM is not guaranteed and the ADMM subproblems can be computationally demanding. Proximal ADMM (PADMM), which introduces proximal terms to the ADMM subproblems, not only guarantees convergence of both the primal and the dual iterates but also is able to take advantage of the problem structures. In this paper, by adopting a convex combination technique we propose a new variant of the classical ADMM, which we call golden ratio proximal ADMM (GrpADMM) as the golden ratio appears to be a key parameter. GrpADMM preserves all the favorable features of PADMM, such as the ability to take full use of problem structures and global convergence under relaxed parameter condition. We show that GrpADMM shares the O(1/N) ergodic sublinear convergence rate, where N denotes the iteration counter. Furthermore, as long as one of the functions in the objective is strongly convex, the algorithm can be modified to achieve faster O(1/N-2) ergodic convergence. Finally, we demonstrate the performance of the proposed algorithms via preliminary numerical experiments.

关键词： separable convex optimization Linear equality constrained Alternating direction method of multipliers Proximal Golden ratio Ergodic convergence

来源：评论

学校读者我要写书评

暂无评论

Convergence rates for an inexact ADMM applied to separable convex optimization

引用

COMPUTATIONAL optimization AND APPLICATIONS 2020年第3期77卷 729-754页

作者： Hager, William W. Zhang, Hongchao Univ Florida Dept Math POB 118105 Gainesville FL 32611 USA Louisiana State Univ Dept Math Baton Rouge LA 70803 USA

Convergence rates are established for an inexact accelerated alternating direction method of multipliers (I-ADMM) for general separable convex optimization with a linear constraint. Both ergodic and non-ergodic iterates are analyzed. Relative to the iteration number k, the convergence rate is O(1/k) in a convex setting and O(1/k(2)) in a strongly convex setting. When an error bound condition holds, the algorithm is 2-step linearly convergent. The I-ADMM is designed so that the accuracy of the inexact iteration preserves the global convergence rates of the exact iteration, leading to better numerical performance in the test problems.

关键词： separable convex optimization Alternating direction method of multipliers ADMM Accelerated gradient method Inexact methods Global convergence Convergence rates

来源：评论

学校读者我要写书评

暂无评论

Interior-Point Lagrangian Decomposition Method for separable convex optimization

引用

JOURNAL OF optimization THEORY AND APPLICATIONS 2009年第3期143卷 567-588页

作者： Necoara, I. Suykens, J. A. K. Katholieke Univ Leuven Dept Elect Engn ESAT B-3001 Louvain Belgium Univ Politehn Bucuresti Automat Control & Syst Engn Dept Bucharest 060042 Romania

In this paper, we propose a distributed algorithm for solving large-scale separable convex problems using Lagrangian dual decomposition and the interior-point framework. By adding self-concordant barrier terms to the ordinary Lagrangian, we prove under mild assumptions that the corresponding family of augmented dual functions is self-concordant. This makes it possible to efficiently use the Newton method for tracing the central path. We show that the new algorithm is globally convergent and highly parallelizable and thus it is suitable for solving large-scale separable convex problems.

关键词： separable convex optimization Self-concordant functions Interior-point methods Augmented Lagrangian decomposition Parallel computations

来源：评论

学校读者我要写书评

暂无评论

AN INEXACT PERTURBED PATH-FOLLOWING METHOD FOR LAGRANGIAN DECOMPOSITION IN LARGE-SCALE separable convex optimization

引用

SIAM JOURNAL ON optimization 2013年第1期23卷 95-125页

作者： Quoc Tran Dinh Necoara, Ion Savorgnan, Carlo Diehl, Moritz Katholieke Univ Leuven Dept Elect Engn ESAT SCD B-3001 Louvain Belgium Katholieke Univ Leuven Optimizat Engn Ctr OPTEC B-3001 Louvain Belgium Univ Politehn Bucuresti Automat & Syst Engn Dept Bucharest 060042 Romania

This paper studies an inexact perturbed path-following algorithm in the framework of Lagrangian dual decomposition for solving large-scale separable convex programming problems. Unlike the exact versions considered in the literature, we propose solving the primal subproblems inexactly up to a given accuracy. This leads to an inexactness of the gradient vector and the Hessian matrix of the smoothed dual function. Then an inexact perturbed algorithm is applied to minimize the smoothed dual function. The algorithm consists of two phases, and both make use of the inexact derivative information of the smoothed dual problem. The convergence of the algorithm is analyzed, and the worst-case complexity is estimated. As a special case, an exact path-following decomposition algorithm is obtained and its worst-case complexity is given. Implementation details are discussed, and preliminary numerical results are reported.

关键词： smoothing technique self-concordant barrier Lagrangian decomposition inexact perturbed Newton-type method separable convex optimization parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：