On the rate of convergence of certain methods of centers
Tóm tắt
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.
Tài liệu tham khảo
C. Berge,Topological spaces (MacMillan, New York, 1963).
M. Canon, C. Cullum and E. Polak,Theory of optimal control and mathematics programming (McGraw-Hill Co., New York, 1970) Theorem 19, p. 4 and Lemma 1, p. 68.
P. Faure and P. Huard, “Resultats nouveaux relatif a la methode des centres,” Paper presented at the Fourth International Conference on Operations Research, Boston, 1966.
A. Geoffrion, “Duality in nonlinear programming,”SIAM Review 13 (1971) 1.
P. Huard, “The method of centers,” in:Nonlinear programming, Ed. J. Abadie (North-Holland Publ. Co., Amsterdam, 1967).
P. Huard, “Programmation mathematique convex,”RIRO R7 (1968) 43–59.
H.W. Kuhn and A.W. Tucker, “Nonlinear programming,” in:Proc. second berkeley symposium math. stat. probability (University of California Press, Berkeley, California, 1951) pp. 481–492.
F.A. Lootsma, “Constrained optimization via parameter free penalty functions,”Philips Research Reports 23 (1968) 424–437 and suppl. 3 (1970).
O. Mangasarian,Nonlinear programming (McGraw-Hill Co., New York, 1969).
R. Mifflin, “Convergence rates for a method of center algorithm,” Thesis Operation Research Center, University of California, Berkeley, 1971.
J. Ortega and W. Rheinboldt,Iterative solution of nonlinear equations in several variables (Academic Press, New York, 1970).
O. Pironneau and E. Polak, “On the rate of convergence of certain method of centers,” Memorandum No. ERL-M296. University of California, Berkeley 1971.
O. Pironneau and E. Polak, “A dual method for optimal control problems with initial and final boundary constraints,” Memorandum No. ERL-M299, University of California, Berkeley 1971.
E. Polak,Computational methods of optimization (Academic Press, New York, 1971).
R.T. Rockafellar,Convex analysis (Princeton University Press, Princeton, New Jersey, 1970).
D. Topkis and A. Veinnott, “On the convergence of some feasible direction algorithms for nonlinear programming,”SIAM Journal on Control 5 (2) (1967) 268–79.
R. Tremolieres, “La methode des centres a troncature variable,” These, Paris, 1968.
P. Wolfe, “A duality theorem for nonlinear programming,”Quarterly of Applied Mathematics (1968) 239–244.
P. Wolfe, “The simplex method for quadratic programming,”Econometrica 27 (1959) 382–397.
G. Zoutendijk,Method of feasible direction (Elsevier Publishing Co., Amsterdam, 1960).