一类互补问题基于核函数的原始对偶大步校正内点算法.pdf

三峡大学 硕士学位论文 一类互补问题基于核函数的原始-对偶大步-校正内点算法 姓名：陈华平 申请学位级别：硕士 专业：应用数学 指导教师：张明望 20100501 三 峡 大 学 硕 士 学 位 论 文 II 内 容 摘 要 互补问题是一类广泛应用于经济分析，交通平衡中的数学问题，对它的研究具有 重要的理论价值和现实意义. 内点算法是目前求解各种优化问题的一种有效算法. 自 1984 年，第一个具有实用性的多项式内点算法诞生之日起，内点算法便成为优化领 域研究的热点之一. 经过二十多年的努力, 内点算法已取得了丰硕的成果， 目前许多 内点算法已经成为软件包的核心. 本文讨论一类重要的互补问题— * Pκ( )互补问题，为 * Pκ( )线性互补问题和 * Pκ( ) 非线性互补问题分别设计出了新算法. 基于两个不同的核函数，本文最终证明了这些 新算法在理论上具有良好的多项式迭代复杂性. 全文共分为四章, 具体安排为：第一章介绍了相关的基本知识以及内点算法的研 究概况；第二章为 * Pκ( )线性互补问题设计了两个新的算法，通过借用两个不同的核 函数作为分析工具，本文给出了算法的多项式复杂性分析；第三章将第二章中的第二 个算法推广到 * Pκ( )非线性互补问题上，通过对映射作相对李谱希茨条件假设，本文 最终也证明了新算法的多项式复杂性. 第四章对全文作出总结，并对后续研究进行展 望. 关键词：互补问题 内点算法 大步-校正 核函数 多项式复杂性 关键词：互补问题 内点算法 大步-校正 核函数 多项式复杂性 三 峡 大 学 硕 士 学 位 论 文 III Abstract Complementarity problem is a class of the mathematical problems widely used in economic analysis and traffic equilibrium. Its research has important theoretical value and practical significance. Interior-point algorithm for solving various optimization problems is an efficient algorithm. Since the first practical polynomial interior-point algorithm was presented in 1984, interior-point algorithm has become one of the active areas of research. After 20 years of hard work, interior-point method has achieved fruitful results. At present, some of them have become the base of software package. This article majors in discussing an important class of complementarity proble- ms— * Pκ( ) complementarity problem. New algorithms are designed for * Pκ( ) linear complementarity problem and * Pκ( ) nonlinear complementarity problems, respectively. Based on two different kernel functions, the favorable polynomial iteration complexi ty for new methods is proved. Full-text is divided into four chapters, the concrete contents are arranged as follows. The first chapter introduces the preliminary knowledge and the research situations of the interior point methods. The second chapter designs two new methods for * Pκ( ) linear complementarity. By means of two different kernel functions, it gives the proof of the complexity. The extension of the second algorithm in the second chapter for * Pκ( ) nonlinear complementarity problems is studied in third chapter. With the assumption of the Relative Lipschitz Condition, it obtains the polynomial complexity. Finally, a conclusion and some further researches are made in fourth chapter. Key Words: complementarity problem interior-point algorithm large–update kernel function polynomial complexity 三 峡 大 学 硕 士 学 位 论 文 I 三峡大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果，除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品成果。

