Maximal Monotone Operators and the Proximal Point Algorithm in the Presence of Computational Errors

In a finite-dimensional Euclidean space, we study the convergence of a proximal point method to a solution of the inclusion induced by a maximal monotone operator, under the presence of computational errors. Most results known in the literature establish the convergence of proximal point methods, when computational errors are summable. In the present paper, the convergence of the method is established for nonsummable computational errors. We show that the proximal point method generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant.     

Inexact Proximal Point Methods in Metric Spaces

We study the local convergence of a proximal point method in a metric space under the presence of computational errors. We show that the proximal point method generates a good approximate solution if the sequence of computational errors is bounded from above by some constant. The principle assumption is a local error bound condition which relates the growth of an objective function to the distance to the set of minimizers introduced by Hager and Zhang (SIAM J Control Optim 46:1683–1704, 2007).     

Two Strong Convergence Theorems for a Proximal Method in Reflexive Banach Spaces

Two strong convergence theorems for a proximal method for finding common zeroes of maximal monotone operators in reflexive Banach spaces are established. Both theorems take into account possible computational errors.     

The Extragradient Method for Solving Variational Inequalities in the Presence of Computational Errors

In a Hilbert space, we study the convergence of the subgradient method to a solution of a variational inequality, under the presence of computational errors. Most results known in the literature establish convergence of optimization algorithms, when computational errors are summable. In the present paper, the convergence of the subgradient method for solving variational inequalities is established for nonsummable computational errors. We show that the subgradient method generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant.     

The Extragradient Method for Convex Optimization in the Presence of Computational Errors

In this article, we study convergence of the extragradient method for constrained convex minimization problems in a Hilbert space. Our goal is to obtain an ε-approximate solution of the problem in the presence of computational errors, where ε is a given positive number. Most results known in the literature establish convergence of optimization algorithms, when computational errors are summable. In this article, the convergence of the extragradient method for solving convex minimization problems is established for nonsummable computational errors. We show that the the extragradient method generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant.     

A HOMOTOPY-BASED ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR STRUCTURED CONVEX OPTIMIZATION

The alternating direction method of multipliers(ADMM for short) is efficient for linearly constrained convex optimization problem. The practical computational cost of ADMM depends on the sub-problem solvers. The proximal point algorithm is a common sub-problem-solver. However, the proximal parameter is sensitive in the proximal ADMM. In this paper, we propose a homotopy-based proximal linearized ADMM, in which a homotopy method is used to solve the sub-problems at each iteration. Under some suitable conditions, the global convergence and the convergence rate of O(1/k) in the worst case of the proposed method are proven. Some preliminary numerical results indicate the validity of the proposed method.     

Weak convergence of a splitting algorithm in Hilbert spaces

In this paper, we present a splitting algorithm with computational errors for solving common solutions of zero point, fixed point and equilibrium problems. Weak convergence theorems of common solutions are established in the framework of real Hilbert spaces.     

An inertial-like proximal algorithm for equilibrium problems

The paper concerns with an inertial-like algorithm for approximating solutions of equilibrium problems in Hilbert spaces. The algorithm is a combination around the relaxed proximal point method, inertial effect and the Krasnoselski–Mann iteration. The using of the proximal point method with relaxations has allowed us a more flexibility in practical computations. The inertial extrapolation term incorporated in the resulting algorithm is intended to speed up convergence properties. The main convergence result is established under mild conditions imposed on bifunctions and control parameters. Several numerical examples are implemented to support the established convergence result and also to show the computational advantage of our proposed algorithm over other well known algorithms.     

On a proximal point method for convex optimization in banach spaces

We analyze the behavior of a parallel proximal point method for solving convex optimization problems in reflexive Banach spaces. Similar algorithms were known to converge under the implicit assumption that the norm of the space is Hilbertian. We extend the area of applicability of the proximal point method to solving convex optimization problems in Banach spaces on which totally convex functions can be found. This includes the class of all smooth uniformly convex Banach spaces. Also, our convergence results leave more flexibility for the choice of the penalty function involved in the algorithm and, in this way, allow simplification of the computational procedure.     

New results on the proximal point algorithm in non-positive curvature metric spaces

The subject of this paper is the inexact proximal point algorithm of usual and Halpern type in non-positive curvature metric spaces. We study the convergence of the sequences given by the inexact proximal point algorithm with non-summable errors. We also prove the strong convergence of the Halpern proximal point algorithm to a minimum point of the convex function. The results extend several results in Hilbert spaces, Hadamard manifolds and non-positive curvature metric spaces.     

Strong Convergence of an Inexact Proximal Point Algorithm in a Banach Space

Journal of Optimization Theory and Applications - By using our own approach, we study the strong convergence of an inexact proximal point algorithm with possible unbounded errors for a maximal...     

Local convergence of the proximal point method for a special class of nonconvex functions on Hadamard manifolds

Local convergence analysis of the proximal point method for a special class of nonconvex functions on Hadamard manifold is presented in this paper. The well definedness of the sequence generated by the proximal point method is guaranteed. Moreover, it is proved that each cluster point of this sequence satisfies the necessary optimality conditions and, under additional assumptions, its convergence for a minimizer is obtained.     

An extension of the proximal point algorithm with Bregman distances on Hadamard manifolds

