一种求解非线性互补问题的非精确光滑化牛顿算法可编辑.docx
- 文档编号:9186288
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:30
- 大小:34.86KB
一种求解非线性互补问题的非精确光滑化牛顿算法可编辑.docx
《一种求解非线性互补问题的非精确光滑化牛顿算法可编辑.docx》由会员分享,可在线阅读,更多相关《一种求解非线性互补问题的非精确光滑化牛顿算法可编辑.docx(30页珍藏版)》请在冰点文库上搜索。
一种求解非线性互补问题的非精确光滑化牛顿算法可编辑
一种求解非线性互补问题的非精确光滑化牛顿算法(可编辑)
一种求解非线性互补问题的非精确光滑化牛顿算法
AnInexactSmoothingNewtonMethod
forSolvingPq~NCPProblems
学科专业:
计算数学
研宄生:
武彩英
指导教师:
谢伟松副教授
天津大学理学院
二零一三年五月独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研宄工作和取得的研
宄成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表或撰
写过的研宄成果,也不包含为获得天津大学或其他教育机构的学位或证书而使
用过的材料.与我一同工作的同志对本研宄所做的任何贡献均已在论文中作了明
确的说明并表示了谢意学位论文作者签名:
签字日期:
年月日
学位论文版权使用授权书
本学位论文作者完全了解天津大学有关保留、使用学位论文的规定.特授
权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检
索,并采
用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅.同意学校向国家有关
部门或机构送交论文的复印件和磁盘保密的学位论文在解密后适用本授权说明)
学位论文作者签名:
导师签名:
签字日期:
年月日签字日期:
年月日中文摘要
互补问题是运筹学与计算数学的交叉研宄领域.由于与最优化、变分不等式、
平衡问题、对策论、不动点理论等数学分支的紧密联系,以及在实际生活中的广
泛应用,互补问题越来越显示其重要性.本文主要研宄非线性互补问题的非精确
牛顿算法;针对其算法中求解线性子系统的复杂性,提出了求解其近似解的方法,
从而减少计算量.基于光滑牛顿法的基本思想,利用光滑对称扰动FB-函数对光滑
牛顿算法做出了一些改进,提出了一种新的求解PrNCP的非精确光滑Newton算
法然后对该算法进行了细致的收敛性分析,证明过程表明该算法在适当条件下
是全局超线性局部二次收敛的.最后给出了一些利用非精确光滑牛顿算法
求解
非线性互补问题的数值结果.数值结果证明该算法是适定的并且对于大规模
问题
的求解是非常有效的.
关键词:
非线性互补问题;非精确牛顿算法;全局线性收敛;二次收
敛.Abstract
ThecomplementarityproblemisaninterdisciplinaryresearchareaofOp?
erationsResearchandComputationalMathematics.Becauseitsclosecontact
withthebranchesofmathematicsoptimization,variationalinequalities,balance
problems,gametheory,fixedpointtheoryandextensiveapplications,thecomple?
mentarityproblembecamemoreandmoreimportant.Inthispaper,aninexact
smoothingNewtonmethodforsolvingthenonlinearcomplementarityproblem
wasdeveloped.Thismethodwasbasedonasmoothsymmetricperturbation
FischerBurmeisterfunctionandaimedtoovercomethecomplexityofthelinear
subsystemswithreducingcomputationforobtainingtheapproximatesolutionof
NCP.Thenewalgorithmperformedglobalandsuperlinearconvergencewithout
strictcomplementarityundermildconditions.Furthermore,numericalexperi?
mentsdemonstratedthefeasibilityandhighefficiencyofthenewalgorithmfor
solvinglarge-scaleproblems.
KeyWords:
Nonlinearcomplementarityproblems;SmoothingNewtonmethod;
Globalconvergence;Superlinearconvergence;Quadraticconvergence.目录
第一章绪论.1
1.1前言.1
1.1.1互补问题的引入1
112应用背景1
12本文主要工作4
第二章非线性互补问题的基本理论5
2.1基本概念5
22非线性互补问题的解的存在性、唯一性和解集的有界性6
221相关定义6
222解的存在性、唯一性和解集的有界性..8第三章求解NCP问题的几种常见算法.1431投影方法14
32光滑化牛顿方法..15
33非光滑化牛顿方法.17
第四章求解NCP问题的非精确光滑牛顿算法194.1预备知识19
42非精确牛顿算法..21
43算法的收敛性分析.25
44数值结果26
第五章总结与展望31
参考文献.32
发表论文和科研情况说明.35
?
M36第一章绪论
第一章绪论
1.1前言
111互补问题的引入
互补问题是指这样的问题,即寻求向量;xGRn,使其满足:
x0,Fx0,xTFx01-1其中,F:
R+^Rn为由R++到Rn的一映射.若FxMx+q,其中GRnxn,qGRn,贝丨JI-I为线性互补
问题,记
为LCPM^;否则为非线性互补问题,记为NCPF.
互补问题的一个自然引入就是变分不等式问题.互补问题和变分不等式问题
是相伴而产生的,在第二章中会详细说明两者之间的关系112应用背景
互补问题是一类重要的优化问题,在许多部门和领域有着广泛的应用,如
1.具有生产和投资的经济模型
考虑具有生产和投资的竞争经济模型设有m种商品和n种经济活动,令p
piGRm表示商品的价格矢量,Pi是商品i的价格,bbiGRm表示投资矢量,
b是对商品的初始投资.dpdipGRm表示市场需求函数,表p是在价格p条
件下对商品i的需求量.yyjGRn表示活动水平矢量,yj是活动j+的水平,这是
一未知量CCiG尺”表示活动的单位运行费用矢量,Cj是活动j+的单位运行费
用A[aij]GRmxn表示投入产出系数矩阵,aij0表示产出,叫0表示投入
假设函数式p是连续可微的非线性函数,价格矢量p*和活动水平矢量y*被称为是
一‘‘均衡”,如果p*,y*满足:
1c-Atp*0,即活动不可能有正的收益;
2b+Ay*-dp*0,即对商品没有过量的需求;
3P*0,y*0;
4c-ATp*y*0,即不运行可导致亏损的活动;
1第一章绪论
5p*Tb+Ay*-dp*0,即过量供应商品的价格为零,且商品有正的
价格意味着市场缺乏此种商品这一均衡问题组成如下的非线性互补问题:
c一Atp
y
1-2
z
fz
b+Ay一dp
p
求z*GR++m,满足fz*GR++m,z*Tfz*0.
2.静态交通流均衡问题
这里我们考虑的静态交通流均衡问题是要预测一个拥挤的交通网络中平稳状
态下的交通流量.令#表示交通网络的全部结点的集合,A表示网络的全部有向弧
的集合.假设交通网络的使用人对于道路的选择有非合作的竞争,目的是减少其同
行费用令fb表示弧b上的流量,ffb,bGA表示流量矢量令Caf表示弧a的
通行费用,它是矢量f的非线性函数,cfCaf,aGA表示费用矢量令
O表
示交通网络的全部起点的集合,D表示网络的全部终点的集合,显然有OCN,
DCN令W表示某些“起点-终点对”组成的集合,即WCOXD.对于任
一GW,以凡表示连接^的起点和终点的所有路径的集合,令pLUwP?
如图1-1中的连接起点ai和终点^的路径集Pu含有两条路径,用粗线表示.对于
图1-1路径集Pi:
任意一路径pGP,以hp表示p上的流量,hhp,pGP表示路上的流量矢量
令Cph表示p上的通行费,它是矢量h的一函数,ChCph,pG尸表示通行
费矢量对于任意^GW,以^表示^的起点和终点之间的路径的最小通行费,它
是未知量,uUiv?
GW表示全部最小通行费矢量令d?
u表示^的起点和终
2第一章绪论
点之间的通行需求量,它是u的一函数.一般的交通需求模型是“弹性需求”,即
函数心U不是一常数令A表示“弧一路”关联矩阵,其中
J1,如弧a在路p上,aGA,pGP
ap:
t0,其他
显然矩阵A满足/Ah,通常假设路径通行费函数C九有“可加性”,即对任意
路pGP,Cph是:
p上的所有弧a的通行费用Ca/之和.可加性可表示成公式
ChAtc/AtcAh
Wardrop用户均衡原则是研宄交通均衡问题的一个基础,它提出:
交通网络的使用
人在起点与终点之间选择通行费用最小的路径,通行费用较高的路径将没有交通
流Wardrop原则可表示为:
CpK0,hp0,hTCph-Uw01-3
静态交通流均衡问题是:
寻求一流量矢量h和最小通行费用矢量u,使得h和u满足
条件1-3及条件
hpdwu,Uw0.VwGW1-4
p?
Pw
我们称满足条件1-3和1-4的解h,M为一”交通网络均衡”.静态交通均衡问题
在某些合理的假设条件下转化为一非线性互补问题定义映射F为:
1-5
fM:
I
Uh一du
其中n[?
Wp]是“路径一起点终点对”的关联矩阵,即
1,如弧pGPw:
!
0,其他
我们可以证明:
如Cj3K0,dwu0,VpGP,uGW,
含关系
^hpCph0,hhp0今hp0,VpGPw1-6
p?
Pw
则静态交通流均衡问题等价于非线性互补问题ncpf.
除了这两个典型的应用之外,非线性互补问题还广泛应用于障碍和自由边界
问题、供应链问题等3第一章绪论
12本文主要工作
本文主要研宄非线性互补问题的非精确牛顿算法;针对其算法中求解线性子
系统的复杂性,提出了求解其近似解的方法,以达到减少计算量的目的.基于光
滑牛顿法的基本思想,利用光滑对称扰动FB-函数对光滑牛顿算法做出了一些改
进,提出了一种新的求解PrNCP的非精确光滑Newton算法.然后对该算法进行
了细致的收敛性分析,分析表明该算法在适当条件下是全局超线性局部二次收
敛的.最后给出了一些利用非精确光滑牛顿算法求解非线性互补问题的的实
例及
其数值结果具体地说,本文的主要内容包括以下几方面.第一章首先引入互补问题及其
应用背景第二章详细介绍了非线性互补问题的基本性质和理论,主要是非线性
互补问题的解的存在性、唯一性和有界性定理.第三章给出了几种求解非线性互
补问题的基本方法,包括投影法、光滑化Newton方法和非光滑化Newton法.第
四章基于光滑对称扰动FB-函数对光滑牛顿算法做出了一些改进,提出了一种求
解PrNCP的非精确Newton算法并证明了该算法在适当条件是全局超线性二
次收敛的.最后给出了利用非精确光滑牛顿算法求解一类非线性互补问题的过
程和一些实例的数值结果第五章对全文进行了简单的总结,并对本课题的研宄
前景进行了展望4第二章非线性互补问题的基本理论
第二章非线性互补问题的基本理论
2.1基本概念
对于一个给定的互补问题,它是否有解,是否有唯一解或其他性质,往往是不
容易弄清楚的关于互补问题的解的存在唯一性、解集的有界性、误差界以及
其
他的有关问题,以往的文献中已有了广泛的研宄.这些定性研宄阐述了不同的互
补问题的特征,也成为设计求解不同互补问题的算法的理论基础.这一章我们叙
述一些基本的理论结果WRn表示n维欧氏空间,Rn*的矢量或点均为列向量,aT表示矢量a的转
置,aTb表示矢量a与b的内积,R++表示Rn中的非负象限,即R++xGRn|x0,
R++xGRn|x0.本章中涉及的矢量模与矩阵模Il?
II,如不特别说明,均指
欧氏模.
定义2.1令F:
R+^Rn为由R+^l」Rn的一映射,相应的互补问题可以表
示为:
求;rGRn,使得
x0,Fx0,2-1
xTFx0
2-2
记为CPF.称满足不等式2-1的点为互补问题CPF的“可行点”;称满足不
等式;x0和Fx0的点为CPF的“严格可行点”;称满足2-1和2-2的点
为CPF的“解”所有可行点的集合记为FEAF,所有解的集合记为SOLF特别地,如果映射FxMx+q,其中MGRnxn为一nxn实数矩阵,qGRnS
一n维矢量,则称互补问题为线性互补问题,表示为LCPMj.如果F为一非线性
映射,则称互补问题为非线性互补问题,表示为NCPF.给定一互补问题CPF,
它可能没有可行点,即不等式2-1无解;或虽有可行点,但没有解.如果可行点
集FEAF为非空的,则称此CPF是可行的如果解集SOLF是非空的,则称
此CPF是可解的5第二章非线性互补问题的基本理论
22非线性互补问题的解的存在性、唯一性和解集的有界性
221相关定义
由定义2.1,与一般映射F:
R+^Rn相对应的互补问题CPF是:
求;rG
Rn,使得
x0,Fx0,xTFx02-3
众所周知,当F是线性映射时,由于线性互补问题和二次规划的特殊联系,我
们可以利用二次规划及其相关理论来研宄线性互补问题的解的存在性、唯一
性和
解的其他性质而当F为非线性映射时,所对应的非线性互补问题,CPF可以没
有解这说明线性互补问题的解的性质不一定能推广到非线性互补问题,其解的
存在性和唯一性的研宄也不能借助于二次规划,但是基于变分不等式和互补问题
的关系,在研宄非线性互补问题的解的存在性和唯一性时,常常需要借助变分不
等式这一有效工具以下给出变分不等式的定义及其与互补问题的关系.
定义2.2给定非空闭凸集SGRn及向量函数F:
Rn^Rn,变分不等式问
题即求向量;xGS满足如下不等式:
Fx,y一xO,yGS2-4
由凸集夕的法锥Nsx的定义,式2-4可表示为
0GFx+Nsx2-5
式2-5可看成求解点集映射F+Nsx:
Rn^Rn的零点,因此,变分不等式问
题也被称为广义方程当映射F恰为某个可微函数:
Rn^R的梯度映射:
Rn^Rn时,式2-5变为
0G^fx+Nex
故由切锥的必要性条件,式2-4表示在凸集S上求函数^的最小值的最优性条件
特别地,当^为凸函数时,该极值问题与变分不等式问题2-4等价变分不等式问题2-4中特别重要的是集合S为如下长方体的情形
SxGRn|ZixiUi,i1,…,n2-6
6第二章非线性互补问题的基本理论
其中,liG[一^,+to且UiG一^,+to],i1,,n.特别地,当L一to或Ui
+to时,IiXi与:
xUi分别意味着-toXi及Xi+to.因此,一般来说,长方
体不只限于有界长方体.另外,由于当-TOliUi+to时,变量而可视为常数,
以下总假定IiUi.以下定理说明,在长方体上定义的变分不等式问题能够表示
成各个分量的不等式定理2.1设集合S为式2-6所定义的长方体,则变分不等式问题2-4与下
式等价:
对任意iG1,?
n,均有
Fixyi一Xi0,yiG[li,Ui]2-7
其中FxF1X,?
FnxT.
证明:
若式2-7对任意i均成立,贝lJ2-4显然成立反之,假设存在;XGS,
使得式2-4成立,则对每个给定指标i,当向量yGC满足yjXjji
时总
有Fx,y一xFix,yi一Xi0,故式2-7成立对于式2-6所定义
的长方体S,由于必要时可进行适当的变量替换因此,不
失一般性,可假设指标集N1,?
n有如下分解:
NNiuN2UN3
其中Nii|li?
to,Ui+to,N2i|li0,Ui+to,N3i|
一to
liUi+to.于是由式2-7,变分不等式问题2-4可表示如下:
Fix0,iGNi
fXi0,FiX0\,^GN2IXi0今Fix0
h今Fix0
Xi
GNs2-8
liXiUi今Fix0
xi一ui今Fix0
fs0时,变分不等式问题2-4归结为非线性方程组
特别地,当?
Fx0
2-9
7第二章非线性互补问题的基本理论
另外,当?
N0时有5R+三xGRn|x0,故变分不等式问题2-4
可
表示为
\xi0,Fix0i1,…,n
yxi0今Fix0
这意味着对每个指标i,;Ti与FiT均为非负值,并且至少有一个为0.上述条件进一
步等价于
x0,Fx0,xTFx0.2-10
集合R+上的变分不等式问题,也即求解满足式2-10的向量;xG尺”的问题称为互
补问题或非线性互补问题特别地,若映射F可由nxn阶矩阵M及n维向量q定义
为FxMx+q,则成为线性互补问题此外,求解满足式2-10的向量;r的问题
称为混合互补问题222解的存在性、唯一性和解集的有界性
对于变分不等式问题2-4,定义映射:
Rn^Rn如下:
HaPsx-aFx2-11
其中a0为常数,Ps表示到闭凸集S上的投影算子.下面的定理给出了变分不等
式问题2-4有解的一个充分条件定理2.2给定映射F:
Rn^Rn与非空闭凸集SCRn,xGS为变分不等
式问题2-4的解的充要条件是xHaT成立进一步,若F连续且S为紧集,
则
变分不等式问题2-4有解证明:
由Ha的定义2-11及投影算子的性质知
x?
aFx?
Hax,W?
Hax0,yGS2-12
若Haxx,则由式2-12可得
aFx,y?
x0,yGS2-13
由于a0,式2-13即表明;x为变分不等式2-4的解.反之若x为变分不等式问
题2-4的解,则对任意a0均有
aFx,x-y0,yGS
8第二章非线性互补问题的基本理论
在上式及2-12中分别取yHaT及yx,然后相加可得
x一aFx,x一aFx||x一aFx||202-14
此即意味着xHax.
当S为非空闭凸集时,||Psx一Psy|||x一y||,所以当映射F连续时,由2-
12定义的映射Ha也连续,此外,由投影算子的定义,对所有;rG夕均有HaxGS,
故由Brouwer不动点定理知,必存在xGS满足xHax.
若集合S为无界集,则当映射F满足适当条件时,也可以保证变分不等式问题
的解的存在性以下强单调性和强制性概念在证明变分不等式时会非常有用
称映射F:
Rn^Rn在集合S上是强单调的,如果存在常数a0,使得
Fx一Fy,x一ya||x一y||2
称映射F:
Rn^Rn在集合S上是强制的,如果存在^。
GS,使得
Fx,x一x0
lim、、,,,?
?
-+?
2-15
IIxII
若映射F在S上强单调,则F在S上是强制的考虑下面与2-4相关的变分不等式
问题:
Fx,y一x0,yGSr2-16
其中Sr为由某常数r0定义的如下凸集:
SrSPlB0,rxGRn|xGS,||x|r
由定理2.2,当映射F连续且集合Sr非空时,变分不等式问题2-16至少存在一个
解GSr.首先证明下面的引理:
引理2.1设F:
Rn^Rn为连续映射,SCRn为非空闭凸集,则变分不等
式问题2-4有解的充要条件是存在某个常数r0,使得变分不等式问题2-16具
有满足IbrIlr的解GSr.
证明:
必要性显然,只证充分性设GSr为变分不等式问题2-4的一个满
足|x
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 求解 非线性 互补 问题 精确 光滑 牛顿 算法 编辑