摘要
针对线性规划问题,给出了其原问题和对偶问题的最优性条件,并通过引入一个正则化的对称扰动的光滑函数,将其扩展成一个混合线性互补问题,并利用光滑型算法求解.该算法具有全局收敛的特性.对于有最优解的问题,算法能求得问题的一个严格互补解;对于不可行的问题,算法也能表明问题的不可行性.
To solve linear programs ( LP ), the optimality conditions of original problem and the dual problem were proposed. By introducing a smoothing function with a regularized symmetrical perturbation, the optimality conditions were reformulated as a mixed linear complementary problem, which is solved by using the proposed smoothing algorithm. The proposed algorithm is shown to be globally convergent if the LP has a optimal solution, then the proposed algorithm is able to find a strictly complementary solution; and if the LP is infeasible, then the algorithm will detect infeasibility of the LP.
出处
《天津大学学报》
EI
CAS
CSCD
北大核心
2008年第7期877-883,共7页
Journal of Tianjin University(Science and Technology)
基金
国家自然科学基金资助项目(79670064)
关键词
线性规划
光滑型算法
全局收敛性
严格互补解
linear program
smoothing algorithm
global convergence
strictly complementary solution