基于尺度中心路径的预估—矫正光滑化算法  

Predictor-Corrector Smoothing Methods Based on a Scaled Central Path for Linear Programming

作　　者：刘长河[1,2] 甘从辉[3] 丁艳风[4] 

机构地区：[1]河南科技大学理学院,河南洛阳471003 [2]西安电子科技大学理学院,陕西西安710071 [3]河南科技大学电子信息工程学院,河南洛阳471003 [4]郑州大学升达经贸管理学院,河南郑州451191

出　　处：《西安文理学院学报（自然科学版）》2010年第2期31-35,共5页Journal of Xi’an University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60674108)

摘　　要：对于求解线性规划问题提出了一个基于尺度中心路径的预估-矫正光滑化方法.在适当的假设条件下,证明了方法的全局和局部二次收敛性.特别,在方法的局部二次收敛性分析中,不需要假定线性规划的解是唯一的.文中的方法可以推广到P0-线性互补问题和单调线性互补问题.This paper presents a predictor-corrector smoothing-type method based on a scaled central path for the solution of linear programs. Its main idea is to reformulate the primal-dual optimality conditions as a nonlinear and non-smooth system of equations, and to apply a Newton-type method to a smooth approximation of this non-smooth system. The method presented here is shown to be globally and locally quadratically convergent under reasonable assumptions （ which do not imply that the solution set consists of a single element）. The proposed method in this paper can also be extended to solve and monotone linear complementarity problems.

关 键 词：线性规划 尺度中心路径 光滑化方法 二次收敛 

分 类 号：O221[理学—运筹学与控制论]