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

AN ACCELERATED inexact proximal point method FOR SOLVING NONCONVEX-CONCAVE MIN-MAX PROBLEMS

SIAM JOURNAL ON OPTIMIZATION 2021年第4期31卷 2558-2585页

作者： Kong, Weiwei Monteiro, Renato D. C. Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper presents smoothing schemes for obtaining approximate stationary points of unconstrained or linearly constrained composite nonconvex-concave min-max (and hence non smooth) problems by applying well-known algorithms to composite smooth approximations of the original problems. More specifically, in the unconstrained (resp., constrained) case, approximate stationary points of the original problem are obtained by applying, to its composite smooth approximation, an accelerated inexact proximal point (resp., quadratic penalty) method presented in a previous paper by the authors. Iteration complexity bounds for both smoothing schemes are also established. Finally, numerical results are given to demonstrate the efficiency of the unconstrained smoothing scheme.

关键词： quadratic penalty method composite nonconvex problem iteration complexity inexact proximal point method first-order accelerated gradient method minimax problem

来源：评论

学校读者我要写书评

暂无评论

COMPLEXITY OF A QUADRATIC PENALTY ACCELERATED inexact proximal point method FOR SOLVING LINEARLY CONSTRAINED NONCONVEX COMPOSITE PROGRAMS

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第4期29卷 2566-2593页

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

This paper analyzes the iteration complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. More specifically, the objective function is of the form f + h, where f is a differentiable function whose gradient is Lipschitz continuous and h is a closed convex function with possibly unbounded domain. The method, basically, consists of applying an accelerated inexact proximal point method for approximately solving a sequence of quadratic penalized subproblems associated with the linearly constrained problem. Each subproblem of the proximal point method is in turn approximately solved by an accelerated composite gradient (ACG) method. It is shown that the proposed scheme generates a rho-approximate stationary point in at most O(rho(-3)) ACG iterations. Finally, numerical results showing the efficiency of the proposed method are also given.

关键词： quadratic penalty method composite nonconvex program iteration complexity inexact proximal point method first-order accelerated gradient method

来源：评论

学校读者我要写书评

暂无评论

COMPLEXITY-OPTIMAL AND PARAMETER-FREE FIRST-ORDER methodS FOR FINDING STATIONARY pointS OF COMPOSITE OPTIMIZATION PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2024年第3期34卷 3005-3032页

作者： Kong, Weiwei Oak Ridge Natl Lab Comp Sci & Math Div Oak Ridge TN 37830 USA

This paper develops and analyzes an accelerated proximal descent method for finding stationary points of nonconvex composite optimization problems. The objective function is of the form f + h, where h is a proper closed convex function, f is a differentiable function on the domain of h, and \nabla f is Lipschitz continuous on the domain of h. The main advantage of this method is that it is ``parameter-free"" in the sense that it does not require knowledge of the Lipschitz constant of \nabla f or of any global topological properties of f. It is shown that the proposed method can obtain an \varepsilon -approximate stationary point with iteration complexity bounds that are optimal, up to logarithmic terms over \varepsilon , in both the convex and nonconvex settings. Some discussion is also given about how the proposed method can be leveraged in other existing optimization frameworks, such as min-max smoothing and penalty frameworks for constrained programming, to create more specialized parameter-free methods. Finally, numerical experiments are presented to support the practical viability of the method.

关键词： nonconvex composite optimization first-order accelerated gradient method itera tion complexity inexact proximal point method parameter-free adaptive optimal complexity

来源：评论

学校读者我要写书评

暂无评论

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 ACCELERATED HPE-TYPE ALGORITHM FOR A CLASS OF COMPOSITE CONVEX-CONCAVE SADDLE-point PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2016年第1期26卷 29-56页

作者： He, Yunlong Monteiro, Renato D. C. Georgia Inst Technol Sch Math Atlanta GA 30332 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper proposes a new algorithm for solving a class of composite convex-concave saddle-point problems. The new algorithm is a special instance of the hybrid proximal extragradient framework in which a Nesterov accelerated variant is used to approximately solve the prox subproblems. One of the advantages of the new method is that it works for any constant choice of proximal stepsize. Moreover, a suitable choice of the latter stepsize yields a method with the best known (accelerated inner) iteration complexity for the aforementioned class of saddle-point problems. In contrast to the smoothing technique of [Y. Nesterov, Math. Program., 103 (2005), pp. 127-152], our accelerated method does not assume that a feasible set is bounded due to its proximal point nature. Experiment results on three problem sets show that the new method outperforms Nesterov's smoothing technique of [Y. Nesterov, Math. Program., 103 (2005), pp. 127-152].

关键词： saddle-point problem composite convex optimization monotone inclusion problem inexact proximal point method hybrid proximal extragradient accelerated method complexity smoothing

来源：评论

学校读者我要写书评

暂无评论

An Alternating Direction method for Nash Equilibrium of Two-Person Games with Alternating Offers

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2013年第2期157卷 533-551页

作者： Peng, Zheng Zhu, Wenxing Fuzhou Univ Coll Math & Comp Sci Fuzhou 350108 Peoples R China Fuzhou Univ Ctr Discrete Math & Theoret Comp Sci Fuzhou 350108 Peoples R China

In this paper, we propose a method for finding a Nash equilibrium of two-person games with alternating offers. The proposed method is referred to as the inexact proximal alternating direction method. In this method, the idea of alternating direction method simulates alternating offers in the game, while the inexact solutions of subproblems can be matched to the assumptions of incomplete information and bounded individual rationality in practice. The convergence of the proposed method is proved under some suitable conditions. Numerical tests show that the proposed method is competitive to the state-of-the-art algorithms.

关键词： Computational game theory Nash equilibrium inexact proximal point method Alternating direction method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：