×

zbMATH — the first resource for mathematics

A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions. (English) Zbl 0781.90073
Summary: This paper presents a theoretical result on convergence of a primal affine-scaling method for convex quadratic programs. It is shown that, as long as the stepsize is less than a threshold value which depends on the input data only, Ye and Tse’s interior ellipsoid algorithm for convex quadratic programming [see Y. Ye and E. Tse, Math. Program., Ser. A 44, No. 2, 157-179 (1989; Zbl 0674.90077)] is globally convergent without nondegeneracy assumptions. In addition, its local convergence rate is at least linear and the dual iterates have an ergodically convergent property.

MSC:
90C20 Quadratic programming
90C25 Convex programming
Citations:
Zbl 0674.90077
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1989) 174–182. · Zbl 0626.90052
[2] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[3] I.I. Dikin, ”On the speed of an iterative process,”Upravlyaemye Sistemi 12 (1974) 54–60. · Zbl 0402.90059
[4] R.C. Monteiro, I. Adler and M.G.C. Resende, ”A polynomial-time primal–dual affine scaling algorithm for linear and convex quadratic programming and its power series extension,”Mathematics of Operations Research 15 (1990) 191–214. · Zbl 0714.90060
[5] P. Tseng and Z.-Q. Luo, ”On the convergence of the affine-scaling algorithm,” Preprints CICS-P-169, M.I.T. (Cambridge, MA, 1989).
[6] T. Tsuchiya, ”Global convergence of the affine scaling methods for degenerate linear programming problems,” Research Memorandum No. 373, The Institute of Statistical Mathematics (Tokyo, Japan, 1990).
[7] T. Tsuchiya, ”Global convergence property of the affine scaling methods for primal degenerate linear programming problems,” Research Memorandum No. 367, The Institute of Statistical Mathematics (Tokyo, Japan, 1989). · Zbl 0762.90053
[8] R.J. Vanderbei and J.C. Lagarias, ”Dikin’s convergence result for the affine-scaling algorithm,” in: J. Lagarias and M. Todd,Contemporary Mathematics No. 114 (AMS, Providence, RI, 1990) pp. 109–119. · Zbl 0727.90050
[9] R.J. Vanderbei, M.S. Meketon and B.A. Freeman, ”A modification of Karmarkar’s linear programming algorithm,”Arithmica 1 (1986) 395–407. · Zbl 0626.90056
[10] Y. Ye, ”An extension of Karmarkar’s projective algorithm and the trust region method for quadratic programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming – Interior Point and Related Methods (Springer, Berlin, 1989). · Zbl 0678.90064
[11] Y. Ye and E. Tse, ”An extension of Karmarkar’s projective algorithm for convex quadratic programming,”Mathematical Programming 44 (1989) 157–180. · 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.