×

zbMATH — the first resource for mathematics

Interior dual proximal point algorithm for linear programs. (English) Zbl 0810.90092
Summary: A new algorithm for solving a linear program based on an interior point method applied to the dual of a proximal point formulation of the linear program is presented. This dual formulation contains only the nonnegativity constraint on some of the variables. This simple constraint allows us to start the algorithm without a Phase 1 method required by many other variants of the interior point method. Numerical results from a large set of test problems show that the proposed algorithm can be very competitive with other interior point methods and with MINOS 5.3, a state-of-the-art linear programming package based on the simplex method. Global convergence of the algorithm is also established.

MSC:
90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Software:
KORBX; MINOS; YSMP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adler, I.; Resende, M.G.C.; Veiga, G., An implementation of Karmarkar’s algorithm for linear programming, Mathematical programming, 44, 297-335, (1989) · Zbl 0682.90061
[2] Bertsekas, D.P., Constrained optimization and Lagrange multipliers methods, (1982), Academic Press New York · Zbl 0453.65045
[3] Choi, I.C.; Monna, C.L.; Shanno, D.F., Further development of a primal-dual interior point method, ORSA journal on computing, 4, 304-311, (1990) · Zbl 0757.90051
[4] Eisenstat, S.C.; Gursky, M.C.; Schultz, M.H.; Sherman, A.H., Yale sparse matrix package I: the symmetric codes, () · Zbl 0492.65012
[5] Eisenstat, S.C.; Gursky, M.C.; Schultz, M.H.; Sherman, A.H., Yale sparse matrix package I: the symmetric codes, International journal for numerical methods in engineering, 18, 1145-1151, (1982) · Zbl 0492.65012
[6] Gay, D.M., Electronic mail distribution of linear programming test problems, Mathematical programming society COAL newsletter, (December 1985)
[7] Gay, D.M., Stopping tests that compute optimal solutions for interior-point linear programming algorithms, () · Zbl 0813.90082
[8] Gill, P.E.; Murray, W.; Saunders, M.A., A single-phase dual barrier method for linear programming, () · Zbl 0815.65080
[9] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[10] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., Computational experience with a primal-dual interior point method for linear programming, Linear algebra and its applications, 152, 191-222, (1991) · Zbl 0731.65049
[11] Mangasarian, O.L., A stable theorem of the alternative: an extension of the Gordan theorem, Linear algebra and its applications, 41, 209-223, (1981) · Zbl 0488.90044
[12] Mangasarian, O.L., Nonlinear programming, (1969), McGraw-Hill New York · Zbl 0194.20201
[13] Marsten, R.E.; Saltzman, M.J.; Shanno, D.F.; Pierce, G.S.; Ballintijn, J.F., Implementation of a dual affine interior point algorithm for linear programming, ORSA journal on computing, 1, 287-297, (1988) · Zbl 0752.90046
[14] McShane, K.A.; Monma, C.L.; Shanno, D., An implementation of a primal-dual interior point method for linear programming, ORSA journal on computing, 1, 70-83, (1989) · Zbl 0752.90047
[15] Monma, C.L.; Morton, A.J., Computational experience with a dual affine variant of the Karmarkar’s method for linear programming, Operative research letters, 6, 261-267, (1987) · Zbl 0627.90065
[16] Murtagh, B.A.; Saunders, M.A., MINOS 5.0 User’s guide, ()
[17] Polyak, B.T., Introduction to optimization, (1987), Optimization Software Inc New York · Zbl 0652.49002
[18] Rockafellar, R.T., Monotone operators and the proximal point algorithm, SIAM journal on control and optimization, 14, 877-898, (1976) · Zbl 0358.90053
[19] Rockafellar, R.T., A dual approach to solving nonlinear programming problems by unconstrained minimization, Mathematical programming, 5, 354-373, (1973) · Zbl 0279.90035
[20] Setiono, R.; Setiono, R., Interior proximal point algorithm for linear programs, (), Journal of optimization theory and applications, 74/3, 425-444, (1992) · Zbl 0795.90041
[21] Tseng, P., A simple complexity proof for a polynomial-time linear programming algorithms, Operations research letters, 8, 155-159, (1989) · Zbl 0682.90059
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.