求解单调变分不等式的近似邻近点算法的收敛性分析

为了求解单调变分不等式,建立了一个新的误差准则,并且在不需要增加诸如投影,外梯度等步骤的情况下证明了邻近点算法的收敛性.     

关于极大强单调算子的不精确邻近点算法的收敛性分析

该文研究集值映象方程0∈T(z)的解的迭代逼近，其中T是极大强单调算子．设{x^k}与{e^k}是由不精确邻近点算法x^{k+1}+c_kT(x^{k+1})> x^k+e^{k+1}生成的序列，满足‖e^{k+1}‖≤η_k‖x^{k+1}_x^k‖, ∑^∞_{k=0}(η_k-1)<+∞且inf_(k≥0) η_k=μ≥1.在适当的限制下证明了，{x^k}收敛到T的一个根当且仅当 lim inf_{k→+∞} d(x^k,Z)=0，其中Z是方程0∈T(z)的解集     

关于单调的变分不等式问题的收敛性方法

１引言变分不等式的性质及解法的研究是优化领域的重要课题．所谓变分不等式问题就是：寻找一个点,使得其中Ｘ是Ｒｎ中的非空闲凸集,Ｆ是Ｒｎ中的映射,表示Ｒｎ中的内积．求解问题（１．１）有多种思路［１,４,５］其中之一就是将（１．１）转化为它的某种等价问题,再进行求解．在山中ＭａｓａｏＦｕｋｕｓｈｉｍａ给出了（１．１）的如下的等价问题Ｇ是对称正定矩阵．山提出了求解（１．２）的带精确搜索和Ａｒｍｉｊｏ搜索的两种收敛性算法．本文建立了“ｄ－ｆｕｎｃｔｉｏｎ”的概念,利用“Ｄ－ｆｕｎｃｔｉｎ”给出了（１．１）…     

有界约束单调变分不等式的内点连续算法

讨论变分不等式问题VIP(X，F)，其中F是单调函数，约束集X为有界区域．利用摄动技术和一类光滑互补函数将问题等价转化为序列合两个参数的非线性方程组，然后据此建立VIP(X，F)的一个内点连续算法．分析和论证了方程组解的存在性和惟一性等重要性质，证明了算法很好的整体收敛性，最后对算法进行了初步的数值试验。     

一般单调变分不等式的近似邻近外梯度算法

近似邻近点算法是求解单调变分不等式的一个有效方法,该算法通过解决一系列强单调子问题,产生近似邻近点序列来逼近变分不等式的解,而外梯度算法则通过每次迭代中增加一个投影来克服一般投影算法限制太强的缺点,但它们均未能改变迭代步骤中不规则闭凸区域上投影难计算的问题.于是,本文结合外梯度算法的迭代格式,构造包含原投影区域的半空间,将投影建立在半空间上,简化了投影的求解过程,并对新的邻近点序列作相应限制,使得改进的算法具有较好的收敛性.     

求解单调变分不等式的两类迭代算法

给出了求解单调变分不等式的两类迭代算法．通过解强单调变分不等式子问题,产生两个迭代点列,都弱收敛到变分不等式的解．最后,给出了这两类新算法的收敛性分析．     

一般伪单调变分不等式的改进投影算法

本文基于算子的分裂技巧给出了解一般伪单调变分不等式几种新的投影算法，包括三步和走步迭代算法．在算子T是g-伪单调和g-Lipschitz连续的条件下，即可证明新提出算法的收敛性．     

一类单调变分不等式的非精确交替方向法

交替方向法适合于求解大规模问题.该文对于一类变分不等式提出了一种新的交替方向法.在每步迭代计算中,新方法提出了易于计算的子问题,该子问题由强单调的线性变分不等式和良态的非线性方程系统构成.基于子问题的精确求解,该文证明了算法的收敛性.进一步,又提出了一类非精确交替方向法,每步迭代计算只需非精确求解子问题.在一定的非精确条件下,算法的收敛性得以证明.     

单调变分不等式可行与非可行点组合的连续算法

本文给出了单调变分不等式问题一个新的连续型求解方法，方法的实现依赖于一系列含有四个参数的摄动单调变分不等式的求解．其中摄动参数要求的条件较为温和，这使得本文方法成为可行点与非可行点算法的有机组合和统一．在适当的假设条件下，我们分析和证明了摄动变分不等式问题解的存在性，唯一性和算法的强收敛性．     

求解伪单调变分不等式的两种投影算法

本文提出了两种求解伪单调变分不等式的定步长的投影算法．这与Solodov ＆ Tseng(1996)和He(1997)的变步长策略不同．我们证明了算法的全局收敛性，并且还在一定条件下证明了算法的Q-线性收敛性．     

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

