Comparison of two kinds of approximate proximal point algorithms for monotone variational inequalities

This paper proposes two kinds of approximate proximal point algorithms （APPA） for monotone variational inequalities, both of which can be viewed as two extended versions of Solodov and Svaiter＇s APPA in the paper ＂Error bounds for proximal point subproblems and associated inexact proximal point algorithms＂ published in 2000. They are both prediction- correction methods which use the same inexactness restriction; the only difference is that they use different search directions in the correction steps. This paper also chooses an optimal step size in the two versions of the APPA to improve the profit at each iteration. Analysis also shows that the two APPAs are globally convergent under appropriate assumptions, and we can expect algorithm 2 to get more progress in every iteration than algorithm 1. Numerical experiments indicate that algorithm 2 is more efficient than algorithm 1 with the same correction step size,

PROXIMAL POINT ALGORITHM WITH ERRORS FOR GENERALIZED STRONGLY NONLINEARQUASIVARIATIONAL INCLUSIONS

In this paper, a class of generalized strongly nonlinear quasivariational inclusions are studied. By using the properties of the resolvent operator associated with a maximal monotone; mapping in Hilbert space, an existence theorem of solutions for generalized strongly nonlinear quasivariational inclusion is established and a new proximal point algorithm with errors is suggested for finding approximate solutions which strongly converge to the exact solution of the generalized strongly, nonlinear quasivariational inclusion. As special cases, some known results in this field are also discussed.

Comparison of two approximal proximal point algorithms for monotone variational inequalities

Proximal point algorithms （PPA） are attractive methods for solving monotone variational inequalities （MVI）. Since solving the sub-problem exactly in each iteration is costly or sometimes impossible, various approximate versions ofPPA （APPA） are developed for practical applications. In this paper, we compare two APPA methods, both of which can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. By extending the general forward-backward splitting methods, we obtain Algorithm Ⅰ; in the same way, Algorithm Ⅱ is proposed by spreading the general extra-gradient methods. Our analysis explains theoretically why Algorithm Ⅱ usually outperforms Algorithm Ⅰ. For computation practice, we consider a class of MVI with a special structure, and choose the extending Algorithm Ⅱ to implement, which is inspired by the idea of Gauss-Seidel iteration method making full use of information about the latest iteration. And in particular, self-adaptive techniques are adopted to adjust relevant parameters for faster convergence. Finally, some numerical experiments are reported on the separated MVI. Numerical results showed that the extending Algorithm II is feasible and easy to implement with relatively low computation load.

MODIFIED APPROXIMATE PROXIMAL POINT ALGORITHMS FOR FINDING ROOTS OF MAXIMAL MONOTONE OPERATORS

In order to find roots of maximal monotone operators, this paper introduces and studies the modified approximate proximal point algorithm with an error sequence {e k} such that || ek || \leqslant hk || xk - [(x)\tilde]k ||\left\| { e^k } \right\| \leqslant \eta _k \left\| { x^k - \tilde x^k } \right\| with ?k = 0￥ ( hk - 1 ) < + ￥\sum\limits_{k = 0}^\infty {\left( {\eta _k - 1} \right)} and infk \geqslant 0 hk = m\geqslant 1\mathop {\inf }\limits_{k \geqslant 0} \eta _k = \mu \geqslant 1 . Here, the restrictions on {η k} are very different from the ones on {η k}, given by He et al (Science in China Ser. A, 2002, 32 (11): 1026–1032.) that supk \geqslant 0 hk = v < 1\mathop {\sup }\limits_{k \geqslant 0} \eta _k = v . Moreover, the characteristic conditions of the convergence of the modified approximate proximal point algorithm are presented by virtue of the new technique very different from the ones given by He et al.

Proximal point algorithm for a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings

We introduced a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings. Using the resolvent operator method in Hilbert spaces, we suggested a new proximal point algorithm for finding approximate solutions, which strongly converge to the exact solution of a fuzzy set-valued variational inclusion with (H,η)-monotone. The results improved and generalized the general quasi-variational inclusions with fuzzy set-valued mappings proposed by Jin and Tian Jin MM, Perturbed proximal point algorithm for general quasi-variational inclusions with fuzzy set-valued mappings, OR Transactions, 2005, 9(3): 31-38, (In Chinese); Tian YX, Generalized nonlinear implicit quasi-variational inclusions with fuzzy mappings, Computers & Mathematics with Applications, 2001, 42: 101-108.

