变分不等式问题投影收缩算法线搜索策略的改进

发布时间：2019-01-08 13:23

【摘要】：变分不等式问题(VIP)是运筹学中的一个基本问题,同时在经济学、生态学、工程科学和金融学等很多领域具有广泛应用.因此,从上世纪60年代以来,变分不等式问题一直得到了众多研究者的广泛关注,特别是它的数值计算方法.比如人们熟知的算法有牛顿型算法、交替方向法、临近点算法、内点法、神经网络和投影法,其中,投影法以其简单易操作的特点,更是得到了众多学者的青睐,对这类算法的研究层出不穷,何炳生提出的投影收缩算法就是其中的一类.投影收缩算法的特点是,每次的迭代计算量不大,一般是一些函数的简单计算到可行集的投影.而本文的主要工作是对此进行深一步研究,企图构造一种新的投影收缩算法来解决变分不等式问题.具体工作是改进已有的投影收缩法,通过对何炳生的搜索方向进行探索研究来考虑步长的选取,在原来的下降方向的前提下,得到了一个效率更高的步长,进而得到一种新的投影收缩算法来解决变分不等式问题.具体内容安排如下:第一章主要是绪论,首先对变分不等式问题的出现、发展以及其他一些背景知识进行简单的介绍,然后,给出了变分不等式问题和凸集上投影的一些基本概念和结论,接着,介绍了几种常见的求解变分不等式问题的算法,最后,在章末给出了本文内容上的安排工作.第二章首先给出了关于变分不等式问题的几个不等式以及南京大学何炳生老师所提出的投影收缩算法的基本思想.其次,结合师兄王金龙的论文,对投影收缩算法的机理进行了分析,提出了改进线搜索策略的投影收缩算法,在原问题有解且向量值函数F单调的假设下,证明了新算法的全局收敛性.最后通过几个算例,对改进前后的两种算法的数值实验结果进行了对比,验证了改进后的算法效率更高.第三章是对本文所做工作的总体分析和评价,并对下一步研究工作进行梳理和展望.
[Abstract]:Variational inequality problem (VIP) is a basic problem in operational research and has been widely used in many fields such as economics, ecology, engineering science and finance. Therefore, since the 1960s, variational inequality has been widely concerned by many researchers, especially its numerical method. For example, the well-known algorithms are Newton algorithm, alternating direction method, proximity point algorithm, interior point method, neural network and projection method. Among them, projection method is favored by many scholars because of its simple and easy to operate. There are many researches on this kind of algorithm, among which he Bingsheng's projection contraction algorithm is one of them. The characteristic of the projection contraction algorithm is that the computation of each iteration is small, and it is usually the projection from some simple functions to the feasible set. The main work of this paper is to study this problem one step further and try to construct a new projection contraction algorithm to solve the variational inequality problem. The specific work is to improve the existing projection contraction method, by exploring the search direction of he Bingsheng to consider the selection of step size. Under the premise of the original descent direction, a more efficient step is obtained. Then a new projection contraction algorithm is proposed to solve the variational inequality problem. The main contents are as follows: the first chapter is an introduction to the emergence, development and other background knowledge of variational inequalities. Some basic concepts and conclusions of variational inequality problems and projection on convex sets are given. Then, several common algorithms for solving variational inequality problems are introduced. At the end of the chapter, the arrangement work of this paper is given. In the second chapter, some inequalities about variational inequalities and the basic idea of projection contraction algorithm proposed by he Bingsheng of Nanjing University are given. Secondly, combining with Wang Jinlong's paper, the mechanism of projection contraction algorithm is analyzed, and a projection contraction algorithm with improved line search strategy is proposed. Under the assumption that the original problem is solved and the vector value function F is monotone, The global convergence of the new algorithm is proved. Finally, several examples are given to compare the numerical results of the two algorithms before and after the improvement, which proves that the improved algorithm is more efficient. The third chapter is the overall analysis and evaluation of the work done in this paper.
【学位授予单位】：内蒙古工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O22

【参考文献】