《《1993 A primal—dual infeasible-interior-point algorithm for linear programming》.pdf

Mathematical Programming 61 (1993) 263-280 263 North-Holland A primal-dual infeasible-interior-point algorithm for linear programming Masakazu Kojima* Department of Information Sciences, TokyoInstitute of Technology, Tokyo, Japan Nimrod Megiddo IBM Almaden Research Center, San Jose, CA, USA, and School of Mathematical Sciences, Tel Aviv University, TelAviv, Israel Shinji Mizuno** The Institute of Statistical Mathematics, Tokyo, Japan Received 5 December 1991 Revised manuscript received 14 September 1992 As in many primal dual interior-point algorithms, a primal dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence. Key words: Infeasible-interior-point algorithm, interior-point algorithm, prima~dual algorithm, linear program, large step, global convergence. 1. Introduction The primal-dual infeasible-interior-point algorithm which we will discuss has stemmed from the primal dual interior-point algorithm (Megiddo [16], Kojima, Mizuno and Yoshise [7], Monteiro and Adler [19], Tanabe [22]) for linear programs. It has already been studied by many researchers (Lustig [12], Lustig, Marsten and Shanno [13], Marsten, Subramanian, Saltzman, Lustig and Shanno [14], Tanabe [22, 23], Vanderbei and Carpenter [24], etc.), and is known as practically efficient Correspondence to : Prof. Masakazu Kojima, Department of Information Sciences, To