AN EXTERIOR POINT LINEAR PROGRAMMING METHOD BASED ON INCLUSIVE NORMAL CONES

作者：Liu Yanqun^*

来源：Journal of Industrial and Management Optimization, 2010, 6(4): 825-846.

DOI：10.3934/jimo.2010.6.825

• Linear programming
• optimality
• inclusive normal cones
• exterior point algorithm
• convergence

In this paper, we present a geometrical exterior climbing method based on inclusive normal cones for solving general linear programming problems in canonical form. The method iteratively updates the inclusive cone by climbing within its associated inclusive region (also called a ladder), and eventually reaches an optimal solution. This method allows the development of a class of 'ladder algorithms' by using different climbing schemes. Some aspects of the current method are intrinsically related to the dual simplex method. However, it originates from different ideas and provides a new angle to look at the linear programming problem. It can be shown that the dual simplex algorithms are special ladder algorithms in this context. We present two climbing schemes leading to two finitely convergent ladder algorithms. The algorithms are tested by solving a number of linear programming examples. Some numerical results are provided.

• 出版日期2010-11