求解线性规划的一个非内点算法  

A non-interior point algorithm for linear programming

作　　者：李兴斯[1] 潘少华[2] 

机构地区：[1]大连理工大学工业装备结构分析国家重点实验室,辽宁大连116024 [2]大连理工大学应用数学系,辽宁大连116024

出　　处：《大连理工大学学报》2004年第2期176-180,共5页Journal of Dalian University of Technology

基　　金：国家基础性研究发展规划资助项目(G1999032805).

摘　　要：利用NCP函数和光滑化方法将线性规划的K-K-T条件化为一个光滑方程组,构造了一个非内点原-对偶路径跟踪算法,并分析了其全局及局部收敛性;同时通过计算标准线性规划考题,验证了它的可行性及有效性.A NCP function and smoothing methods are used to convert the optimality conditions of linear programming into a smooth system of equations, and a non-interior point path following algorithm is developed. For this algorithm, its global and local quadratic convergence analysis is presented, and its feasibility and efficiency are validated by computing the Netlib test problems.

关 键 词：线性规划 NCP函数 光滑化方法 非内点原-对偶路径跟踪算法 

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