蔡晓璇 非线性互补问题(终稿).doc

非线性互补问题及其常见解法 摘要 非线性互补问题是运筹学与计算数学的一个交叉领域，它与非线性规划、对策论、不动点理论等分支有紧密联系.本文概述了非线性互补问题的来源、发展历程和目前的研究现状，重点介绍了求解非线性互补问题的数值方法，如不动点迭代法、投影法、内点法、光滑方程法等，并通过数值例子验证了不动点迭代法的有效性。 关键词：非线性互补问题；不动点迭代法；投影法；内点法；ABSTRACT Nonlinear complementarily problem is a cross field of operational research and computational mathematics. It has close relationship with nonlinear programming, game theory, fixed point theory and so no. In this paper, we present the origin of the nonlinear complementarily problem, its development and current research situation. We stress the numerical method for solving nonlinear complementarily problems, such as fixed point iteration method, the projection method, interior point and smoothing equation method. And we give some numerical result to test the effectiveness of fixed point iteration method.KEY WORDS: nonlinear complementarily problem; fixed point iteration method; projection method; interior point; smoothing equation method 目录第一章 绪论1.1互补问题的介绍.31.2互补问题的模型.4第二章 不动点的迭代法2.1 不动点迭代法的基本性质.82.2 不动点迭代算法.82.3 数值试验.9第三章 非线性互补问题的其他解法 3.1可微的无约束优化法.113.2 投影法.113.2 内点法 .11参考文献.13第一章 绪论1.1 互补问题的介绍互补问题是运筹学与计算数学的一个交叉研究领域，与数学规划、经济学、对策论、力学、变分学、随机最优控制等学科关系密切，在科学研究和工程技术各领域有着广泛的应用。互补问题自20世纪60年代开始发展到现在，无论在理论还是在算法研究上都取得了丰硕的成果。 互补问题的研究又可以分为理论和算法。前者主要研究问题解的存在性、唯一性、稳定性以及灵敏度分析等性质。后者集中研究如何构造有效算法及其理论分析。我们首先给出互补问题的定义：定义1.1（线性互补问题）：求一点，满足 当为线性函数时（令，）时，称为线性互补问题。定义1.2（非线性互补问题）： 求一个维向量，使得： 其中，是：连续可微。 互补问题与最优化问题关系密切，最优化中的许多问题都可以转化为互补问题求解，下面分别给出说明。（1）线性规划 考虑原始线性规划问题(PLP)： 其中：。它的对偶问题(DLP)为： 设分别是(PLP)和的(DLP)可行解，则同为最优解的充要条件是：设： ，则： 在同为最优解的条件下，可以构造如下的互补问题（LCP）：求，使得,。是（LCP）的解当且仅当是（PLP）和（DLP）的最优解。（2）二次规划考虑二次规划问题（QPP）： 其中。 引入松弛变量，使得。则由K-T条件，存在向量乘子，使得：将上面的条件改成如下形式：若令 则K-T条件等价地可以写为：求使得且. 而这正是线性互补问题的形式.（3）非线性规划考虑非线性规划（NLP）其中，连续可微。令则由约束最优化的K-T条件：将上面的式子展开写成：. 若令 ，则K-T条件等价于：求,使得,且这也是互补问题。1.1.2 互补问题的模型 生活的各个领域中，线性互补问题的应用十分普遍，本文主要简单的介绍工程力学互补问题模型和供应链互补问题模型。1.1.2.1工程力学互补问题模型因为在研究经济、工程中的许多现象时会自然地出现互补关系, 所以互补问题广泛地应用于经济，工程技术等各个领域,如在工程中的应用有接触力学问题、断裂力学问题、弹塑性问题、润滑问题、最优控制问题及交通平衡问题等。这里主要讲述互补问题在力学中的部分应用情况。对工程力学问题而言, 其互补关系主要来自于以下三个方面:塑性流动法则、单侧接触定律以及库仑摩擦定律。所以可以将力学中的许多问题用互补模型来表述,如接触问题、弹塑性问题及结构优化问题等。接触问题和弹塑性问题都属于边界待定的变分问题, 对接触类问题, 事先并不能确定可能发生接触的边界哪部分是处于脱离、粘贴或滑动状态; 对弹塑性类问题, 事先无法准确判断出哪部分材料进入到了塑性变形状态。而互补条件恰恰能够自动识别出哪些不等式变为等式, 即对弹塑性问题, 能够自动地确定变形是处于弹性状态还是塑性状态, 对接触问题, 可自动确定接触状态。将力学问题写成互补模型的主要好处是: 一方面是使力学问题有更自然、更精确的数学描述; 另一方面是可以运用互补问题丰富而实用的理论结果, 如可以用解的存在性和唯一性理论来分析力学问题的结构模型, 而且更重要的是能够利用互补问题许多有效和强健的数值算法。1.1.2.2供应链互补问题模型目前，对供应链问题的研究比较流行的模型是分散式的供应链网络模型。该模型通常包括三层决策者: 制造商、销售商和消费者，它们在商品流通过程中都有自己的目标。随着各种各样的供应链概念和分析模型的出现，对供应链的研究已经引起了越来越多的研究者的注意。与对供应链的建模的研究相比较，对其相应算法的研究却很少。大多数供应链文章是将供应链均衡模型建立为变分不等式模型，然后利用投影方法(或修正的投影方法) 求解。第二章 不动点迭代法2.1 不动点迭代法的基本性质不动点迭代法的基本思想:将NCP(F)转化为一个等价的不动点方程来求解。，记,，其中算子max指分量的最大，则有及则显然，而不难发现, ，令，其中为常数。则非线性互补问题等价于下面的不动点问题： 于是可以构造不动点迭代格式： 2.2 不动点迭代算法以下根据迭代格式给出求解非线性互补问题的一个不动点迭代算法，并在适当的条件下，证明了其算法是收敛的，且数值结果表明这一方法是有效的。算法1(不动点迭代算法)步骤1 给定一个初始点，精度以及选择适当，步骤2 如果，则停止步骤3 令，步骤4 步骤5 k=k+1,转步骤2;定理1 若是一致函数，即存在一常数，对任意点，存在下标，使得，是Lipschitz连续的，（Lipschitz常数为），并且满足 则存在满足，此外，由算法1产生的序列收敛于证明: 由算法1 可知， 又 因此， 由 ，则 从而，不动点迭代有唯一解,且满足有算法1产生的序列收敛于 2.3 数值实验为了验证算法的有效性，对以下算例进行了数值实验. 算例1 实验函数为 这个例子在上有唯一解对于不同的初始点，数值结果如表1；对于相同的初始点，数值结果如表2；表1 算例1的数值结果（） 初始值 参数迭代次数k0.053760.37440.4640.054370,37450,4640.053770.37450.464表2 算例1的数值结果参数迭代次数k0.00542000.12000.3570.35440.375430.38460.464综合表1和表2可以看出，当参数0.37时，不同初始值的收敛性和收敛速度都是较好的.第三章 非线性互补问题的其他常见的解法 上一章介绍了非线性互补问题不动点迭代法，本章主要介绍非线性互补问题其他几种常见的解法，如可微的无约束优化法，投影法和内点法，这对于以后我们研究非线性互补问题有很大的帮助。3.1 可微的无约束优化法 这是把互补问题转化为一个与之等价的可微无约束优化问题，然后用某种大范围或Newton类型法求解由于无约束优化法较为成熟，因此，对这类方法的研究重心在于如何转化上。给出一个可微的势函数 这里表示2-范数。 称为隐Lagrange函数。定理6 对，且解 实际上，可由可微的函数 并取向量1-范数生成，即得到。定理2 假设F是可微的，且正定，则是的稳定点的充要条件是的一个解。3.2投影法 投影法是求解互补问题的一类基本而又重要的方法。基本迭代格式为：这里 为步长。然而它的收敛性需要是强单调的假设。为此,Korpelevich提出外梯度法， 即它的收敛性仅要求单调且解集不是空集。3.3内点法 内点法是把互补问题转化为一个与之等价的非负约束方程组，然后用Newton类型法求解。现在来考察内点法的基本思想。令，则互补问题(2)可转化为： 这里。显然，是一个带有非负约束的2n阶非线性方程组。当时，仅第二个方程是非线性的，且有特殊形式的表达式。容易证明， 当是函数时,Jacobian矩阵是非奇异的。 因此，在迭代中可取Newton方向为搜索方向。给定点，内点法的一般迭代格式为： 这里是由经过一个微小扰动而得，其目的是调节迭代的收敛速度；为步长，它的取法使新点，且效益函数有一定量的下降。如果在迭代过程中能保证，则称为可行内点法； 否则称为不可行内点法。如果取的自然势函数作为效益函数，则称为路径跟踪法；如果取某种对数函数作为效益函数，则称为降势函数法。内点法的收敛结果大致有：(1)大范围收敛性：若单调，可行集存在内点，那么由内点法产生的迭代点列满足且Q-线性(2)局部超线性收敛：假设单调且可行集存在内点若是的一个极限点且有某种正则性，则超线性收敛于零或。(3)多项式复杂性：若单调且可行集存在内点，那么对可行内点法，最好的复杂性界为；对不可行内点法，最好的复杂性界为。 参考文献：1 陈宝林最优化理论与算法M北京：清华大学出版社，2005：25-432 Rockefeller, R.T., (1970). Convex Analysis. Princeton University Press, Princeton. 3 G. Isa