On the rate of convergence of certain methods of centers

It is shown in this paper that a theoretical method of centers, introduced by Huard, converges linearly. It is also shown, by counter-example, that a modified method of centers due to Huard and a method of feasible direction due to Topkis and Veinot cannot converge linearly even under convexity assumptions. Because of this, a new modified method of centers is introduced which uses a quadratic programming direction finding subroutine. In most uses this new method is not more complicated than Huard's modified method of centers. But it does converge linearly. A method for implementing it without loss of rate of convergence is also discussed.Research sponsored by the Joint Services Electronics Program, Grant AF-AFOSR-68-1488 and the National Aeronautics and Space Administration, Grant NGL-05-003-016.