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

On the pointwise iteration-complexity of a dynamic regularized ADMM with over-relaxation stepsize

APPLIED MATHEMATICS AND COMPUTATION 2018年 336卷 315-325页

作者： Goncalves, M. L. N. Univ Fed Goias IME BR-74001970 Goiania Go Brazil

In this paper, we extend the improved pointwise iteration-complexity estimation of a dynamic regularized alternating direction method of multipliers (ADMM) for a new stepsize domain. In this complexity analysis, the stepsize parameter can be chosen in the interval (0,2) instead of interval (0, (1 +root 5)/2). We illustrate, by means of a numerical experiment, that the enlargement of this stepsize domain can lead to better performance of the method in some applications. Our complexity study is established by interpreting this ADMM variant as an instance of a hybrid proximal extragradient framework applied to a specific monotone inclusion problem. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Alternating direction method of multipliers Hybrid proximal extragradient framework pointwise iteration-complexity Convex programming

来源：评论

学校读者我要写书评

暂无评论

IMPROVED pointwise iteration-complexity OF A REGULARIZED ADMM AND OF A REGULARIZED NON-EUCLIDEAN HPE FRAMEWORK

引用

SIAM JOURNAL ON OPTIMIZATION 2017年第1期27卷 379-407页

作者： Goncalves, Max L. N. Melo, Jefferson G. Monteiro, Renato D. C. Univ Fed Goias Inst Math & Stat Campus 2Caixa Postal 131 BR-74001970 Goiania Go Brazil Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper describes a regularized variant of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex programs. It is shown that the pointwise iteration-complexity of the new variant is better than the corresponding one for the standard ADMM method and that, up to a logarithmic term, is identical to the ergodic iteration-complexity of the latter method. Our analysis is based on first presenting and establishing the pointwise iteration-complexity of a regularized non-Euclidean hybrid proximal extragradient framework whose error condition at each iteration includes both a relative error and a summable error. It is then shown that the new ADMM variant is a special instance of the latter framework where the sequence of summable errors is identically zero when the ADMM stepsize is less than one or a nontrivial sequence when the stepsize is in the interval [1, (1 + root 5)/2).

关键词： alternating direction method of multipliers hybrid proximal extragradient method non-Euclidean Bregman distances convex program pointwise iteration-complexity first-order methods inexact proximal point method regularization

来源：评论

学校读者我要写书评

暂无评论

An inexact version of the symmetric proximal ADMM for solving separable convex optimization

引用

NUMERICAL ALGORITHMS 2023年第1期94卷 1-28页

作者： Adona, Vando A. Goncalves, Max L. N. Univ Fed Goias IME Campus 2131 BR-74001970 Goiania GO Brazil

In this paper, we propose and analyze an inexact version of the symmetric proximal alternating direction method of multipliers (ADMM) for solving linearly constrained optimization problems. Basically, the method allows its first subproblem to be solved inexactly in such way that a relative approximate criterion is satisfied. In terms of root the iteration number k, we establish global O(1/ k) pointwise and O(1/k) ergodic convergence rates of the method for a domain of the acceleration parameters, which is consistent with the largest known one in the exact case. Since the symmetric proximal ADMM can be seen as a class of ADMM variants, the new algorithm as well as its convergence rates generalize, in particular, many others in the literature. Numerical experiments illustrating the practical advantages of the method are reported. To the best of our knowledge, this work is the first one to study an inexact version of the symmetric proximal ADMM.

关键词： Symmetric alternating direction method of multipliers Convex program Relative error criterion pointwise iteration-complexity Ergodic iteration-complexity

来源：评论

学校读者我要写书评

暂无评论

iteration-complexity analysis of a generalized alternating direction method of multipliers

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第2期73卷 331-348页

作者： Adona, V. A. Goncalves, M. L. N. Melo, J. G. Univ Fed Goias IME Campus 2Caixa Postal 131 BR-74001970 Goiania Go Brazil

This paper analyzes the iteration-complexity of a generalized alternating direction method of multipliers (G-ADMM) for solving separable linearly constrained convex optimization problems. This ADMM variant, first proposed by Bertsekas and Eckstein, introduces a relaxation parameter into the second ADMM subproblem in order to improve its computational performance. It is shown that, for a given tolerance epsilon>0, the G-ADMM with (0,2) provides, in at most O(1/epsilon 2) iterations, an approximate solution of the Lagrangian system associated to the optimization problem under consideration. It is further demonstrated that, in at most O(1/epsilon) iterations, an approximate solution of the Lagrangian system can be obtained by means of an ergodic sequence associated to a sequence generated by the G-ADMM with (0,2]. Our approach consists of interpreting the G-ADMM as an instance of a hybrid proximal extragradient framework with some special properties. Some preliminary numerical experiments are reported in order to confirm that the use of >1 can lead to a better numerical performance than =1 (which corresponds to the standard ADMM).

