A simple proof of a primal affine scaling method |
| |
Authors: | Romesh Saigal |
| |
Institution: | (1) Department of Industrial and Operations Engineering, The University of Michigan, 48109-2117 Ann Arbor, Michigan, USA |
| |
Abstract: | In this paper, we present a simpler proof of the result of Tsuchiya and Muramatsu on the convergence of the primal affine scaling method. We show that the primal sequence generated by the method converges to the interior of the optimum face and the dual sequence to the analytic center of the optimal dual face, when the step size implemented in the procedure is bounded by 2/3. We also prove the optimality of the limit of the primal sequence for a slightly larger step size of 2q/(3q–1), whereq is the number of zero variables in the limit. We show this by proving the dual feasibility of a cluster point of the dual sequence.Partially supported by the grant CCR-9321550 from NSF. |
| |
Keywords: | Linear programming affine scaling methods interior point methods |
本文献已被 SpringerLink 等数据库收录! |
|