Abstract
For nonconvex problems, the saddle point equivalence of the Lagrangian approach need not hold. The nonexistence of a saddle point causes the generation of a dual gap at the solution point, and the Lagrangian approach then fails to give the solution to the original problem. Unfortunately, dual gaps are a fairly common phenomenon for engineering system design problems.
Methods which are available to resolve the dual gaps destroy the separability of separable systems. The present work employs the method of multipliers by Hestenes to resolve the dual gaps of engineering system design problems; it then develops an algorithmic procedure which preserves the separability characteristics of the system. The theoretical foundations of the proposed algorithm are developed, and examples are provided to clarify the approach taken.
Similar content being viewed by others
References
Everett, H., III,Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources, Operations Research, Vol. 11, No. 3, 1963.
Lasdon, L. S.,Optimization Theory for Large Systems, McMillan Publishing Company, New York, New York, 1970.
Greenberg, H. J.,Lagrangian Duality Gaps: Their Source and Resolution, Southern Methodist University, Technical Report No. CP-69005, 1969.
Gould, F. J.,Extensions of Lagrange Multipliers in Nonlinear Programming, SIAM Journal on Applied Mathematics, Vol. 17, No. 6, 1969.
Bellman, R., andKarush, W.,On a New Functional Transform in Analysis: The Maximum Transform, Bulletin of American Mathematical Society, Vol. 67, No. 5, 1961.
Greenberg, H. J., andPierskalla, W. P.,Surrogate Mathematical Programs, Operations Research, Vol. 18, No. 5, 1970.
Glover, F.,A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem, Operations Research, Vol. 16, No. 4, 1968.
Loane, E. P.,An Algorithm to Solve Finite Separable Constrained Optimization Problems, Operations Research, Vol. 19, No. 6, 1971.
Bellmore, M., Greenberg, H. J., andJarvis, J. J.,Generalized Penalty Function Concepts in Mathematical Optimization, Operations Research, Vol. 18, No. 2, 1970.
Falk, J. E., andSoland, R. M.,An Algorithm for Separable Nonconvex Programming Problems, Management Science, Vol. 15, No. 9, 1969.
Soland, R. M.,An Algorithm for Separable Non-Convex Programming Problems II: Non-Convex Constraints, Management Science, Vol. 17, No. 11, 1971.
Greenberg, H. J.,Bounding Nonconvex Programs by Conjugates, Operations Research, Vol. 21, No. 1, 1973.
McGalliard, R. L., andWesterberg, A. W.,Structural Sensitivity Analysis in Design Synthesis, The Chemical Engineering Journal, Vol. 4, No. 4, 1972.
Rockafellar, R. T.,Non-Linear Programming, American Mathematical Society Summer Seminar on the Mathematics of the Decision Sciences, Stanford University, 1967.
Hestenes, M. R.,Multiplier and Gradient Methods, Journal of Optimization Theory and Applications, Vol. 4, No. 5, 1969.
Miele, A., Moseley, P. E., Levy, A. V., andCoggins, G. M.,On the Method of Multipliers for Mathematical Programming Problems, Journal of Optimization Theory and Applications, Vol. 10, No. 1, 1972.
McGalliard, R. L.,Structural Sensitivity Analysis in Design Synthesis, University of Florida, Ph.D. Thesis, 1971.
Author information
Authors and Affiliations
Additional information
Communicated by R. Jackson
This work was supported by NSF Grant No. GK-18633.
Rights and permissions
About this article
Cite this article
Stephanopoulos, G., Westerberg, A.W. The use of Hestenes' method of multipliers to resolve dual gaps in engineering system optimization. J Optim Theory Appl 15, 285–309 (1975). https://doi.org/10.1007/BF00933339
Issue Date:
DOI: https://doi.org/10.1007/BF00933339