《蔡晓璇 非线性互补问题(终稿)》由会员分享，可在线阅读，更多相关《蔡晓璇 非线性互补问题(终稿)（13页珍藏版）》请在金锄头文库上搜索。
1、 摘要非线性互补问题是运筹学与计算数学的一个交叉领域，它与非线性规划、对策论、不动点理论等分支有紧密联系.本文概述了非线性互补问题的来源、发展历程和目前的研究现状，重点介绍了求解非线性互补问题的数值方法，如不动点迭代法、投影法、内点法、光滑方程法等，并通过数值例子验证了不动点迭代法的有效性。关键词：非线性互补问题；不动点迭代法；投影法；内点法； 非线性互补问题及其常见解法1ABSTRACTNonlinear complementarily problem is a cross field of operational research and computational mathematics
2、. 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 probl
3、ems, 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; i
4、nterior point; smoothing equation method 非线性互补问题及其常见解法2目录第一章 绪论1.1 互补问题的介绍.31.2 互补问题的模型.4第二章 不动点的迭代法2.1 不动点迭代法的基本性质.82.2 不动点迭代算法.82.3 数值试验.9第三章 非线性互补问题的其他解法 3.1 可微的无约束优化法.113.2 投影法.113.2 内点法 .11参考文献.13 非线性互补问题及其常见解法3第一章 绪论1.1 互补问题的介绍互补问题是运筹学与计算数学的一个交叉研究领域，与数学规划、经济学、对策论、力学、变分学、随机最优控制等学科关系密切，在科学研究和工程技
5、术各领域有着广泛的应用。互补问题自 20 世纪 60 年代开始发展到现在，无论在理论还是在算法研究上都取得了丰硕的成果。 互补问题的研究又可以分为理论和算法。前者主要研究问题解的存在性、唯一性、稳定性以及灵敏度分析等性质。后者集中研究如何构造有效算法及其理论分析。我们首先给出互补问题的定义：定义 1.1（线性互补问题）：求一点 ，满足nxR0()TFx (1)当 为线性函数时（令 ， ， ）时，称 为线性互补()Fx()MqnRnq()问题。定义 1.2（非线性互补问题）： 求一个 维向量 ，使得：x0x()F (2) T其中， 是： 连续可微。()FxnR互补问题与最优化问题关系密切，最优化
6、中的许多问题都可以转化为互补问题求解，下面分别给出说明。（1）线性规划考虑原始线性规划问题(PLP)： min()FxTc 0;Ab(3) 其中： 。它的对偶问题(DLP)为：,mnnARbcRax(),Thy.0stTAcmyR 非线性互补问题及其常见解法4设 分别是(PLP)和的(DLP)可行解，则 同为最优解的充要条件是：0,xy 0,xyTcb设： ，,() TTxcAAyzfzzybx 则：(),TTTTTcyzfxcbyA在 同为最优解的条件下，可以构造如下的互补问题（LCP）：求 ，使0,xy 0mnzR得, 。0()()mnTfzRzf且是（LCP）的解当且仅当 是（PLP）和
7、（DLP）的最优解。0y0,xy（2）二次规划考虑二次规划问题（QPP）： 1min()2TfxQcx.0stAb (4)其中 。,mmQRcAR引入松弛变量 ，使得 。则由 K-T 条件，存在向量乘子 ，vxv ,mR使得： 0,TmTQcAuxvbuR将上面的条件改成如下形式： ,0TcxQAvb0(),0mnmnuxuRv若令 , TxcxAzfzb则 K-T 条件等价地可以写为：求 使得 且 . 而这正是线性互,mn(),mnfzR()0Tzf补问题的形式. 非线性互补问题及其常见解法5（3）非线性规划考虑非线性规划（NLP） min().01,.ifxstgim其中 ， 连续可微。(
8、)fxig令 1(,)()miLxfugx则由约束最优化的 K-T 条件： 11()()00,()()0miTTmfxxugxxL将上面的式子展开写成： 111(,)(,)(,)(,)nLuuhhxM. (,)(,)(,)(,)nnmnLxuxux若令 ，1,.,Tnzhzh则 K-T 条件等价于：求 , 使得 ,且 这也是互补问题。mnR()mR()0z1.1.2 互补问题的模型生活的各个领域中，线性互补问题的应用十分普遍，本文主要简单的介绍工程力学互补问题模型和供应链互补问题模型。1.1.2.1 工程力学互补问题模型因为在研究经济、工程中的许多现象时会自然地出现互补关系, 所以互补问题广泛
9、地应用于经济，工程技术等各个领域,如在工程中的应用有接触力学问题、断裂力学问题、弹塑性问题、润滑问题、最优控制问题及交通平衡问题等。这里主要讲述互补问题在力学中的部分应用情况。对工程力学问题而言, 其互补关系主要来自于以下三个方面:塑性流动法则、单侧接触定律以及库仑摩擦定律。所以可以将力学中的许多问题用互补模型来表述,如接触问题、弹塑性问题及结构优化问题等。接触问题和弹塑性问题都属于边界 非线性互补问题及其常见解法6待定的变分问题, 对接触类问题, 事先并不能确定可能发生接触的边界哪部分是处于脱离、粘贴或滑动状态; 对弹塑性类问题, 事先无法准确判断出哪部分材料进入到了塑性变形状态。而互补条件
10、恰恰能够自动识别出哪些不等式变为等式, 即对弹塑性问题, 能够自动地确定变形是处于弹性状态还是塑性状态, 对接触问题, 可自动确定接触状态。将力学问题写成互补模型的主要好处是: 一方面是使力学问题有更自然、更精确的数学描述; 另一方面是可以运用互补问题丰富而实用的理论结果, 如可以用解的存在性和唯一性理论来分析力学问题的结构模型, 而且更重要的是能够利用互补问题许多有效和强健的数值算法。1.1.2.2 供应链互补问题模型目前，对供应链问题的研究比较流行的模型是分散式的供应链网络模型。该模型通常包括三层决策者: 制造商、销售商和消费者，它们在商品流通过程中都有自己的目标。随着各种各样的供应链概念
11、和分析模型的出现，对供应链的研究已经引起了越来越多的研究者的注意。与对供应链的建模的研究相比较，对其相应算法的研究却很少。大多数供应链文章是将供应链均衡模型建立为变分不等式模型，然后利用投影方法(或修正的投影方法 ) 求解。 非线性互补问题及其常见解法7第二章 不动点迭代法2.1 不动点迭代法的基本性质不动点迭代法的基本思想:将 NCP(F)转化为一个等价的不动点方程来求解。 nxR，记 , ，其中算子 max 指分量的最大，则有 及1max02ax0, 122则显然 ，而不难发现 , ，令120Tx1()2x21()xx1()U， 21=()FUPp（ ）其中 为常数。则非线性互补问题等价于
12、下面的不动点问题：p11()2pxx于是可以构造不动点迭代格式：1(),0,2.kkkF(5)2.2 不动点迭代算法以下根据迭代格式 给出求解非线性互补问题的一个不动点迭代算法，并在适当的(5)条件下，证明了其算法是收敛的，且数值结果表明这一方法是有效的。算法 1(不动点迭代算法)步骤 1 给定一个初始点 ，精度 以及选择适当 ，0nzR0eps0pk步骤 2 如果 ，则停止min,()kF步骤 3 令 ， ，ax0,kiiyz1,2.,n12(,.,)kkkTnyy步骤 4 1122(),.,.,kkkkkiii nzyzzp步骤 5 k=k+1,转步骤 2; 非线性互补问题及其常见解法8定
13、理 1 若 是一致 函数，即存在一常数 ，对任意点 ，:FnRP0a,xyR存在下标 ，使得 ， 是 Lipschitz 连续的，(,)kxyk()()kkkxyffyxF（Lipschitz 常数为 ），并且满足0240ap则存在 满足 ，此外，由算法 1 产生的序列 收敛于*nzR(5) kz*z证明: 由算法 1 可知，211()2kkkkpzyFy21111()()()4kkkkTkkyFy21()kpay又 1 11mx0,a,kkkkyzzz 因此， 121 2()4k kpz 由 ，20a则 12(1)4p从而，不动点迭代 有唯一解 ,且满足有算法 1 产生的序列收敛于 5*nzR*z2.3 数值实验为了验证算法的有效性，对以下算例进行了数值实验. 算例 1
