A POTENTIAL REDUCTION ALGORITHM WITH USER-SPECIFIED PHASE-I PHASE-II BALANCE FOR SOLVING A LINEAR PROGRAM FROM AN INFEASIBLE WARM START

作     者：FREUND, RM 

作者机构：CORNELL UNIVCOLL ENGNSCH OPERAT RES & IND ENGNITHACANY 14853 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：1995年第5卷第2期

页      面：247-268页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：LINEAR PROGRAM POTENTIAL FUNCTION INTERIOR POINT ALGORITHM POLYNOMIAL TIME COMPLEXITY 

摘      要：This paper develops a potential reduction algorithm for solving a linear programming problem directly from a warm start initial point that is neither feasible nor optimal. The algorithm is an interior point variety that seeks to reduce a single potential function which simultaneously coerces feasibility improvement (Phase I) and objective value improvement (Phase II). The key feature of the algorithm is the ability to specify beforehand the desired balance between infeasibility and nonoptimality in the following sense. Given a prespecified balancing parameter beta 0, the algorithm maintains the following Phase I-Phase II beta-balancing constraint throughout (c(T)x-z) beta xi(T)x, where C(T)x is the objective function, z is the (unknown) optimal objective value of the linear program, and xi(T)x measures the infeasibility of the current iterate x. This balancing constraint can be used to either emphasize rapid attainment of feasibility (set beta large) at the possible expense of good objective function values or to emphasize rapid attainment of good objective values (set beta small) at the possible expense of a lower infeasibility gap. The algorithm seeks to minimize the feasibility gap while maintaining the beta-balancing condition, thus solving the original linear program as a consequence. The algorithm exhibits the following advantageous features: (i) the iterate solutions monotonically decrease the infeasibility measure, (ii) the iterate solutions satisfy the beta-balancing constraint, (iii) the iterate solutions achieve constant improvement in both Phase I and Phase II in O(n) iterations, (iv) there is always a possibility of finite termination of the Phase I problem, and (v) the algorithm is amenable to acceleration via linesearch of the potential function.