一个基于罚方程的性互补问题的广义牛顿法.pdf

2015年 3月 高 等 学 校 计 算 数 学 学 报 第 37卷第 1期 一 个基于罚方程的线性互补问题的 广义牛顿法 李园 韩海山 杨丹丹 (内蒙古民族大学数学学院，通辽028043) APENALIZED EQUATION BASED GENERALIZED NEW ToN M ETHoD FoR SoIⅣ ING LINEAR CoM PLEM ENTARITY PRoBLEM S LiYuan HanHaishan YangDandan (CollegeofMathematics，InnerMongoliaUniversityfortheNationalities， Tongliao028043) Abstract Recently,a new equivalenttransformation called nonlinearpenalty equation isproposed which givesa new way forsolvinglinearcomplementary problems．Inthispaper，wegeneralizethenonlinearpenalizedequation，propose ageneralized Newton method ofrsolvingthegeneralized equation and proveits globalconvergence．Numericalresultsshow thefeasibilityandeffectivenessofour method． Key words operationsresearch，linearcomplementarity problem，P—matrix， nonlinearpenalizedequation，generalizedNewtonmethod． AMS(2000)subjectclassifications 90C33，65N12，65K10 中图法分类号 O221．2 内蒙古自然科学基金 (2011MS0114) 收稿 日期：2013．07-01． 李园等：一个基于罚方程的线性互补问题的广义牛顿法 第 1期 1 引 言 线性互补问题是运筹学与计算数学的一个交叉研究领域，已经广泛应用于力学、交 通、经济、金融、控制等领域中出现的许多数学模型，例如障碍和 自由边界问题、供应链 问题、交通分配问题、经济均衡问题、非均衡博弈论等，这使得线性互补问题成为数学规 划中的一个十分热门的研究课题．许多学者对线性互补问题的求解进行了深入的研究，提 出了许多算法 [1--4]，例如：投影法、光滑牛顿法、非光滑牛顿法、松弛法、内点法、非光 滑方程法等．进一步掌握和研究互补问题的各类算法不仅具有理论意义，而且具有实际意 义． 本文考虑如下线性互补问题 (简记作LCP(A，b))：求向量 X=(Xl，X2，… ，z) ∈R”， 使得 Ax—b 0， 0， ( 一6)X=0， (1) 其中A∈R ，b∈R ． 令 K={ ∈R 0}，则求解线性互补问题 (1)等价于求解如下变分不等式问题： 求向量Z∈K，使得对任意的Y∈K，满足 (Y— )Ax (一 )b． (2) 文 [6]构造了如下关于线性互补问题 (1)的非线性罚方程：求 ∈R“，满足 Axx+ [)、]军=b， 其中 0是惩罚因子，七0，[，“】+=max{u，0)．并且对任意