Abstract
This paper attempts to consolidate over 15 years of attempts at designing algorithms for geometric programming (GP) and its extensions. The pitfalls encountered when solving GP problems and some proposed remedies are discussed in detail. A comprehensive summary of published software for the solution of GP problems is included. Also included is a numerical comparison of some of the more promising recently developed computer codes for geometric programming on a specially chosen set of GP test problems. The relative performance of these codes is measured in terms of their robustness as well as speed of computation. The performance of some general nonlinear programming (NLP) codes on the same set of test problems is also given and compared with the results for the GP codes. The paper concludes with some suggestions for future research.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dembo, R. S.,Second-Order Algorithms for the Geometric Programming Dual, Part 1: Analysis, Mathematical Programming (to appear).
Gill, P. E., andMurray, W.,Numerical Methods in Constrained Optimization, Academic Press, New York, New York, 1974.
Wolfe, P.,Convergence Theory in Nonlinear Programming, Integer and Nonlinear Programming, Edited by J. Abadie, North-Holland Publishing Company, Amsterdam, Holland, 1970.
Rijckaert, M. J., andMartens, X. M.,A Comparison of Generalized Geometric Programming Algorithms, Katholieke Universiteit te Leuven, Report No. CE-RM-7503, 1975.
Dembo, R. S.,GGP—A Computer Program for Solving Generalized Geometric Programting Problems, Technion, Israel Institute of Technology, Department of Chemical Engineering, Users Manual, Report No. 72/59, 1972.
Williams, A. C., Private Communication, 1972.
Rammamurthy, S., andGallagher, R. H.,Generalized Geometric Programming in Light Gage Steel Design, Paper Presented at the ORSA/TIMS Meeting, Miami, Florida, 1976.
Dinkel, J. J., andKochenberger, G. A., Private Communication, 1975.
Duffin, R. J., Peterson, E. L., andZener, C.,Geometric Programming—Theory and Application, John Wiley and Sons, New York, New York, 1967.
IBM Corporation,Mathematical Programming System—Extended (MPSX) and Generalized Upper Bounding (GUB) Program Description, Program No. 5734-XM4, 1972.
Dembo, R. S.,Dual to Primal Conversion in Geometric Programming, Journal of Optimization Theory and Applications, Vol. 26, No. 1, 1978.
Beck, P. A., andEcker, J. G.,A Modified Concave Simplex Algorithm for Geometric Programming, Journal of Optimization Theory and Applications, Vol. 15, pp. 189–202, 1975.
Dembo, R. S.,Sensitivity Analysis in Geometric Programming, Yale University, School of Organization and Management, Working Paper No. SOM-35, 1978.
Templeman, A. B., Private Communication, 1975.
Passy, U., andWilde, D. J.,Generalized Polynomial Optimization, SIAM Journal on Applied Mathematics, Vol. 15, pp. 1344–1356, 1967.
Beightler, C. S., andPhillips, D. T.,Applied Geometric Programming, John Wiley and Sons, New York, New York, 1976.
Avriel, M., andWilliams, A. C.,Complementary Geometric Programming, SIAM Journal on Applied Mathematics, Vol. 19, pp. 125–141, 1970.
Dembo, R. S.,The Solution of Complementary Geometric Programming Problems, Technion, Israel Institute of Technology, MS Thesis, 1972.
Avriel, M., Dembo, R. S., andPassy, U.,Solution of Generalized Geometric Programming Problems, International Journal of Numerical Methods in Engineering, Vol. 9, pp. 141–169, 1975.
Duffin, R. J., andPeterson, E. L.,Geometric Programming with Signomials, Journal of Optimization Theory and Applications, Vol. 11, pp. 3–35, 1973.
Bradley, J.,The Development of Polynomial Programming Algorithms with Applications, Dublin University, Department of Computer Science, PhD Thesis, 1975.
Rijckaerts, M. J., andMartens, X. M.,A Condensation Method for Generalized Geometric Programming, Katholieke Universiteit te Leuven, Report No. CE-RM-7503, 1975.
Dembo, R. S.,A Set of Geometric Programming Test Problems and Their Solutions, Mathematical Programming, Vol. 10, pp. 192–213, 1976.
Dinkel, J. J., Kochenberger, G. A., andMcCarl, B.,A Computational Study of Methods for Solving Polynomial Geometric Programs, Journal of Optimization Theory and Applications, Vol. 19, pp. 233–259, 1976.
Colville, A. R.,A Comparative Study of Nonlinear Programming Codes, IBM, New York Scientific Center, Report No. 320–2949, 1968.
Ratner, M., Lasdon, L. S., andJain, A.,Solving Geometric Programs Using GRG—Results and Comparisons, Standford University, Systems Optimization Laboratory, Technical Report No. SOL-76-1, 1976.
Dembo, R. S., andMulvey, J. M.,On the Analysis and Comparison of Mathematical Programming Algorithms and Software, Proceedings of the Bicentennial Conference on Mathematical Programming, Gaithersburg, Maryland, 1976.
Himmelblau, D. M.,Applied Nonlinear Programming, McGraw-Hill Book Company, New York, New York, 1972.
Rijckaert, M. J., Private Communication, 1975.
Lasdon, L. S., Warren, A. D., Ratner, M. W., andJain, A.,GRG System Documentation, Cleveland State University, Technical Memorandum No. CIS-75-01, 1975.
Abadie, J., andGuigou, J.,Numerical Experiments with the GRG Method, Integer and Nonlinear Programming, Edited by J. Abadie, North Holland Publishing Company, Amsterdam, Holland, 1970.
Kreuser, J. L., andRosen, J. B.,GPM/GPMNLC Extended Gradient Projection Method Nonlinear Programming Subroutines, University of Wisconsin, Academic Computer Center, 1971.
Himmelblau, D. M., Private Communication, 1975.
Duffin, R. J., andPeterson, E. L.,Reserved Geometric Programs Treated by Harmonic Means, Carnegie-Mellon University, Research Report No. 71–79, 1971.
Dembo, R. S.,Some Real-World Applications of Geometric Programming, Applied Geometric Programming, Edited by C. S. Beightler and D. T. Phillips, Prentice-Hall, Englewood Cliffs, New Jersey, 1976.
Reklaitis, G. V.,Singularity in Differentiable Optimization Theory: Differential Algorithm for Posynomial Programs, Stanford University, PhD Thesis, 1969.
Reklaitis, G. V., andWilde, D. J.,A Differentiable Algorithm for Posynomial Programs, DECHEMA Monographien, Vol. 67, pp. 503–542, 1971.
Reklaitis, G. V., andWilde, D. J.,Geometric Programming via a Primal Auxiliary Problem, AIIE Transactions, Vol. 6, 1974.
Wilde, D. J., andBeightler, D. D.,Foundations of Optimization, Prentice-Hall, Englewood Cliffs, New Jersey, 1967.
Duffin, R. J.,Linearizing Geometric Programs, SIAM Review, Vol. 12, pp. 211–227, 1970.
Reklaitis, G. V., Private Communication, 1976.
Gochet, W., andSmeers, Y.,On the Use of Linear Programs to Solve Prototype Geometric Programs, Katholieke Universiteit te Leuven, Center for Operations Research and Econometrics, Discussion Paper No. 7229, 1972.
Dawkins, G. S., McInnis, B. C., andMoonat, S. K.,Solution to Geometric programming Problems by Transformation to Convex Programming Problems, International Journal of Solid Structures, Vol. 10, pp. 135–136, 1974.
Hartley, H. O., andHocking, R. R.,Convex Programming by Tangential Approximation, Management Science, Vol. 9, pp. 600–612, 1963.
Ecker, J. G., andZoracki, M. J.,An Easy Primal Method for Geometric Programming, Management Science, Vol. 23, pp. 71–77, 1976.
Dinkel, J. J.,Elliott, W. H., andKochenberger, G. A.,A Linear Programming Approach to Geometric Programs, Naval Research Logistics Quarterly (to appear).
Frank, C. J.,An Algorithm for Geometric Programming, Recent Advances in Optimization Techniques, Edited by D. D. Lavi and D. D. Vogel, John Wiley and Sons, New York, 1966.
Frank, C. J.,Development of a Computer Program for Geometric Programming, Westinghouse Report No. 64-1, HO-124-R2, 1964.
Hooke, R., andJeeves, T. A.,Direct Search Solution of Numerical and Statistical Problems, Journal of the Association for Computing Machinery, Vol. 8, pp. 212–219, 1961.
Blau, G. E., andWilde, D. J.,A Lagrangean Algorithm for Equality Constrained Generalized Polynomial Optimization, AIChE Journal, Vol. 17, pp. 235–240, 1971.
Kuester, J. L., andMize, J. H.,Optimization Techniques with FORTRAN Programs, McGraw-Hill Book Company, New York, New York, 1973.
Westley, G. W.,A Geometric Programming Algorithm, Oak Ridge National Laboratory, Technical Report No. ORNL-4650, 1971.
Murtagh, B. A., andSargent, R. W. H.,A Constrained Minimization Method with Quadratic Convergence, Optimization, Edited by R. Fletcher, Academic Press, London, 1969.
Templeman, A. B., Wilson, A. J., andWinterbottom, S. K.,SIGNOPT—A Computer Code for Solving Signomial Geometric Programming Problems, University of Liverpool, Department of Civil Engineering, Research Report, 1972.
Fletcher, R., andReeves, C. M.,Function Minimization by Conjugate Gradients, Computer Journal, Vol. 7, pp. 149–154, 1964.
Jefferson, T.,Geometric Programming, with an Application to Transportation Planning, Northwestern University, PhD Thesis, 1972.
Jefferson, T.,Manual for the Geometric Programming Code GPROG (CDC) VERSION 2, University of New South Wales, Australia, Mechanical and Industrial Engineering Department, Report No. 1974/OR/2, 1974.
Duffin, R. J., andPeterson, E. L.,Geometric Programs Treated with Slack Variables, Applied Analysis, Vol. 2, pp. 255–267, 1972.
Kochenberger:, G. A., Woolsey, R. E. D., andMcCarl, B. A.,On the Solution of Geometric Programs via Separable Programming, Operations Research Quarterly, Vol. 24, pp. 285–296, 1973.
Bradley, J.,An Algorithm for the Numerical Solution of Prototype Geometric Programs, Institute of Industrial Research and Standards, Dublin, Ireland, 1973.
Dinkel, J. J., Kochenberger, G. A., andMcCarl, B. A.,An Approach to the Numerical Solution of Geometric Programs, Mathematical Programming, Vol., pp. 181–190, 1974.
McNamara, J. R.,A Solution Procedure for Geometric Programming, Operations Research, Vol. 24, pp. 15–25, 1976.
Duffin, R. J., andPeterson, E. L.,The Proximity of (Algebraic) Geometric Programming to Linear Programming, Mathematical Programming, Vol. 3, pp. 250–253, 1972.
Shapley, M., andCutler, L.,Rand's Chemical Composition Program—A Manual, The Rand Corporation, Report No. 495-PR, 1970.
Clasen, R. J.,The Numerical Solution of the Chemical Equilibrium Problem, The Rand Corporation, Report No. 4345-PR, 1965.
Author information
Authors and Affiliations
Additional information
Communicated by M. Avriel
This work was supported in part by the National Research Council of Canada, Grant No. A-3552, Canada Council Grant No. S74-0418, and a research grant from the School of Organization and Management, Yale University. The author wishes to thank D. Himmelblau, T. Jefferson, M. Rijckaert, X. M. Martens, A. Templeman, J. J. Dinkel, G. Kochenberger, M. Ratner, L. Lasdon, and A. Jain for their cooperation in making the comparative study possible.
Rights and permissions
About this article
Cite this article
Dembo, R.S. Current state of the art of algorithms and computer software for geometric programming. J Optim Theory Appl 26, 149–183 (1978). https://doi.org/10.1007/BF00933402
Issue Date:
DOI: https://doi.org/10.1007/BF00933402