×

zbMATH — the first resource for mathematics

A first-order interior-point method for linearly constrained smooth optimization. (English) Zbl 1216.49028
Summary: We propose a first-order interior-point method for linearly constrained smooth optimization that unifies and extends the first-order affine-scaling method and the replicator dynamics method for standard quadratic programming. Global convergence and, in the case of quadratic program, (sub)linear convergence rate and iterate convergence results are derived. Numerical experiences on simplex constrained problems with 1000 variables are presented.

MSC:
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C25 Convex programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C51 Interior-point methods
Software:
MINOS; minpack
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bertsekas D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[2] Bomze I.M.: On standard quadratic optimization problems. J. Global Optim. 13, 369–387 (1998) · Zbl 0916.90214
[3] Bomze I.M.: Regularity vs. degeneracy in dynamics games and optimization: a unified approach to different aspects. SIAM Rev. 44, 394–414 (2002) · Zbl 1021.91007
[4] Bomze I.M.: Portfolio selection via replicator dynamics and projection of indefinite estimated covariances. Dyn. Cont. Discrete Impuls. Syst. Ser. B 12, 527–564 (2005) · Zbl 1181.90209
[5] Bomze, I. M., Schachinger, W.: Multi-standard quadratic optimization problems. Comput. Optim. Appl. doi: 10.1007/s10589-009-9243-8 (2009) · Zbl 1218.90151
[6] Bonnans J.F., Pola C.: A trust region interior point algorithm for linearly constrained optimization. SIAM J. Optim. 7, 717–731 (1997) · Zbl 0899.90146
[7] Dikin I.I.: Iterative solution of problems of linear and quadratic programming. Soviet Math. Dokl. 8, 674–675 (1967) · Zbl 0189.19504
[8] Dikin I.I.: Letter to the editor. Math. Program. 41, 393–394 (1988)
[9] Forsgren A., Gill P.E., Wright M.H.: Interior methods for nonlinear optimization. SIAM Rev. 44, 525–597 (2002) · Zbl 1028.90060
[10] Gill P.E., Murray W., Wright M.H.: Practical Optimization. Academic Press, New York (1981)
[11] Gonzaga, C.C., Carlos, L.A.: A primal affine scaling algorithm for linearly constrained convex programs. Tech. Report ES-238/90, Department of Systems Engineering and Computer Science, COPPE Federal University of Rio de Janeiro, Rio de Janeiro, December 1990
[12] Hofbauer J., Sigmund K.: Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge (1998) · Zbl 0914.90287
[13] Hoffman A.J.: On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49, 263–265 (1952)
[14] Luo Z.-Q., Tseng P.: On the convergence of the affine-scaling algorithm. Math. Program. 56, 301–319 (1992) · Zbl 0762.90052
[15] Lyubich Y., Maistrowskii G.D., Ol’khovskii Yu.G.: Selection-induced convergence to equilibrium in a single-locus autosomal population. Probl. Inf. Transm. 16, 66–75 (1980) · Zbl 0458.92011
[16] Mangasarian O.L.: A simple characterization of solution sets of convex programs. Oper. Res. Lett. 7, 21–26 (1988) · Zbl 0653.90055
[17] Monteiro R.D.C., Tsuchiya T.: Global convergence of the affine scaling algorithm for convex quadratic programming. SIAM J. Optim. 8, 26–58 (1998) · Zbl 0915.90221
[18] Monteiro R.D.C., Tsuchiya T., Wang Y.: A simplified global convergence proof of the affine scaling algorithm. Ann. Oper. Res. 46/47, 443–482 (1993) · Zbl 0804.90091
[19] Monteiro R.D.C., Wang Y.: Trust region affine scaling algorithms for linearly constrained convex and concave programs. Math. Program. 80, 283–313 (1998) · Zbl 0901.90166
[20] Moran P.A.P.: The statistical Processes of Evolutionary Theory. Clarendon Press, Oxford (1962) · Zbl 0119.35901
[21] MorĂ© J.J., Garbow B.S., Hillstrom K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17–41 (1981) · Zbl 0454.65049
[22] Murtagh, B.A., Saunders, M.A.: MINOS 5.5 user’s guide. Report SOL 83-20R, Department of Operations Research, Stanford University, Stanford (Revised July 1998)
[23] Pelillo M.: Replicator equations, maximal cliques, and graph isomorphism. Neural Comput. 11, 1933–1955 (1999)
[24] Pelillo M.: Matching free trees, maximal cliques, and monotone game dynamics. IEEE Trans. Pattern Anal. Machine Intell. 24, 1535–1541 (2002) · Zbl 05112638
[25] Pelillo M., Siddiqi K., Zucker S.W.: Matching hierarchical structures using association graphs. IEEE Trans. Pattern Anal. Mach. Intell. 21, 1105–1120 (1999) · Zbl 05112796
[26] Saigal R.: The primal power affine scaling method. Ann. Oper. Res. 62, 375–417 (1996) · Zbl 0848.90090
[27] Sun J.: A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions. Math. Program. 60, 69–79 (1993) · Zbl 0781.90073
[28] Sun J.: A convergence analysis for a convex version of Dikin’s algorithm. Ann. Oper. Res. 62, 357–374 (1996) · Zbl 0848.90101
[29] Tseng P.: Convergence properties of Dikin’s affine scaling algorithm for nonconvex quadratic minimization. J. Global Optim. 30, 285–300 (2004) · Zbl 1066.90076
[30] Tsuchiya T.: Global convergence of the affine scaling methods for degenerate linear programming problems. Math. Program. 52, 377–404 (1991) · Zbl 0749.90051
[31] Tsuchiya T.: Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems. Ann. Oper. Res. 46/47, 509–539 (1993) · Zbl 0793.90055
[32] Tsuchiya T., Muramatsu M.: Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems. SIAM J. Optim. 5, 525–551 (1995) · Zbl 0838.90081
[33] Ye Y.: On affine scaling algorithms for nonconvex quadratic programming. Math. Program. 56, 285–300 (1992) · Zbl 0767.90065
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.