×

A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality. (English) Zbl 0405.90062


MSC:

90C30 Nonlinear programming
90C99 Mathematical programming
49M29 Numerical methods involving duality
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agmon, S., The relaxation method for linear inequalities, Can. J. Math., 6, 382-392 (1954) · Zbl 0055.35001
[2] Balas, E., An infeasibility pricing decomposition method for linear programs, Operations Res., 14, 847-873 (1966) · Zbl 0158.38404
[3] (Balinski, M. L.; Wolfe, P., Mathematical Programming Study 3: Nondifferentiable Optimization (1975), North-Holland: North-Holland Amsterdam) · Zbl 0335.00010
[4] Bazaraa, M. S., Geometry and resolution of duality gaps, Naval Res. Logist. Quart., 20, 357-365 (1973) · Zbl 0262.90056
[5] Bazaraa, M. S.; Goode, J. J., The traveling salesman problem: A duality approach, Mathematical Programming, 13, 221-237 (1977) · Zbl 0377.90092
[6] Bazaraa, M. S.; Sherali, H. D., A convergent subgradient optimization scheme (1978), School of Industrial and Systems Engineering, Georgia Institute of Technology: School of Industrial and Systems Engineering, Georgia Institute of Technology Atlanta, GA
[7] Bazaraa, M. S.; Shetty, C. M., Nonlinear Programming: Theory and Algorithms (1979), John Wiley: John Wiley New York · Zbl 0476.90035
[8] Bazaraa, M. S.; Goode, J. J.; Rardin, R. L., An algorithm for finding the shortest element of a polyhedral set with application to Lagrangian duality, J. Math. Anal. Appl., 65, 278-288 (1978) · Zbl 0383.90073
[9] Bazaraa, M. S.; Goode, J. J.; Rardin, R. L., A finite steepest ascent algorithm for maximizing piecewise-linear concave functions, J. Optimization Theory Appl., 25, 437-442 (1978) · Zbl 0362.90114
[10] Bertsekas, D. P., Nondifferentiable optimization via approximation, (Balinski, M. L.; Wolfe, P., Mathematical Programming Study, 3 (1975), North-Holland: North-Holland Amsterdam), 1-25 · Zbl 0866.90059
[11] Danskin, J. M., The theory of max-min with applications, SIAM J. Appl. Math., 14, 641-664 (1966) · Zbl 0144.43301
[12] Dantzig, G. B.; Wolfe, P., The decomposition algorithm for linear programming, Econometrica, 29, 767-778 (1961) · Zbl 0104.14305
[13] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.33103
[14] Demyanov, V. F., Algorithms for some minimax problems, J. Comput. Systems Sci., 2, 342-380 (1968) · Zbl 0177.23104
[15] Dzielinski, B. P.; Gomory, R., Optimal programming of lot size inventory and labor allocations, Management Sci., 11, 874-890 (1965)
[16] Eggleston, H. G., Convexity (1958), Cambridge University Press: Cambridge University Press Cambridge, MA · Zbl 0086.15302
[17] Everett, H., Generalized Lagrange multiplier method for solving problems of optimum allocation of resources, Operations Res., 11, 399-417 (1963) · Zbl 0113.14202
[18] Falk, J. E., Lagrange multipliers and nonlinear programming, J. Math. Anal., 19, 141-159 (1967) · Zbl 0154.44803
[19] Falk, J. E.; Soland, R. M., An algorithm for separable nonconvex programming problems, Management Sci., 15, 550-569 (1969) · Zbl 0172.43802
[20] Fenchel, W., Convex Cones, Sets, and Functions, Lecture Notes (1953), Princeton University Press: Princeton University Press Princeton. NJ · Zbl 0053.12203
[21] Fisher, M. L., Optimal solution of scheduling problems using generalized Lagrange multipliers: Part I, Operations Res., 11, 1114-1127 (1973) · Zbl 0294.90085
[22] Fisher, M. L., A dual algorithm for the one machine scheduling problem, Mathematical Programming, 11, 229-251 (1976) · Zbl 0359.90039
[23] Fisher, M. L.; Northup, W. D.; Shapiro, J. F., Using duality to solve discrete optimization problems: Theory and computational experience, (Balinski, M. L.; Wolfe, P., Mathematical Programming Study, 3 (1975), North-Holland: North-Holland Amsterdam), 56-94 · Zbl 0367.90087
[24] Geoffrion, A. M., Elements of large-scale mathematical programming, Management Sci., 10, 652-691 (1970) · Zbl 0209.22801
[25] Geoffrion, A. M., Duality in nonlinear programming: A simplified applications-oriented development, SIAM Rev., 13, 1-37 (1971) · Zbl 0232.90049
[26] Geoffrion, A. M., Lagrangian relaxation for integer programming, (Balinski, M. L., Mathematical Programming Study, 2 (1974), North-Holland: North-Holland Amsterdam), 82-114 · Zbl 0395.90056
[27] Gill, P. E.; Murray, W., Numerical Methods for Constrainted Optimization (1974), Academic Press: Academic Press New York
[28] Grinold, R. C., Steepest ascent for large scale linear programs, SIAM Rev., 14, 447-464 (1972) · Zbl 0281.90044
[29] Held, M.; Karp, R. M., The traveling salesman problem and minimum spanning trees, Operations Res., 18, 1138-1162 (1970) · Zbl 0226.90047
[30] Held, M.; Karp, R. M., The traveling salesman problem and minimum spanning trees: Part II, Mathematical Programming, 1, 6-25 (1971) · Zbl 0232.90038
[31] Held, M.; Wolfe, P.; Crowder, H. D., Validation of subgradient optimization, Mathematical Programming, 6, 62-88 (1974) · Zbl 0284.90057
[32] Kelley, J. E., The cutting plane method for solving convex programs, SIAM J. Appl. Math., 8, 703-712 (1960) · Zbl 0098.12104
[33] Kennington, J.; Shalaby, M., An effective subgradient procedure for minimal cost multi-commodity flow problems, Management Sci., 23, 994-1004 (1977) · Zbl 0366.90118
[34] Kuhn, H. W.; Tucker, A. W., Nonlinear programming, (Neyman, J., Proceedings of the Second Berkeley Symposium in Mathematical Statistics and Probability (1951), University of California Press: University of California Press Berkeley, CA) · Zbl 0044.05903
[35] Lasdon, L. S., Optimization Theory for Large Systems (1970), MacMillan: MacMillan New York · Zbl 0224.90038
[36] Lemarech, C., An extension of Davidon methods to nondifferentiable problems, (Balinski, M. L.; Wolfe, P., Mathematical Programming Study, 3 (1975), North-Holland: North-Holland Amsterdam), 95-109 · Zbl 0358.90051
[37] Luenberger, D. G., Introduction to Linear and Nonlinear Programming (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0241.90052
[38] Marsten, R. E., The use of the boxstep in discrete optimization, (Balinski, M. L.; Wolfe, P., Mathematical Programming Study, 3 (1975), North-Holland: North-Holland Amsterdam), 127-144 · Zbl 0353.90063
[39] Marsten, R. E.; Hogan, W. W.; Blankenship, J. W., The boxstep method for large scale optimization, Operations Res., 23, 389-405 (1975) · Zbl 0372.90078
[40] Motzkin, R.; Schoenberg, I. J., The relaxation method for linear inequalities, Can. J. Math., 6, 393-404 (1954) · Zbl 0055.35002
[41] Muckstadt, J. A.; Koening, S. A., An application of Lagrangian relaxation to scheduling in power generation system, Operations Res., 25, 387-403 (1977) · Zbl 0383.90065
[42] Poljak, B. T., A general method of solving extremum problems, Soviet Math. Dokl., 8, 593-597 (1967) · Zbl 0177.15102
[43] Poljak, B. T., Minimization of unsmooth functionals, U.S.S.R. Computational Math. and Math. Phys., 9, 14-29 (1964) · Zbl 0229.65056
[44] Rockafellar, R. T., Duality in nonlinear programming, (Dantzig, G. B.; Veinott, A., Mathematics of the Decision Sciences (1969), American Mathematical Society) · Zbl 0231.90037
[45] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0229.90020
[46] Rosenbrock, H. H., Automatic method for finding the greatest or least value of a function, Comput. J., 3, 175-184 (1960)
[47] Shor, N. Z., On the rate of convergence of the generalized gradient method, Kibernetika, 4 (1968) · Zbl 0243.90038
[48] Smeers, Y., An algorithm for some special nondifferentiable optimization problems, Operations Res., 25, 808-817 (1977) · Zbl 0385.90093
[49] Tucker, A. W., Least-distance programming, (Kuhn, H. W., Proceedings of the Princeton Symposium on Mathematical Programming (1971), Princeton University Press: Princeton University Press Princeton, NJ), 583-588 · Zbl 0208.21703
[50] Wolfe, P., On the convergence of gradient methods under constraint, IBM J. Res. Develop., 16, 407-411 (1972) · Zbl 0265.90046
[51] Wolfe, P., Algorithm for a least-distance programming problem, (Balinski, M. L., Mathematical Programming Study, 1 (1974), North-Holland: North-Holland Amsterdam), 190-205 · Zbl 0359.90062
[52] Wolfe, P., A method of conjugate subgradients for minimizing non-differentiable functions, (Balinski, M. L.; Wolfe, P., Mathematical Programming Study, 3 (1975), North-Holland: North-Holland Amsterdam), 145-173 · Zbl 0369.90093
[53] 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.