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

iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

MATHEMATICAL PROGRAMMING 2021年第1-2期185卷 199-244页

作者： Xu, Yangyang Rensselaer Polytech Inst Dept Math Sci Troy NY 12180 USA

Augmented Lagrangian method (ALM) has been popularly used for solving constrained optimization problems. Practically, subproblems for updating primal variables in the framework of ALM usually can only be solved inexactly. The convergence and local convergence speed of ALM have been extensively studied. However, the global convergence rate of the inexact ALMis still open for problems with nonlinear inequality constraints. In this paper, we work on general convex programs with both equality and inequality constraints. For these problems, we establish the global convergence rate of the inexactALMand estimate its iteration complexity in terms of the number of gradient evaluations to produce a primal and/or primal-dual solution with a specified accuracy. We first establish an ergodic convergence rate result of the inexact ALM that uses constant penalty parameters or geometrically increasing penalty parameters. Based on the convergence rate result, we then apply Nesterov's optimal first-order method on each primal subproblem and estimate the iteration complexity of the inexact ALM. We show that if the objective is convex, then O( e-1) gradient evaluations are sufficient to guarantee a primal e-solution in terms of both primal objective and feasibility violation. If the objective is strongly convex, the result can be improved to O(e- 1 2 | log e|). To produce a primal-dual e-solution, more gradient evaluations are needed for convex case, and the number is O(e - 4 3), while for strongly convex case, the number is still O( e - 1 2 | log e|). Finally, we establish a nonergodic convergence rate result of the inexact ALM that uses geometrically increasing penalty parameters. This result is established only for the primal problem. We show that the nonergodic iteration complexity result is in the same order as that for the ergodic result. Numerical experiments on quadratically constrained quadratic programming are conducted to compare the performance of the inexact ALM with diffe

关键词： Augmented Lagrangian method (ALM) Nonlinearly constrained problem First-order method Global convergence rate iteration complexity

来源：评论

学校读者我要写书评

暂无评论

iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

引用

MATHEMATICAL PROGRAMMING 2014年第1-2期144卷 1-38页

作者： Richtarik, Peter Takac, Martin Univ Edinburgh Sch Math Edinburgh EH9 3JZ Midlothian Scotland

In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an -accurate solution with probability at least in at most iterations, where is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341-362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving first true iteration complexity bounds. For strongly convex functions the method converges linearly. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale -regularized least squares problems with a billion variables.

关键词： Block coordinate descent Huge-scale optimization Composite minimization iteration complexity Convex optimization LASSO Sparse regression Gradient descent Coordinate relaxation Gauss-Seidel method

来源：评论

学校读者我要写书评

暂无评论

iteration complexity of a Proximal Augmented Lagrangian Method for Solving Nonconvex Composite Optimization Problems with Nonlinear Convex Constraints

引用

MATHEMATICS OF OPERATIONS RESEARCH 2023年第2期48卷 1066-1094页

作者： Kong, Weiwei Melo, Jefferson G. Monteiro, Renato D. C. Oak Ridge Natl Lab Comp Sci & Math Div Oak Ridge TN 37830 USA Univ Fed Goias Inst Matemat & Estat BR-74001970 Goiania Go Brazil Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper proposes and analyzes a proximal augmented Lagrangian (NL-IAPIAL) method for solving constrained nonconvex composite optimization problems, where the constraints are smooth and convex with respect to the order given by a closed convex cone. Each NL-IAPIAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite gradient method followed by a Lagrange multiplier update. Under some mild assumptions, a complexity bound for NL-IAPIAL to obtain an approximate stationary solution of the problem is also derived. Numerical experiments are also given to illustrate the computational efficiency of the proposed method.

关键词： inexact proximal augmented Lagrangian method K-convexity nonlinear constrained smooth nonconvex composite programming accelerated first-order methods iteration complexity

来源：评论

学校读者我要写书评

暂无评论

iteration complexity of Fixed-Step Methods by Nesterov and Polyak for Convex Quadratic Functions

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2024年第1期202卷 456-474页

作者： Hagedorn, Melinda Jarre, Florian Heinrich Heine Univ Dusseldorf Germany

This note considers the momentum method by Polyak and the accelerated gradient method by Nesterov, both without line search but with fixed step length applied to strongly convex quadratic functions assuming that exact gradients are used and appropriate upper and lower bounds for the extreme eigenvalues of the Hessian matrix are known. Simple 2-d-examples show that the Euclidean distance of the iterates to the optimal solution is non-monotone. In this context, an explicit bound is derived on the number of iterations needed to guarantee a reduction of the Euclidean distance to the optimal solution by a factor e. For both methods, the bound is optimal up to a constant factor, it complements earlier asymptotically optimal results for the momentum method, and it establishes another link of the momentum method and Nesterov's accelerated gradient method.

关键词： Momentum method Convex quadratic optimization iteration complexity Nesterov's accelerated gradient method

来源：评论

学校读者我要写书评

暂无评论

iteration complexity OF AN INNER ACCELERATED INEXACT PROXIMAL AUGMENTED LAGRANGIAN METHOD BASED ON THE CLASSICAL LAGRANGIAN FUNCTION

引用

SIAM JOURNAL ON OPTIMIZATION 2023年第1期33卷 181-210页

This paper establishes the iteration complexity of an inner accelerated inexact prox-imal augmented Lagrangian (IAIPAL) method for solving linearly constrained smooth nonconvex composite optimization problems that is based on the classical augmented Lagrangian (AL) func-tion. More specifically, each IAIPAL iteration consists of inexactly solving a proximal AL subprob-lem by an accelerated composite gradient (ACG) method followed by a classical Lagrange multiplier update. Under the assumption that the domain of the composite function is bounded and the prob-lem has a Slater point, it is shown that IAIPAL generates an approximate stationary solution in O(\varepsilon -5/2 log2\varepsilon -1) ACG iterations where \varepsilon > 0 is a tolerance for both stationarity and feasibility. Moreover, the above bound is derived without assuming that the initial point is feasible. Finally, numerical results are presented to demonstrate the strong practical performance of IAIPAL.

