【作者】 李欢；

【导师】 李声杰；

【作者基本信息】 重庆大学 ， 运筹学与控制论， 2016， 硕士

【摘要】 变分不等式问题是优化领域中一类重要的问题,并且在实际生活中,有许多问题都可以转化为变分不等式问题,如凸规划问题,互补问题,不动点问题,交通平衡问题等。目前,对于求解变分不等式问题已经有一系列的算法,如邻近点算法,投影收缩算法,增广拉格朗日法,交替方向法等。这些算法在统计学习,图像处理,交通优化,矩阵优化等领域都有着广泛的应用。随着信息技术的飞速发展,研究具有特殊结构的大规模的问题已发展成为数学规划领域的一个重要研究热点,因而,本文的目的就是设计有效的算法来求解这类特殊问题。基于此,本文的主要研究工作如下:（1）针对可分离结构型变分不等式问题,Chen在参考文献[44]中提出了一种非精确交替方向法。当数据维数非常大的时候,并行分裂算法比交替方向法更为有效,在此基础上,本文提出了一种新的非精确并行分裂算法,并且将其应用到交通平衡问题中。新算法的特点在于求解子变分不等式时采用Jacobi型,并且引入一个非精确项来进行求解,由此得到一个预测步,然后校正预测步中的解,使其逼近于真实解,它也可以称为预测校正法。在合理的假设下,我们给出了算法的收敛性证明,同时数值结果表明了算法的有效性。（2）由于上述非精确交替方向法和新的非精确并行分裂算法有类似的结构,因此提出了一个既具有非精确交替算法又具有非精确并行分裂算法的统一结构的新算法,在合理的假设下我们还证明了算法的收敛性和有效性。（3）仍然考虑在参考文献[44]的基础上,我们将校正步中两个方向d₁（w^k,（?）^k） 和d₂（w^k,（?）^k）通过线性组合为一个新方向,通过校正已得到的预测点,使得预测点更加接近于真实解,并且新算法的收敛性及有效性都得到了证明。更多还原

【Abstract】 Variational inequality（VI） problem is a class of important problems in the field of optimization and many problems, which arise from applications of field, can change to variational inequality problems, such as, convex programming problems,complementarity problems, fixed point problems, and traffic equilibrium problems, etc.Nowadays, there are a series of algorithms for solving variational inequality problems,e.g., proximal point algorithm（PPA）, projection contraction method, augmented Lagrangian method,alternating direction method（ADM）. These algorithms are widely used in handling statistical learning,signal processing, traffic optimization, and matrix optimization.With the rapid development of information technology, studying on large-scale problems with special structure has become an important research hotspot in the fields of mathematical programming. Therefore, the purpose of this paper is to design effective algorithms to solve this kind of special problems. The main research work of this paper is as follows:（1） For variational inequality problem with separable structure, Chen proposed an inexact alternating direction method（IADM） in [44]. When the dimensionality of data is tremendous large, parallel splitting method（PSM） is more efficient than ADM, so based on IADM, we proposed a new inexact parallel splitting method（NIPSM）, and apply it to solve some applications in traffic equilibrium problems. The characteristic of this new algorithm is solving the sub variational inequalities in Jacobi type, and instead of solving the sub-VIs exactly, we add an inexact term to solve them inexactly. Then, we get a predictor and correct them to approximate the sub-VIs’ real solutions. So, it is also a prediction-correction method. Convergence of the new method is proved under mild assumptions and some numerical results demonstrate that the new method NIPSM is efficient.（2） Because of the similar structure between IADM and NIPSM, we propose a new algorithm for solving the unified structure. The convergence and effectiveness of the new method is proved under mild assumptions.（3） Still based on the reference [44], we proposed a new method, which use a linear combination of two directions d₁（w^k,（?）^k） and d₂（w^k,（?）^k） as a new direction in the correction step for correcting the predictor in order to approximate the real solutions.The convergence and effectiveness of the new algorithm are proved.更多还原