The primal power affine scaling method

Abstract

In this paper, we present a variant of the primal affine scaling method, which we call the primal power affine scaling method. This method is defined by choosing a real r >0.5, and is similar to the power barrier variant of the primal-dual homotopy methods considered by den Hertog, Roos and Terlaky and Sheu and Fang. Here, we analyze the methods for r >1. The analysis for 0.50< r <1 is similar, and can be readily carried out with minor modifications. Under the non-degeneracy assumption, we show that the method converges for any choice of the step size α. To analyze the convergence without the non-degeneracy assumption, we define a power center of a polytope. We use the connection of the computation of the power center by Newton's method and the steps of the method to generalize the 2/3rd result of Tsuchiya and Muramatsu. We show that with a constant step size α such that α/(1-α) 2 r > 2/(2 r -1) and with a variable asymptotic step size α k uniformly bounded away from 2/(2 r +1), the primal sequence converges to the relative interior of the optimal primal face, and the dual sequence converges to the power center of the optimal dual face. We also present an accelerated version of the method. We show that the two-step superlieear convergence rate of the method is 1+ r /( r +1), while the three-step convergence rate is 1+ 3 r /( r +2). Using the measure of Ostrowski, we note thet the three-step method for r =4 is more efficient than the two-step quadratically convergent method, which is the limit of the two-step method as r approaches infinity.