§1　Introduction and preliminariesA set T Rn×Rnis called a monotone operator on Rn,if T has the property(x,y) ,(x′,y′)∈T 〈x -x′,y -y′〉≥0 ,where〈·,·〉denotes the inner product on Rn.T is maximal if(considered as a graph) itis not strictly contained in any other monotone operator on Rn.It is well known that thetheory of maximal monotone operators plays an important role in the study of convexprogramming and variational inequalities since itcan provide a powerful general framework…     

DC函数优化问题的非精确邻近点算法

本文对DC函数(即两凸函数之差)的最小化问题提出了一个非精确邻近点算法,并证明此算法的下降性和全局收敛性.     

PPA BASED PREDICTION-CORRECTION METHODS FOR MONOTONE VARIATIONAL INEQUALITIES

In this paper we study the proximal point algorithm (PPA) based prediction-correction (PC) methods for monotone variational inequalities. Each iteration of these methods consists of a prediction and a correction. The predictors are produced by inexact PPA steps. The new iterates are then updated by a correction using the PPA formula. We present two profit functions which serve two purposes: First we show that the profit functions are tight lower bounds of the improvements obtained in each iteration. Based on this conclusion we obtain the convergence inexactness restrictions for the prediction step. Second we show that the profit functions are quadratically dependent upon the step lengths, thus the optimal step lengths are obtained in the correction step. In the last part of the paper we compare the strengths of different methods based on their inexactness restrictions.     

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

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

求解广义混合单调变分不等式的预解算子方法

1引言设R~n表示n维欧式空间,‖·‖和＜,＞分别表示R~n中的范数和内积,K为R~n中的非空闭凸集,(?)是R~n到R∪{ ∞)的算子．对于给定的非线性算子T,g：R~n→R~n,考虑下面的广义混合变分不等式,记为GMVI：求u∈R~n满足(Tu)~T(g(v)-g(tu)) (?)(g(v))-(?)(g(u))(?)0,(?)g(v)∈R~n．(1)假如(?)是R~n中非空闭凸集K的指标集,即,(?)(u)≡I_k(u)=(?)．此时GMVI等价于下面的广义变分不等式：求u∈R~n,g(u)∈K满足     

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

引入和研究了一类新的广义非线性变分包含．在Hilbert空间中利用与极大η-单调映象相联系的预解算子的性质，对新的广义非线性变分包含建立了一个新的寻求近似解的带误差的近似点算法，并证明了求近似解序列强收敛于精确解．其所得结果是近期相关结果的改进和推广．     

A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS*

We present a unified framework for the design and convergence analysis of a class of algorithms based on approximate solution of proximal point subproblems. Our development further enhances the constructive approximation approach of the recently proposed hybrid projection–proximal and extragradient–proximal methods. Specifically, we introduce an even more flexible error tolerance criterion, as well as provide a unified view of these two algorithms. Our general method possesses global convergence and local (super)linear rate of convergence under standard assumptions, while using a constructive approximation criterion suitable for a number of specific implementations. For example, we show that close to a regular solution of a monotone system of semismooth equations, two Newton iterations are sufficient to solve the proximal subproblem within the required error tolerance. Such systems of equations arise naturally when reformulating the nonlinear complementarity problem.

     

A MODIFIED VARIABLE-PENALTY ALTERNATING DIRECTIONS METHOD FOR MONOTONE VARIATIONAL INEQUALITIES

Alternating directions method is one of the approaches for solving linearly constrained separate monotone variational inequalities. Experience on applications has shown that the number of iteration significantly depends on the penalty for the system of linearly constrained equations and therefore the method with variable penalties is advantageous in practice. In this paper, we extend the Kontogiorgis and Meyer method [12] by removing the monotonicity assumption on the variable penalty matrices. Moreover, we introduce a self-adaptive rule that leads the method to be more efficient and insensitive for various initial penalties. Numerical results for a class of Fermat-Weber problems show that the modified method and its self-adaptive technique are proper and necessary in practice.     

GLOBAL CONVERGENCE OF A TRUST REGION ALGORITHM USING INEXACT GRADIENT FOR EQUALITY-CONSTRAINED OPTIMIZATION

1 IntroductionIn this papert we study following nonlinear equlity-constrained optimization problem,where C(x) = (of(x), c200,' t c.(x))"(m 5 n), f, ci: R" -- R are at least twice contimuouslydifferentiable, AC(~) has fllll column rank in the range of interest.There are many trust-region algorithms for problem (1.1), (see [11,[2],[5]), these papershave a same point that is using exact gradient informations, but it is in realistic application.[3] and [41 give a trust region algorithm using i…     

ON THE MONOTONE CONVERGENCE OF THE PROJECTED ITERATION METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS

Under suitable conditions,the monotone convergence about the projected iteration method for solving linear complementarity problem is proved and the influence of the involved parameter matrix on the convergence rate of this method is investigated.