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

An extension of the proximal point algorithm beyond convexity

JOURNAL OF GLOBAL OPTIMIZATION 2022年第2期82卷 313-329页

作者： Grad, Sorin-Mihai Lara, Felipe Univ Vienna Fac Math Oskar Morgenstern Pl 1 A-1090 Vienna Austria Univ Tarapaca Fac Ciencias Dept Matemat Arica Chile

We introduce and investigate a new generalized convexity notion for functions called prox-convexity. The proximity operator of such a function is single-valued and firmly nonexpansive. We provide examples of (strongly) quasiconvex, weakly convex, and DC (difference of convex) functions that are prox-convex, however none of these classes fully contains the one of prox-convex functions or is included into it. We show that the classical proximal point algorithm remains convergent when the convexity of the proper lower semicontinuous function to be minimized is relaxed to prox-convexity.

关键词： Nonsmooth optimization Nonconvex optimization Proximity operator proximal point algorithm Generalized convex function

来源：评论

学校读者我要写书评

暂无评论

Abstract strongly convergent variants of the proximal point algorithm

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2022年第1期83卷 349-380页

作者： Sipos, Andrei Univ Bucharest Fac Math & Comp Sci Res Ctr Log Optimizat & Secur LOS Dept Comp Sci Acad 14 Bucharest 010014 Romania Romanian Acad Simion Stoilow Inst Math Calea Grivitei 21 Bucharest 010702 Romania

