An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption |
| |
Authors: | Masakazu Muramatsu Takashi Tsuchiya |
| |
Institution: | (1) Department of Mechanical Engineering, Sophia University, 7-1 Kioicho, Chiyoda-ku, 102 Tokyo, Japan;(2) The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, 106 Tokyo, Japan |
| |
Abstract: | In this paper, we propose an infeasible-interior-point algorithm for linear programning based on the affine scaling algorithm by Dikin. The search direction of the algorithm is composed of two directions, one for satisfying feasibility and the other for aiming at optimality. Both directions are affine scaling directions of certain linear programming problems. Global convergence of the algorithm is proved under a reasonable nondegeneracy assumption. A summary of analogous global convergence results without any nondegeneracy assumption obtained in 17] is also given. |
| |
Keywords: | Linear programming infeasible-interior-point methods affine scaling algorithm global convergence analysis nondegeneracy assumption |
本文献已被 SpringerLink 等数据库收录! |
|