关键词： inexact proximal augmented Lagrangian method linearly constrained smooth non-convex composite programs inner accelerated first-order methods iteration complexity

来源：评论

学校读者我要写书评

暂无评论

iteration complexity OF A BLOCK COORDINATE GRADIENT DESCENT METHOD FOR CONVEX OPTIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2015年第3期25卷 1298-1313页

作者： Hua, Xiaoqin Yamashita, Nobuo Jiangsu Univ Sci & Technol Sch Math & Phys Zhenjiang 212003 Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

In this paper, we study the iteration complexity of a block coordinate gradient descent (BCGD) method with a cyclic rule for solving convex optimization problems. We propose a new Lipschitz continuity-like assumption and show that the iteration complexity for the proposed BCGD method can be improved to O(max{M, L}/epsilon), where M is the constant in the proposed assumption, L is the usual Lipschitz constant for the gradient of the objective function, and epsilon > 0 is the required precision. In addition, we analyze the relation between M and L, and prove that, in the worst case, M <= root NL, where N is the number of blocks.

关键词： nonsmooth optimization block coordinate gradient descent method iteration complexity convex optimization

来源：评论

学校读者我要写书评

暂无评论

iteration complexity on the generalized Peaceman-Rachford splitting method for separable convex programming

引用

OPTIMIZATION 2019年第9期68卷 1749-1767页

作者： Zhang, Xue-Qing Peng, Jian-Wen Yao, Jen-Chih Chongqing Univ Sch Econ & Business Adm Chongqing Peoples R China Chongqing Normal Univ Sch Math Sci Chongqing Peoples R China China Med Univ Ctr Gen Educ Taichung Taiwan

Recently, a generalized version of Peaceman-Rachford splitting method (GPRSM) for solving a convex minimization model with a general separable structure has been proposed and its global convergence has been proved by Sun and Liu. In this paper, we establish the worst-case convergence rate for the GPRSM in both the ergodic and a nonergodic senses, then we give some numerical results to demonstrate the convergence rate of the GPRSM.

关键词： Convex minimization problem generalized Peaceman-Rachford splitting method iteration complexity LASSO problem matrix optimization

来源：评论

学校读者我要写书评

暂无评论

iteration complexity of generalized complementarity problems

引用

JOURNAL OF INEQUALITIES AND APPLICATIONS 2019年第1期2019卷 1-13页

作者： Salahuddin Alesemi, Meshari Jazan Univ Dept Math Jazan Saudi Arabia

The goal of this paper is to discuss iteration complexity of two projection type methods for solving generalized complementarity problems and establish their worst-case sub-linear convergence rates measured by the ite... 详细信息

关键词： Generalized complementarity problems Projection operators Convergence rate iteration complexity Ergodic and nonergodic sense

来源：评论

学校读者我要写书评

暂无评论

iteration complexity of a Fixed-Stepsize SQP Method for Nonconvex Optimization with Convex Constraints 5th

Iteration Complexity of a Fixed-Stepsize SQP Method for Nonc...

引用

5th International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOV 2020

作者： Facchinei, Francisco Kungurtsev, Vyacheslav Lampariello, Lorenzo Scutari, Gesualdo Department of Computer Control and Management Engineering Antonio Ruberti Sapienza University of Rome Rome Italy Department of Computer Science Faculty of Electrical Engineering Czech Technical University in Prague Prague Czech Republic Department of Business Studies Roma Tre University Rome Italy School of Industrial Engineering Purdue University West-LafayetteIN United States

ISBN: (纸本)9783030720391

We consider an SQP method for solving nonconvex optimization problems whose feasible set is convex and with an objective function that is the sum of a smooth nonconvex term and a nonsmooth, convex one. In the proposed method, at each iteration, a direction is generated by solving a strongly convex approximation to the original problem and then a fixed-stepsize is taken in that direction. The complexity result we establish is, as far as we are aware, the best available for the rather general setting we consider. © 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Fixed-stepsize iteration complexity SQP methods

来源：评论

学校读者我要写书评

暂无评论

On the Information-Adaptive Variants of the ADMM: An iteration complexity Perspective

引用

JOURNAL OF SCIENTIFIC COMPUTING 2018年第1期76卷 327-363页

作者： Gao, Xiang Jiang, Bo Zhang, Shuzhong Univ Minnesota Dept Ind & Syst Engn Minneapolis MN 55455 USA Shanghai Univ Finance & Econ Sch Informat Management & Engn Res Inst Interdisciplinary Sci Shanghai 200433 Peoples R China

Designing algorithms for an optimization model often amounts to maintaining a balance between the degree of information to request from the model on the one hand, and the computational speed to expect on the other hand. Naturally, the more information is available, the faster one can expect the algorithm to converge. The popular algorithm of ADMM demands that objective function is easy to optimize once the coupled constraints are shifted to the objective with multipliers. However, in many applications this assumption does not hold;instead, often only some noisy estimations of the gradient of the objective-or even only the objective itself-are available. This paper aims to bridge this gap. We present a suite of variants of the ADMM, where the trade-offs between the required information on the objective and the computational complexity are explicitly given. The new variants allow the method to be applicable on a much broader class of problems where only noisy estimations of the gradient or the function values are accessible, yet the flexibility is achieved without sacrificing the computational complexity bounds.

关键词： Alternating direction method of multipliers (ADMM) iteration complexity Stochastic approximation First-order method Direct method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：