关键词： Generalized alternating direction method of multipliers Hybrid extragradient method Convex program pointwise iteration-complexity Ergodic iteration-complexity

来源：评论

学校读者我要写书评

暂无评论

A Partially Inexact Proximal Alternating Direction Method of Multipliers and Its iteration-complexity Analysis

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2019年第2期182卷 640-666页

作者： Adona, Vando A. Goncalves, Max L. N. Melo, Jefferson G. Univ Fed Goias IME BR-74001970 Goiania Go Brazil

This paper proposes a partially inexact proximal alternating direction method of multipliers for computing approximate solutions of a linearly constrained convex optimization problem. This method allows its first subproblem to be solved inexactly using a relative approximate criterion, whereas a proximal term is added to its second subproblem in order to simplify it. A stepsize parameter is included in the updating rule of the Lagrangian multiplier to improve its computational performance. pointwise and ergodic iteration-complexity bounds for the proposed method are established. To the best of our knowledge, this is the first time that complexity results for an inexact alternating direction method of multipliers with relative error criteria have been analyzed. Some preliminary numerical experiments are reported to illustrate the advantages of the new method.

关键词： Alternating direction method of multipliers Relative error criterion Hybrid extragradient method Convex program pointwise iteration-complexity Ergodic iteration-complexity

来源：评论

学校读者我要写书评

暂无评论

An inexact proximal generalized alternating direction method of multipliers

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2020年第3期76卷 621-647页

作者： Adona, V. A. Goncalves, M. L. N. Melo, J. G. Univ Fed Goias IME Campus 2Caixa Postal 131 BR-74001970 Goiania Go Brazil

This paper proposes and analyzes an inexact variant of the proximal generalized alternating direction method of multipliers (ADMM) for solving separable linearly constrained convex optimization problems. In this variant, the first subproblem is approximately solved using a relative error condition whereas the second one is assumed to be easy to solve. In many ADMM applications, one of the subproblems has a closed-form solution;for instance, l1 regularized convex composite optimization problems. The proposed method possesses iteration-complexity bounds similar to its exact version. More specifically, it is shown that, for a given tolerance rho>0, an approximate solution of the Lagrangian system associated to the problem under consideration is obtained in at most O(1/rho 2) (resp. O(1/rho) in the ergodic case) iterations. Numerical experiments are presented to illustrate the performance of the proposed scheme.

关键词： Generalized alternating direction method of multipliers Convex program Relative error criterion pointwise iteration-complexity Ergodic iteration-complexity

来源：评论

学校读者我要写书评

暂无评论

INEXACT VARIANTS OF THE ALTERNATING DIRECTION METHOD OF MULTIPLIERS AND THEIR iteration-complexity ANALYSES

INEXACT VARIANTS OF THE ALTERNATING DIRECTION METHOD OF MULT...

引用

作者： Vando Antonio Adona UNIVERSIDADE FEDERAL DE GOIAS

学位级别：博士

This thesis proposes and analyzes some variants of the alternating direction method of multipliers (ADMM) for solving separable linearly constrained convex optimization problems. This thesis is divided into three parts. First, we establish the iteration-complexity of a proximal generalized ADMM. This ADMM variant, proposed by Bertsekas and Eckstein, introduces a relaxation parameter α into the second ADMM subproblem in order to improve its computational performance. We show that, for a given tolerance ρ > 0, the proximal generalized ADMM with α ∈ (0, 2) provides, in at most O(1/ρ2) iterations, an approximate solution of the Lagrangian system associated to the optimization problem under consideration. It is further demonstrated that, in at most O(1/ρ) iterations, an approximate solution of the Lagrangian system can be obtained by means of an ergodic sequence associated to a sequence generated by the proximal generalized ADMM with α ∈ (0, 2]. Second, we propose and analyze an inexact variant of the aforementioned proximal generalized ADMM. In this variant, the first subproblem is approximately solved using a relative error condition whereas the second one is assumed to be easy to solve. It is important to mention that in many ADMM applications one of the subproblems has a closed-form solution; for instance, (cid:96)1-regularized convex composite optimization problems. We show that the proposed method possesses iteration-complexity bounds similar to its exact version. Third, we develop an inexact proximal ADMM whose first subproblem is inexactly solved using an approximate relative error criterion similar to the aforementioned inexact proximal generalized ADMM. pointwise and ergodic iteration-complexity bounds for the proposed method are established. Our approach consists of interpreting these ADMM variants as an instance of a hybrid proximal extragradient framework with some special properties. Finally, in order to show the applicability and advantage of the inexact A

关键词： Alternating direction method of multipliers Convex program Hybrid extragradient method Relative error criterion pointwise iteration-complexity Ergodic iteration-complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：