A new infeasible interior-point algorithm with full step for linear optimization based on a simple function

Abstract

In this paper, we design and analyse an infeasible interior-point algorithm based on a simple function for linear optimization. The infeasible algorithm contains two types of search directions: the feasibility search direction and the centrality search direction. Both of the directions are determined by the simple function. The algorithm uses full step, thus no need to perform the line-search procedure. Although the proposed function is simple, as it will be shown, the induced infeasible algorithm enjoys the best-known iteration complexity for infeasible interior-point algorithm.

Keywords:

• linear optimization
• infeasible interior-point algorithm
• full step
• complexity analysis

2000 AMS Subject Classifications :

• 90C05
• 90C25
• 90C51

Acknowledgements

The research is supported by National Natural Science Foundation of China (No. 11071221, 11071158) and key disciplines of Shanghai Municipality Discipline Project (No. S30104).