On Over-Relaxed Proximal Point Algorithms for Generalized Nonlinear Operator Equation with (A,η,m)-Monotonicity Framework

In this paper, a new class of over-relaxed proximal point algorithms for solving nonlinear operator equations with (A,η,m)-monotonicity framework in Hilbert spaces is introduced and studied. Further, by using the generalized resolvent operator technique associated with the (A,η,m)-monotone operators, the approximation solvability of the operator equation problems and the convergence of iterative sequences generated by the algorithm are discussed. Our results improve and generalize the corresponding results in the literature.

A new approximate proximal point algorithm for maximal monotone operator

The problem concerned in this paper is the set-valued equation 0 ∈ T(z) where T is a maximal monotone operator. For given xk and βk >: 0, some existing approximate proximal point algorithms take $x^{k + 1} = \tilde x^k $ such that $$x^k + e^k \in \tilde x^k + \beta _k T(\tilde x^k ) and \left\| {e^k } \right\| \leqslant \eta _k \left\| {x^k - \tilde x^k } \right\|,$$ where ?k is a non-negative summable sequence. Instead of $x^{k + 1} = \tilde x^k $ , the new iterate of the proposing method is given by $$x^{k + 1} = P_\Omega [\tilde x^k - e^k ],$$ where Ω is the domain of T and PΩ(·) denotes the projection on Ω. The convergence is proved under a significantly relaxed restriction supK>0 ηKη1.

PROXIMAL POINT ALGORITHM FOR MINIMIZATION OF DC FUNCTION

In this paper we present some algorithms for minimization of DC function (difference of two convex functions). They are descent methods of the proximal-type which use the convex properties of the two convex functions separately. We also consider an approximate proximal point algorithm. Some properties of the ε-subdifferential and the ε-directional derivative are discussed. The convergence properties of the algorithms are established in both exact and approximate forms. Finally, we give some applications to the concave programming and maximum eigenvalue problems.

A PROXIMAL POINT ALGORITHM FOR A SYSTEM OF GENERALIZED MIXED VARIATIONAL INEQUALITIES

This paper introduces and considers a new system of generalized mixed variational inequal- ities in a Hilbert space, which includes many new and known systems of variational inequalities and generalized variational inequalities as special cases. By using the two concepts of η-subdifferential and η-proximal mappings of a proper function, the authors try to demonstrate that the system of generalized mixed variational inequalities is equivalence with a fixed point problem. By applying the equivalence, a new and innovative η-proximal point algorithm for finding approximate solutions of the system of generalized mixed variational inequalities will be suggested and analyzed. The authors also study the convergence analysis of the new iterative method under much weaker conditions. The results can be viewed as a refinement and improvement of the previously known results for variational inequalities.

The Developments of Proximal Point Algorithms

The problem of finding a zero point of a maximal monotone operator plays a central role in modeling many application problems arising from various fields,and the proximal point algorithm(PPA)is among the fundamental algorithms for solving the zero-finding problem.PPA not only provides a very general framework of analyzing convergence and rate of convergence of many algorithms,but also can be very efficient in solving some structured problems.In this paper,we give a survey on the developments of PPA and its variants,including the recent results with linear proximal term,with the nonlinear proximal term,as well as the inexact forms with various approximate criteria.

On the Convergence Rate of a Proximal Point Algorithm for Vector Function on Hadamard Manifolds

The proximal point algorithm has many interesting applications,such as signal recovery,signal processing and others.In recent years,the proximal point method has been extended to Riemannian manifolds.The main advantages of these extensions are that nonconvex problems in classic sense may become geodesic convex by introducing an appropriate Riemannian metric,constrained optimization problems may be seen as unconstrained ones.In this paper,we propose an inexact proximal point algorithm for geodesic convex vector function on Hadamard manifolds.Under the assumption that the objective function is coercive,the sequence generated by this algorithm converges to a Pareto critical point.When the objective function is coercive and strictly geodesic convex,the sequence generated by this algorithm converges to a Pareto optimal point.Furthermore,under the weaker growth condition,we prove that the inexact proximal point algorithm has linear/superlinear convergence rate.

