Abstract
In this paper we deal with global convergence of the affine scaling algorithm for strictly convex QP problems satisfying a dual nondegeneracy condition. By means of the local Karmarkar potential function which was successfully applied to demonstrate global convergence of the affine scaling algorithm for LP, we show global convergence of the algorithm when the step-size 1/8 is adopted without requiring any primal nondegeneracy condition.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
I. Adler et al., An implementation of Karmarkar's algorithm for linear programming, Math. Progr. 44 (1989) 297–335.
E.R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Math. Progr. 36 (1986) 174–182.
I.I. Dikin, Iterative solution of problems of linear and quadratic programming, Sov. Math. Doklady 8 (1967) 674–675.
I.I. Dikin and V.I. Zorkaltsev,Iterative Solutions of Mathematical Programming Problems (Nauka, Novosibirsk, 1980).
N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373–395.
J. Moré, The Levenberg-Marquardt algorithm: Implementation and theory, in:Numerical Analysis, ed. G.A. Watson (Springer, Berlin, 1978) pp. 105–116.
A. Schrijver,Theory of Linear and Integer Programming (Wiley, Chichester, England, 1986).
J. Sun, A convergence proof of an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions, Technical Report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208, USA (1990).
P. Tseng and Z.-Q. Luo, On the convergence of the affine-scaling algorithm, Math. Progr. Series A 56 (1992) 301–319.
T. Tsuchiya, Global convergence of the affine scaling methods for degenerate linear programming problems, Math. Progr. Series B 52 (1991) 377–404.
T. Tsuchiya, Global convergence property of the affine scaling methods for primal degenerate linear programming problems, Math. Oper. Res. 17 (1992) 527–557.
R.J. Vanderbei et al., A modification of Karmarkar's linear programming algorithm, Algorithmica 1 (1986) 395–407.
Y. Ye, An extension of Karmarkar's algorithm and the trust region method for quadratic programming, in:Progress in Mathematical Programming, ed. N. Megiddo (Springer, 1989) pp. 49–63.
Y. Ye, A new complexity result on minimization of a quadratic function over a sphere constraint, Technical Report, Department of Management Sciences, The University of Iowa, Iowa City, IA 52242, USA (November, 1990).
Y. Ye and E. Tse, An extension of Karmarkar's projective algorithm for convex quadratic programming, Math. Progr. 44 (1989) 157–179.
Author information
Authors and Affiliations
Additional information
This paper was presented at the 14th International Symposium on Mathematical Programming, held August 5–9, 1991, in Amsterdam, The Netherlands.
Rights and permissions
About this article
Cite this article
Tsuchiya, T. Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems. Ann Oper Res 46, 509–539 (1993). https://doi.org/10.1007/BF02023112
Issue Date:
DOI: https://doi.org/10.1007/BF02023112