In this paper we present an extension of the proximal point algorithm with Bregman distances to solve constrained minimization problems with quasiconvex and convex objective function on Hadamard manifolds. The proposed algorithm is a modified and extended version of the one presented in Papa Quiroz and Oliveira (J Convex Anal 16(1): 49–69, 2009). An advantage of the proposed algorithm, for the nonconvex case, is that in each iteration the algorithm only needs to find a stationary point of the proximal function and not a global minimum. For that reason, from the computational point of view, the proposed algorithm is more practical than the earlier proximal method. Another advantage, for the convex case, is that using minimal condition on the problem data as well as on the proximal parameters we get the same convergence results of the Euclidean proximal algorithm using Bregman distances.     

复合凸优化的快速邻近点算法

在大数据时代,随着数据采集手段的不断提升,大规模复合凸优化问题大量的出现在包括统计数据分析,机器与统计学习以及信号与图像处理等应用中.本文针对大规模复合凸优化问题介绍了一类快速邻近点算法.在易计算的近似准则和较弱的平稳性条件下,本文给出了该算法的全局收敛与局部渐近超线性收敛结果.同时,我们设计了基于对偶原理的半光滑牛顿法来高效稳定求解邻近点算法所涉及的重要子问题.最后,本文还讨论了如何通过深入挖掘并利用复合凸优化问题中由非光滑正则函数所诱导的非光滑二阶信息来极大减少半光滑牛顿算法中求解牛顿线性系统所需的工作量,从而进一步加速邻近点算法.     

Another version of the proximal point algorithm in a Banach space

In this paper, we study some non-traditional schemes of proximal point algorithm for nonsmooth convex functionals in a Banach space. The proximal approximations to their minimal points and/or their minimal values are considered separately for unconstrained and constrained minimization problems on convex closed sets. For the latter we use proximal point algorithms with the metric projection operators and first establish the estimates of the convergence rate with respect to functionals. We also investigate the perturbed projection proximal point algorithms and prove their stability. Some results concerning the classical proximal point method for minimization problems in a Banach space is also presented in this paper.     

Four parameter proximal point algorithms

Several strong convergence results involving two distinct four parameter proximal point algorithms are proved under different sets of assumptions on these parameters and the general condition that the error sequence converges to zero in norm. Thus our results address the two important problems related to the proximal point algorithm — one being that of strong convergence (instead of weak convergence) and the other one being that of acceptable errors. One of the algorithms discussed was introduced by Yao and Noor (2008) [7] while the other one is new and it is a generalization of the regularization method initiated by Lehdili and Moudafi (1996) [9] and later developed by Xu (2006) [8]. The new algorithm is also ideal for estimating the convergence rate of a sequence that approximates minimum values of certain functionals. Although these algorithms are distinct, it turns out that for a particular case, they are equivalent. The results of this paper extend and generalize several existing ones in the literature.     

A hybrid inexact Logarithmic-Quadratic Proximal method for nonlinear complementarity problems

Inspired by the Logarithmic-Quadratic Proximal method [A. Auslender, M. Teboulle, S. Ben-Tiba, A logarithmic-quadratic proximal method for variational inequalities, Comput. Optim. Appl. 12 (1999) 31-40], we present a new prediction-correction method for solving the nonlinear complementarity problems. In our method, an intermediate point is produced by approximately solving a nonlinear equation system based on the Logarithmic-Quadratic Proximal method; and the new iterate is obtained by convex combination of the previous point and the one generated by the improved extragradient method at each iteration. The proposed method allows for constant relative errors and this yields a more practical Logarithmic-Quadratic Proximal type method. The global convergence is established under mild conditions. Preliminary numerical results indicate that the method is effective for large-scale nonlinear complementarity problems.     

A Hybrid Approximate Extragradient – Proximal Point Algorithm Using the Enlargement of a Maximal Monotone Operator

We propose a modification of the classical extragradient and proximal point algorithms for finding a zero of a maximal monotone operator in a Hilbert space. At each iteration of the method, an approximate extragradient-type step is performed using information obtained from an approximate solution of a proximal point subproblem. The algorithm is of a hybrid type, as it combines steps of the extragradient and proximal methods. Furthermore, the algorithm uses elements in the enlargement (proposed by Burachik, Iusem and Svaiter) of the operator defining the problem. One of the important features of our approach is that it allows significant relaxation of tolerance requirements imposed on the solution of proximal point subproblems. This yields a more practical proximal-algorithm-based framework. Weak global convergence and local linear rate of convergence are established under suitable assumptions. It is further demonstrated that the modified forward-backward splitting algorithm of Tseng falls within the presented general framework.     

On the convergence of the entropy-exponential penalty trajectories and generalized proximal point methods in semidefinite optimization

The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite programming problem are studied in this paper. It is proved that the primal path converges to the analytic center of the primal optimal set with respect to the entropy function, the dual path converges to a point in the dual optimal set and the primal-dual path associated to this paths converges to a point in the primal-dual optimal set. As an application, the generalized proximal point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered. The convergence of the primal proximal sequence to the analytic center of the primal optimal set with respect to the entropy function is established and the convergence of a particular weighted dual proximal sequence to a point in the dual optimal set is obtained.     

Applications of the method of partial inverses to convex programming: Decomposition

A primal–dual decomposition method is presented to solve the separable convex programming problem. Convergence to a solution and Lagrange multiplier vector occurs from an arbitrary starting point. The method is equivalent to the proximal point algorithm applied to a certain maximal monotone multifunction. In the nonseparable case, it specializes to a known method, the proximal method of multipliers. Conditions are provided which guarantee linear convergence.This research was sponsored, in part, by the Air Force Office of Scientific Research under grant 80-0195.