对本文的研究做出重要贡献的个人和集体均已在文中以明 确方式标明，本人完全意识到本声明的法律后果由本人承担 学位论文作者签名： 日 期： 三 峡 大 学 硕 士 学 位 论 文 1 引 言 最优化方法是一个重要的数学分支， 它所研究的问题是怎样在众多可行方案中找 出最优方案. 随着计算机技术以及信息技术的飞速发展，这类问题已经普遍存在于社 会生产生活的各个方面. 例如，工程设计参数选取、生产计划安排、资源分配问题、 城市规划、农田规划、军事指挥等，诸如此类，不胜枚举. 互补问题是一类重要的优 化问题，由于系统平衡的概念等同于互补的概念，互补问题被广泛应用于接触力学， 交通平衡，最优控制等有关的工程和经济领域. 此外，凸规划问题也可以转化为互补 问题求解. 因此，对互补问题的研究无论是从理论上还是从实际应用方面都有着十分 重要的意义. 内点算法是在二十世纪八十年代广泛兴起的一类有效算法. 自 1984 年 N.Karmar -kar 为线性规划提出了一个著名的多项式内点算法—梯度投影算法[1]以来，内点算法 便成为优化领域研究的热点之一. 经过二十多年的研究，内点算法已取得了丰硕的成 果， 并已逐渐推广到了各类优化问题. 在各种内点算法中， 原始-对偶内点算法被认为 是最有效的内点算法之一. 然而，经过众多学者多年来的理论研究以及大量的数值实 验表明：这类算法在实际有效性与理论复杂性之间存在着矛盾，即有着良好实际计算 效果的大步校正（宽邻域）算法在理论上却有着较小步校正（窄邻域）算法更差的理 论复杂性. 为了解决这个矛盾，一些大步校正算法被相继提出. 二十一世纪初，在以 加拿大籍华人 J.Peng 等学者的共同努力下，新的算法及分析工具[2-4]应运而生，大步 校正算法的理论复杂性也有了很大程度的改善. 本文正是基于文献[4]中算法的思想，将线性规划基于核函数的原始-对偶大步校 正内点算法推广到一类特殊的互补问题— * Pκ( )互补问题上. 由于线性互补问题是线性规划的直接推广，并且相应理论比较成熟，因此，本文 在第二部分为 * Pκ( )线性互补问题设计了两个算法：第一个算法是基于带参数的有限 核函数的大步校正内点算法， 该算法最终得到了线性互补问题目前已知的最好迭代复 杂性；对于第二个算法，我们则选择了另外一个带参数的有理函数作为核函数，该函 数不仅包括了经典的对数障碍核函数和增长项为二次的经典自正则核函数作为特殊 情况，而且也包含了一大类非自正则核函数. 模型的改变使得算法的迭代方向不在具 有正交性，因此算法分析较线性规划更为复杂. 在第三部分中，我们将上一部分的第二个算法推广到非线性互补问题上. 模型的 一般性使得相应算法的分析较线性互补问题更为困难. 在假设映射满足相对李谱希 茨条件（Relative Lipschitz Condition）下，通过一些新的分析技巧，本文最终证明了 三 峡 大 学 硕 士 学 位 论 文 2 将第二个算法推广到 * Pκ( )非线性互补问题是可行的，并且也得到了类似的多项式复 杂性. 由于非线性互补问题是更一般的数学模型，对它的研究较少，除了文献[3]给出 了一个基于自正则核函数的内点算法外，未见其他的基于核函数的内点算法提出. 鉴 于该算法中的核函数也包含了一类非自正则函数， 因此本算法可视为是将非自正则核 函数推广到非线性互补问题的第一个算法，具有重要的理论意义及研究价值. 三 峡 大 学 硕 士 学 位 论 文 3 1 绪论 1.1 互补问题的介绍 互补问题最初是由 Howson 于 1963 年提出来的. 1964 年，数学规划的创始人 G.B.Dantzig 的学生 R.cottle 在其博士论文里第一次提出了求解它的非线性规划算法， 由此互补问题的研究才开始得到发展. 直至发现了它与一个重要的问题—变分不等 式的密切关系之后，人们才掀起对互补问题的研究热潮（见文献[5-7]）. 随后，互补 问题变成了一种备受关注的新的数学模型， 这种模型所包含的两种决策变量之间满足 一种互补关系，这种关系不仅反映了一种普遍存在的现象，更体现了数学之美. 通常的互补问题是指：寻求向量( , ) nn x sRR∈×，满足： ( ),sf x= 0, T x s = 0,x ≥ 0s ≥， (1.1) 其中( ): nn f xRR→是一个可微映射. 通常称0 T x s =为互补条件，记(1.1)的严格可行 域为： 0 {( , ):( )} nn x sRRsf x ++++ =∈×=F. 根据映射( )f x的不同，可将互补问题分为两大类：当( )f x是线性映射，即 ( )f xMxq=+，问题(1.1)为线性互补问题；当( )f x是非线性映射时，问题(1.1)即为非 线性互补问题. 对这两大互补问题作一些扩展，则互补问题又可以细化为：水平线性 互补问题， 垂直线性互补问题， 混合互补问题等[8,9]. 有着广泛用途的变分不等式则是 非线性互补问题的又一个形式的重要扩展，见文献[10]. 随着生产生活的日趋进步，互补问题的应用也日显突出. 近几十年来，互补问题 的理论与算法也取得长足的进展，就算法而言，取得的成果已经相当丰富，如连续化 算法，光滑（非光滑）方程算法[11]，信赖域算法，投影收缩法[12,13]，内点法等. 其中， 内点法是求解大规模互补问题的一种有效算法. 随着计算科学的进步，用内点法求解 大规模互补问题已显示出其巨大潜力. 1.2 内点算法的发展及研究概况 内点算法的探索源于人们对线性规划的单纯形算法的理论研究. 在1984年以前， 由美国学者G.Dantzig[14]提出的单纯形法一直是求解线性规划的有力工具. 之后，随 着计算机科学的日益应用，。