A nontangential cutting plane algorithm. (English) Zbl 1018.90032
The author examines the cutting plane algorithm for solving the Lagrangian dual problem of a convex program. This paper demonstrates that the algorithm still converges to an optimal solution when cuts are nontangential or generated by not solving the optimality or nearly so. Computational results from randomly generated linear and quadratic programming problems indicate that nontangential cuts can lead to a more efficient algorithm.
Reviewer: Alexander Rappoport (Moskva)
Keywords:
decomposition; large-scale system; cutting plane algorithm; Lagrangian dual problem; convex programReferences:
| [1] | Bazaraa, M. S.; Sherali, H. D.; Shetty, C. M., Nonlinear Programming: Theory and Algorithms (1993), Wiley: Wiley New York · Zbl 0774.90075 |
| [2] | Brooke, A.; Kendrick, D.; Meeraus, A.; Raman, R., GAMS: A User’s Guide (1998), GAMS Development Corporation: GAMS Development Corporation Washington, DC |
| [3] | Dantzig, G. B.; Thapa, M. N., Linear Programming (1997), Springer: Springer New York, NY · Zbl 0883.90090 |
| [4] | Dantzig, G. B.; Wolfe, P., Decomposition principle for linear programs, Oper. Res., 8, 101-111 (1960) · Zbl 0093.32806 |
| [5] | ILOG, CPLEX 6.5 User’s Manual, ILOG Incorporated, Mountain View, CA, 1999.; ILOG, CPLEX 6.5 User’s Manual, ILOG Incorporated, Mountain View, CA, 1999. |
| [6] | B.A. Murtagh, M.A. Saunder, MINOS: user’s guide, Technical Report SOL 83-20R, Department of Operations Research, Stanford University, Stanford, CA, 1995.; B.A. Murtagh, M.A. Saunder, MINOS: user’s guide, Technical Report SOL 83-20R, Department of Operations Research, Stanford University, Stanford, CA, 1995. |
| [7] | Rosen, J. B.; Suzuki, S., Construction of nonlinear programming test problems, Comm. ASM, 8, 113 (1965) |
| [8] | Solomon, D. A., Inside Windows NT (1998), Microsoft Press: Microsoft Press Redmond, WA |
| [9] | Zakeri, G.; Philpott, A. B.; Ryan, D. M., Inexact cuts in Benders decomposition, SIAM J. Optim., 10, 643-657 (2000) · Zbl 0955.90088 |
| [10] | Zangwill, W. I., Nonlinear Programming: A Unified Approach (1969), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0191.49101 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