We prove an abstract form of the strong convergence of the Halpern-type and Tikhonov-type proximal point algorithms in CAT(0) spaces. In addition, we derive uniform and computable rates of metastability (in the sense ... 详细信息

关键词： Halpern iteration proximal point algorithm CAT(0) Jointly firmly nonexpansive families Proof mining Rates of metastability

来源：评论

学校读者我要写书评

暂无评论

High-Dimensional Gaussian Sampling: A Review and a Unifying Approach Based on a Stochastic proximal point algorithm

引用

SIAM REVIEW 2022年第1期64卷 3-56页

作者： Vono, Maxime Dobigeon, Nicolas Chainais, Pierre Huawei Lagrange Math & Comp Res Ctr F-75007 Paris France Univ Toulouse IRIT INP ENSEEIHT F-31071 Toulouse France Inst Univ France IUF Toulouse France Univ Lille CNRS Cent Lille UMR 9189CRIStAL F-59000 Lille France

Efficient sampling from a high-dimensional Gaussian distribution is an old but high-stakes issue. Vanilla Cholesky samplers imply a computational cost and memory requirements that can rapidly become prohibitive in high dimensions. To tackle these issues, multiple methods have been proposed from different communities ranging from iterative numerical linear algebra to Markov chain Monte Carlo (MCMC) approaches. Surprisingly, no complete review and comparison of these methods has been conducted. This paper aims to review all these approaches by pointing out their differences, close relations, benefits, and limitations. In addition to reviewing the state of the art, this paper proposes a unifying Gaussian simulation framework by deriving a stochastic counterpart of the celebrated proximal point algorithm in optimization. This framework offers a novel and unifying revisiting of most of the existing MCMC approaches while also extending them. Guidelines to choosing the appropriate Gaussian simulation method for a given sampling problem in high dimensions are proposed and illustrated with numerical examples.

关键词： Gaussian distribution high-dimensional sampling linear system Markov chain Monte Carlo proximal point algorithm

来源：评论

学校读者我要写书评

暂无评论

Quantitative results on a Halpern-type proximal point algorithm

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2021年第1期79卷 101-125页

作者： Leustean, Laurentiu Pinto, Pedro Univ Bucharest Fac Math & Comp Sci Dept Comp Sci Res Ctr Log Optimizat & Secur LOS Acad 14 Bucharest 010014 Romania Romanian Acad Simion Stoilow Inst Math Calea Grivitei 21 Bucharest 010702 Romania Tech Univ Darmstadt Dept Math Schlossgartenstr 7 D-64289 Darmstadt Germany

We apply proof mining methods to analyse a result of Boikanyo and Morosanu on the strong convergence of a Halpern-type proximal point algorithm. As a consequence, we obtain quantitative versions of this result, provid... 详细信息

关键词： proximal point algorithm Maximally monotone operators Halpern iteration Rates of convergence Rates of metastability Proof mining

来源：评论

学校读者我要写书评

暂无评论

A Rate of Metastability for the Halpern Type proximal point algorithm

引用

NUMERICAL FUNCTIONAL ANALYSIS AND OPTIMIZATION 2021年第3期42卷 320-343页

作者： Pinto, Pedro Tech Univ Darmstadt Dept Math D-64289 Darmstadt Germany

Using proof-theoretical techniques, we analyze a proof by Hong-Kun Xu regarding a result of strong convergence for the Halpern type proximal point algorithm. We obtain a rate of metastability (in the sense of Terence Tao) and also a rate of asymptotic regularity for the iteration. Furthermore, our final quantitative result bypasses the sequential weak compactness argument present in the original proof. This elimination is reflected in the extraction of primitive recursive quantitative information. This work follows from recent results in Proof Mining regarding the removal of sequential weak compactness arguments.

关键词： Metastability proof mining proximal point algorithm rates of asymptotic regularity sequential weak compactness

来源：评论

学校读者我要写书评

暂无评论

TIGHT SUBLINEAR CONVERGENCE RATE OF THE proximal point algorithm FOR MAXIMAL MONOTONE INCLUSION PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第3期30卷 1905-1921页

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

The tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems is established based on the squared fixed point residual. By using the performance estimation framework, the tight sublinear convergence rate problem is written as an infinite dimensional nonconvex optimization problem, which is then equivalently reformulated as a finite dimensional semidefinite programming (SDP) problem. By solving the SDP, the exact sublinear rate is computed numerically. Theoretically, by constructing a feasible solution to the dual SDP, an upper bound is obtained for the tight sublinear rate. On the other hand, an example in two dimensional space is constructed to provide a lower bound. The lower bound matches exactly the upper bound obtained from the dual SDP, which also coincides with the numerical rate computed. Hence, we have established the worst case sublinear convergence rate, which is tight in terms of both the order and the constants involved.

关键词： proximal point algorithm maximal monotone inclusion tight sublinear convergence rate performance estimation framework semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Metastability of the proximal point algorithm with multi-parameters

引用

PORTUGALIAE MATHEMATICA 2020年第3-4期77卷 345-381页

作者： Dinis, Bruno Pinto, Pedro Univ Lisbon Dept Matemat Edificio C6 P-1749016 Lisbon Portugal Tech Univ Darmstadt Dept Math Schlossgartenstr 7 D-64289 Darmstadt Germany

In this article we use techniques of proof mining to analyse a result, due to Yong=hong Yao and Muhammad Aslam Noor, concerning the strong convergence of a generalized proximal point algorithm which involves multiple parameters. Yao and Noor's result ensures the strong convergence of the algorithm to the nearest projection point onto the set of zeros of the operator. Our quantitative analysis, guided by Fernando Ferreira and Paulo Oliva's bounded functional interpretation, provides a primitive recursive bound on the metastability for the convergence of the algorithm, in the sense of Terence Tao. Furthermore, we obtain quantitative information on the asymptotic regularity of the iteration. The results of this paper are made possible by an arithmetization of the lim sup.

关键词： Convex optimization proximal point algorithm proof mining metastability

来源：评论

学校读者我要写书评

暂无评论

BREGMAN proximal point algorithm REVISITED: A NEW INEXACT VERSION AND ITS INERTIAL VARIANT

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第3期32卷 1523-1554页

作者： Yang, L. E., I Toh, Kim-chuan Hong Kong Polytech Univ Dept Appl Math Hung Hom Kowloon Hong Kong Peoples R China Natl Univ Singapore Dept Math Singapore 119076 Singapore Natl Univ Singapore Inst Operat Res & Analyt Singapore 119076 Singapore

We study a general convex optimization problem, which covers various classic problems in different areas and particularly includes many optimal transport related problems arising in recent years. To solve this problem, we revisit the classic Bregman proximal point algorithm (BPPA) and introduce a new inexact stopping condition for solving the subproblems, which can circumvent the underlying feasibility difficulty often appearing in existing inexact conditions when the problem has a complex feasible set. Our inexact condition also covers several existing inexact conditions as special cases and hence makes our inexact BPPA (iBPPA) more flexible to fit different scenarios in practice. As an application to the standard optimal transport (OT) problem, our iBPPA with the entropic proximal term can bypass some numerical instability issues that usually plague the popular Sinkhorn's algorithm in the OT community, since our iBPPA does not require the proximal param-eter to be very small for obtaining an accurate approximate solution. The iteration complexity of O(1/k) and the convergence of the sequence are also established for our iBPPA under some mild conditions. Moreover, inspired by Nesterov's acceleration technique, we develop an inertial variant of our iBPPA, denoted by V-iBPPA, and establish the iteration complexity of O(1/k\lambda), where \lambda\geq 1 is a quadrangle scaling exponent of the kernel function. In particular, when the proximal parameter is a constant and the kernel function is strongly convex with Lipschitz continuous gradient (hence \lambda = 2), our V-iBPPA achieves a faster rate of O(1/k(2)) just as existing accelerated inexact proximal point algorithms. Some preliminary numerical experiments for solving the standard OT problem are conducted to show the convergence behaviors of our iBPPA and V-iBPPA under different inexactness settings. The experiments also empirically verify the potential of our V-iBPPA for improving the convergence speed.

关键词： proximal point algorithm Bregman distance inexact condition Nesterov's accel-eration optimal transport

来源：评论

学校读者我要写书评

暂无评论

proximal point algorithm for nonlinear multivalued type mappings in Hadamard spaces

引用

MATHEMATICAL METHODS IN THE APPLIED SCIENCES 2019年第17期42卷 5758-5768页

作者： Kumam, Wiyada Kitkuan, Duangkamon Padcharoen, Anantachai Kumam, Poom Rajamangala Univ Technol Thanyaburi RMUTT Fac Sci & Technol Dept Math & Comp Sci Program Appl Stat Thanyaburi Thailand KMUTT KMUTT Fixed Point Res Lab KMUTT Fixed Point Theory & Applicat Res Grp Theoret & Computat Sci Ctr TaCS 126 Pracha Uthit Rd Bangkok 10140 Thailand KMUTT Dept Math Fac Sci 126 Pracha Uthit Rd Bangkok 10140 Thailand China Med Univ China Med Univ Hosp Dept Med Res Taichung Taiwan

In this paper, we modify the proximal point algorithm for finding common fixed points in CAT(0) spaces for nonlinear multivalued mappings and a minimizer of a convex function and prove Delta-convergence of the proposed algorithm. A numerical example is presented to illustrate the convergence result. Our results improve and extend the corresponding results in the literature.

关键词： CAT(0) spaces common fixed points convex minimization problems nonlinear multivalued mappings proximal point algorithm

来源：评论

学校读者我要写书评

暂无评论

WEAK AND LINEAR CONVERGENCE OF A GENERALIZED proximal point algorithm WITH ALTERNATING INERTIAL STEPS FOR A MONOTONE INCLUSION PROBLEM

JOURNAL OF NONLINEAR AND VARIATIONAL ANALYSIS

引用

JOURNAL OF NONLINEAR AND VARIATIONAL ANALYSIS 2021年第6期5卷 881-892页

作者： Shehu, Yekini Ezeora, Jeremiah N. Zhejiang Normal Univ Dept Math Jinhua Zhejiang Peoples R China Univ Port Harcourt Dept Math & Stat Port Harcourt Rivers State Nigeria

The proximal point algorithm (PPA) is a powerful tool for solving monotone inclusion problems. Recently, Tao and Yuan [On the optimal linear convergence rate of a generalized proximal point algorithm, J. Sci. Comput. 74 (2018), 826-850] proposed a generalized PPA (GPPA) for finding a zero point of a maximal monotone operator, and obtained the linear convergence rate of the generalized PPA. In this paper, we consider accelerating the GPPA with the aid of the inertial extrapolation. We propose a generalized proximal point algorithm with alternating inertial steps solving monotone inclusion problem, and obtain weak convergence results under some mild conditions. When the inverse of the involved monotone operator is Lipschitz continuous at the origin, we prove that the iterative sequence generated by our generalized proximal point algorithm is linearly convergent. The Fejer monotonicity of even subsequences of the iterative sequence is also recovered. Finally, we give some priori and posteriori error estimates of our generated sequences.

关键词： Alternated inertial step Maximal monotone operator proximal point algorithm Weak and linear convergence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：