论文摘要
最优化理论与算法是一门广泛应用的学科,它主要讨论决策问题的最佳选择之特性,并构造寻求最佳的计算方法,以及研究这些计算方法的理论性质和实际计算效果。数学规划是最优化理论的一个重要分支,和其它数学分支相比,它是一门非常年轻但又十分活跃的应用数学分支。而互补问题又是另外一类相当广泛的数学模型。事实上,许多实际问题的数学模型其实就是一个特殊的互补问题,并且经典的线性规划问题与非线性问题都可以转化为互补问题来进行求解计算。1947年,Danzig提出了线性规划的概念及其著名的单纯型算法,该算法在实际计算过程中具有良好的计算性能,但从理论上来讲其复杂性并不理想,主要原因是随着问题规模的扩大,算法迭代次数迅速增长,这给实际计算带来很大的麻烦。受计算复杂性理论的影响,很多学者曾在很长一段时间内,希望通过证明单纯形法具有多项式时间算法。但是,Klee和Minty在1972年通过举反例,证明了单纯形算法法它并不是一个多项式算法,这样线性规划问题是否存在多项式算法就成为众多学者迫切想知道的问题。接下来,在1979年,Khachiyan针对线性规划问题是否为多项式算法的这一困惑,提出了著名的“椭球算法”,该算法是线性规划的第一个多项式算法,但是此算法的理论上的优势并不能在实际计算性能上超越单纯形算法法,这就引起了众多学者试图再去寻找另外一种新的具有较好实际计算性能的线性规划的多项式算法。直到1984年,Karmarkar的“投影尺度算法”使得线性规划算法出现了真正的突破,这种新算法不仅在理论上优越于单纯形算法,而且也显示出对求解大规模实际问题的巨大潜力。Karmarkar算法再一次真正不同于单纯形算法（单纯性算法是从可行域的一个顶点迭代到另外一个顶点,直到达到问题的最优解）,而Karmarkar算法它是从可行域的内部沿着某个方向逼近问题的最优解,所以有时候也称为“内点算法”。经过众多学者对Karmarkar内点算法的深入探讨与研究,现在已经发展成最具有代表性的有三类：势函数下降投影变换方法（即Karmarkar内点算法）、仿射均衡变换方法和原始-对偶跟踪中心轨迹方法。虽然这三大类内点算法具有很强的计算效果,但是现有可行内点算法也并非完美无缺,其中最突出的问题是,由其计算复杂性分析所得出的多项式时间界限不能作为衡量一个算法好坏的唯一依据,其原因如下：其一,小步长（窄邻域）原始-对偶内点算法的多项式复杂性为O（（?）nlog（n/ε））,远远低于大步长（宽邻域）原始-对偶内点算法的复杂性O（n log（n/ε））.但是在实际的计算效果上,前者计算效果比后者差很多（主要原因是小步长算法较大步长算法极大的限制了步长的选取）。针对这种不一致现象,在90年代,Ye和Huang提出了一种高阶（r阶）预估校正原始-对偶大步长（宽邻域）内点算法,将算法的迭代复杂性降到O（n（r+1）/（2r）L）,其中r∈[1,n)。可以看出,当r=n时,该算法的迭代复杂性近似变为O（√nL）。而其他基于高阶内点算法来降低大步长（宽邻域）原始-对偶内点算法的工作也有一些。比如,Peng等人通过定义自正则（Self-Regular）邻近度量,用这种新的分析工具将大步长（宽邻域）内点算法的多项式时间复杂性降低到O（nq+1/2qlog（n/ε））其中q>1。2006年,Pan等人通过分析发现,上述自正则邻近度量方法在证明上面的结论时所使用的牛顿方向,是通过对“中心方程”用一个等价的幂等变换得到。虽然这种幂函数变换从代数意义上讲等价的,但是到达最优解的速度却不一样,而且也容易理解。因此,基于适当的代数等价变换,也可以达到降低原始-对偶内点算法的计算复杂性的效果。其二,就是可行内点算法在初始迭代点选取上太过于苛刻,既要满足严格等式约束又要满足非负约束条件,并且在实际问题中这种初始点的选取很难获得,而不可行内点算法却放松了这一条件,只要在迭代开始时满足非负条件,而不再需要满足等式约束。这一放松大大降低了初始可行点在选取上的困难性。因此,不可行内点算法在处理实际问题中被广泛应用。本文主要分为理论和应用两大部分。第一部分（第二章到第五章）,理论部分主要利用优化算法解决一些理论上存在的问题,比如大步长与小步长在迭代与计算复杂性上的矛盾以及初始可行点在选取上的困难等；第二部分（第六、七章）是利用优化算法解决一些实际问题,如利用之前的内点算法中的路径跟踪算法和仿射尺度算法解决双矩阵对策问题以及利用优化问题和演化博弈算法解决农村合作组织中的经济问题,通过编程简单的模拟算法的迭代过程以及最后的稳定状态。在理论部分,首先在前人的研究基础上,将P矩阵线性互补问题高阶内点算法推广到更一般的P.（k）阵高阶线性互补问题中去,并基于不同的邻域（大步长和小步长）讨论了算法的复杂性。其次,基于代数等价变换的思想以及KMM算法的框架,对P0阵线性互补问题提出了新的原始-对偶不可行内点算法。该算法的创新点首先是基于KMM算法的框架,该算法在处理不可行内点算法结构上很简单,其次就是利用一个特殊的代数等价代换,因此在复杂性上较之前的算法有了很大改进,主要体现在代数等价变换上,虽然从代数的角度上是等价的,但是达到最优解的速度却不相同,可以在后面的数值试验中体现出来。最后,在前人的研究基础上,将线性规划问题推广到更一般的互补问题中去,分别讨论了基于核函数求解线性互补问题和非线性互补问题的不可行内点算法并证明了其计算具有多项式复杂性,在讨论非线性互补问题时,在前人研究的基础上,构造了一个新的核函数,利用该函数来衡量算法是否达到最优解,最后证明算法经过次迭代达到问题的最优解。第二部分为应用部分,由于互补问题是一类非常重要的优化问题,它广泛应用在经济分析、交通平衡策略等社会经济模型中。因此,对互补问题的研究具有十分重要的现实意义。所以,本文第六章以博弈论理论为基础,探讨了线性互补问题在经济学中的双矩阵博弈中的应用,并提炼出了两个典型双矩阵博弈实例（囚徒困境博弈和监察博弈）,借鉴线性互补问题中的势函数下降法和中心路径跟踪算法有效的解决了上述实例。其次是利用演化博弈理论和最优化算法探求农村合作组织的合作机制,建立了异质农民群体（具有组织管理才能与影响力的阶层与普通农民阶层）在农村合作组织运行的演化博弈模型,局中人根据前一轮合作的结果,通过模仿或学习调整下一轮是否合作的博弈对策,逐步寻求演化稳定均衡解。为了求出演化稳定均衡解提出了一种新的演化博弈算法。该算法的基本思想是将最优化问题的搜索空间映射到博弈论中的策略组合空间中去,目标函数f映射到博弈论的效用函数,通过不完全理性博弈主体的达到局部稳定均衡状态,根据据局部均衡结果博弈主体调整各自对策,进行下一轮博弈,搜寻到更优的均衡,最终达到演化稳定均衡解,从而求解出实际问题的进化稳定状态。
论文目录
相关论文文献
标签：互补问题论文; 内点算法论文; 多项式复杂性论文; 双矩阵博弈论论文; 纳什均衡论文; 演化博弈论论文; 合作机制论文;