Approximate Customized Proximal Point Algorithms for Separable Convex Optimization

Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint.We design two types of inexact error criteria for the subproblems.The first one is absolutely summable error criterion,under which both subproblems can be solved inexactly.When one of the two subproblems is easily solved,we propose another novel error criterion which is easier to implement,namely relative error criterion.The relative error criterion only involves one parameter,which is more implementable.We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms.The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.

用扰动逼近算法解一般混合似变分不等式组

利用预解算子技巧,给出了一个求解一般混合似变分不等式组的显式n步扰动迭代算法,并证明了该算法在适当的条件下收敛.

用扰动逼近算法解广义混合拟似变分不等式组

引入和研究了一类广义混合拟似变分不等式组,借助η 次微分及η 逼近映射,给出了求此类变分不等式组的近似解的扰动η 逼近算法,并证明了此类变分不等式组的解的存在性及算法的强收敛性.

Banach空间中广义混合变分不等式解的迭代算法

利用R.S.Burachik和S.Scheimberg(SIAM J Control Optim,2001,39(5):1633-1649.)介绍的近似点算法和Bregman泛函,在自反Banach空间中建立了一类广义混合变分不等式解的迭代算法,证明了迭代序列是有定义的,并且弱收敛于广义混合变分不等式的解.同时,给出了广义混合变分不等式解的存在性的一个充分必要条件.

一类非线性极小极大问题的粒子群-邻近点算法

针对每个分量函数都是凸函数的离散型非线性极小极大问题,提出一种全局收敛的粒子群-邻近点混合算法。该算法利用极大熵函数将极小极大问题转化为一个光滑函数的无约束凸优化问题;利用邻近点算法为外层算法,内层算法采用粒子群算法来优化此问题;数值结果表明,该算法数值稳定性好、收敛快,是求解此类非线性极小极大问题的一种有效算法。

对广义强非线性拟变分包含带有误差的近似点算法

本文研究了一类广义强非线性拟变分包含·在Ｈｉｌｂｅｒｔ空间内利用与极大单调映象相联系的预解算子的性质，对广义强非线性拟变分包含建立了解的存在性定理和建议了一个新的寻求近似解的带有误差的近似总算法，证明了近似解序列强收敛于精确解·作为特例，在此领域内的某些已知结果也被讨论·

极小极大问题的生物地理学优化邻近点算法

离散型非线性极小极大问题本质上为一个传统的梯度类算法难以求解的不可微优化问题.针对每个分量函数都是凸函数的此类问题,利用熵函数法将其转化为一个光滑的无约束凸优化问题,并将具有并行搜索机制的生物地理学优化算法和具有全局收敛性的邻近点算法相混合,设计了一种具有全局收敛性的混合算法.为了充分发挥生物地理学优化算法的并行搜索机制和无需使用初始点的优点,该混合算法采用生物地理学优化为内层算法邻近点算法为外层算法.数值仿真结果表明,所提算法是求解此类非线性极小极大问题的一种有效算法.

基于张量秩校正的图像恢复方法

针对医学图像和视频图像的恢复问题,基于张量表示,研究有限样本下的低秩张量数据恢复问题,在张量奇异值分解(t-SVD)理论的基础上,提出了张量秩校正模型和两阶段张量秩校正方法,第一阶段是用张量核范数最小化模型求得预估解,第二阶段,根据预估解,求解张量秩校正模型,获得更高精度的解.构建了求解张量秩校正模型和张量核范数最小化模型的张量近似点算法,使得可以在实数域上对张量直接进行计算,并且从理论上证明了该算法的收敛性.通过对医学图像和视频图像的数值仿真实验,验证了本文所提出模型和方法的有效性,实验结果显示,张量秩校正模型和方法能够取得更高的恢复精度.

基于邻近算子求解带凸集约束可分离凸优化问题的原始对偶不动点算法

很多实际问题根据不同的物理背景,解的取值是有一定限制的.本文拟推广PDFP2O算法以求解带闭凸集约束的可分离凸优化问题.通过将闭凸集约束表示成示性函数而加入目标函数中的技巧,适当重组函数,可直接利用PDFP2O算法求解,再利用函数的可分离性,即可得到闭凸集上的基于邻近算子的原始对偶不动点算法(PDFP2OC).因为PDFP2OC本质上就是利用PDFP2O求解与原问题等价的无约束问题,根据PDFP2O的理论结果,可以方便地得到PDFP2OC的收敛性以及收敛速度.最后通过CT重构说明了算法的有效性.