zbMATH — the first resource for mathematics

Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems. (English) Zbl 0793.90055
Summary: 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.

90C25 Convex programming
90C20 Quadratic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] I. Adler et al., An implementation of Karmarkar’s algorithm for linear programming, Math. Progr. 44 (1989) 297–335. · Zbl 0682.90061
[2] E.R. Barnes, A variation on Karmarkar’s algorithm for solving linear programming problems, Math. Progr. 36 (1986) 174–182. · Zbl 0626.90052
[3] I.I. Dikin, Iterative solution of problems of linear and quadratic programming, Sov. Math. Doklady 8 (1967) 674–675. · Zbl 0189.19504
[4] I.I. Dikin and V.I. Zorkaltsev,Iterative Solutions of Mathematical Programming Problems (Nauka, Novosibirsk, 1980).
[5] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[6] J. MorĂ©, The Levenberg-Marquardt algorithm: Implementation and theory, in:Numerical Analysis, ed. G.A. Watson (Springer, Berlin, 1978) pp. 105–116.
[7] A. Schrijver,Theory of Linear and Integer Programming (Wiley, Chichester, England, 1986). · Zbl 0665.90063
[8] 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).
[9] P. Tseng and Z.-Q. Luo, On the convergence of the affine-scaling algorithm, Math. Progr. Series A 56 (1992) 301–319. · Zbl 0762.90052
[10] T. Tsuchiya, Global convergence of the affine scaling methods for degenerate linear programming problems, Math. Progr. Series B 52 (1991) 377–404. · Zbl 0749.90051
[11] T. Tsuchiya, Global convergence property of the affine scaling methods for primal degenerate linear programming problems, Math. Oper. Res. 17 (1992) 527–557. · Zbl 0762.90053
[12] R.J. Vanderbei et al., A modification of Karmarkar’s linear programming algorithm, Algorithmica 1 (1986) 395–407. · Zbl 0626.90056
[13] 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. · Zbl 0678.90064
[14] 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).
[15] Y. Ye and E. Tse, An extension of Karmarkar’s projective algorithm for convex quadratic programming, Math. Progr. 44 (1989) 157–179. · Zbl 0674.90077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.