Advances in Geometric Programming MA THEMA TICAL CONCEPTS AND METHODS IN SCIENCE AND ENGINEERING Series Editor: Angelo Miele Mechanical Engineering and Mathematical Sciences, Rice University INTRODUCTION TO VECTORS AND TENSORS - Volume 1: Linear and Multilinear Algebra c.-c. _ Ray M. Bowen and Wang 2 INTRODUCTION TO VECTORS AND TENSORS - Volume 2: Vector and Tensor Analysis c.-c. - Ray M. Bowen and Wang 3 MULTICRITERIA DECISION MAKING AND DIFFERENTIAL GAMES - haited by George Leitmann 4 ANALYTICAL DYNAMICS OF DISCRETE SYSTEMS _ Reinhardt M. Rosenberg 5 TOPOLOGY AND MAPS _ Taqdir Husain 6 REAL AND FUNCTIONAL ANALYSIS - A. Mukherjea and K. Pothoven 7 PRINCIPLES OF OPTIMAL CONTROL THEORY - R. V. Gamkrelidze 8 INTRODUCTION TO THE LAPLACE TRANSFORM - Peter K. F. KuhJittig 9 MATHEMATICAL LOGIC: An Introduction to Model Theory - A. H. Lightstone 11 INTEGRAL TRANSFORMS IN SCIENCE AND ENGINEERING - Kurt Bernardo Wolf 12 APPLIED MATHEMATICS: An Intellectual Orientation _ Francis J. Murray 14 PRINCIPLES AND PROCEDURES OF NUMERICAL ANALYSIS - Ferenc Szidarovszky and Sidney Yakowitz 16 MATHEMATICAL PRINCIPLES IN MECHANICS AND ELECTROMAGNETISM, c.-c. Part A: Analytical and Continuum Mechanics - Wang 17 MATHEMATICAL PRINCIPLES IN MECHANICS AND ELECTROMAGNETISM, c.-c. Part B: Electromagnetism and Gravitation. Wang 18 SOLUTION METHODS FOR INTEGRAL EQUATIONS: Theory and Applications • Edited by Michael A. Golberg 19 DYNAMIC OPTIMIZATION AND MATHEMATICAL ECONOMICS. h"dited by Pan-Tai Liu 20 DYNAMICAL SYSTEMS AND EVOLUTION EQUATIONS: Theory and Applications • J. A. Walker 21 ADVANCES IN GEOMETRIC PROGRAMMING - Edited by Mordecai Avriel A Continuation Order Plan is available for this series. A continuation order will bring delivery of each new volume immediately upon publication., Volumes are billed only upon actual shipment. For further information please contact the publisher. Advances in Geometric Programming Edited by Mordecai Avriel Technion-Israel Institute of Technology Haifa, Israel PLENUM PRESS . NEW YORK AND LONDON Library of Congress Cataloging in Publication Data Main entry under title: Advances in geometric programming. (Mathematical concepts and methods in science and engineering; v. 21) Includes index. 1. Geometric programming. I. Avriel, M., 1933- T57.825.A33 519.7'6 79-20806 ISBN-13: 978-1-4615-8287-8 e-ISBN-13: 978-1-4615-8285-4 DOl: 10.1007/978-1-4615-8285-4 Acknowledgmen ts Chapter I is reprinted from Lectures in Applied Mathematics, Volume 11, "Math ematics of the decision sciences," Part I, Pages 401-422, by permission of the American Mathematical Society, 1968. Chapter 2 is reprinted with permission from SIAM Review, Vol. 18. Copyright 1976, Society for Industrial and Applied Mathematics. All rights reserved Chapters 3-9 and 17 are reprinted from Journal of Optimization Theory and Applica tions, Vol. 26, No.1, September 1978 Chapter 10 is reprinted from International Journal for NumericalMethods in Engineer ing, Vol. 9,149-168 (1975) Chapters 11-16, 18,20-22 are reprinted from Journal of Optimization Theory and Applications, Vol. 26, No.2, October 1978 Chapter 19 is reprinted from Journal of Optimization Theory and Applications, Vol. 28, No. I, May 1979 © 1980 Plenum Press, New York Softcover reprint of the hardcover 1st edition 1980 A Division of Plenum Publishing Corporation 227 West 17th Street, New York, N.Y. 10011 All rights reserved No part of this book may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, microfilming, recording, or otherwise, without written permission from the publisher Contributors R. A. Abrams, Graduate School of Business, University of Chicago, Chicago, Illinois M. Avriel, Faculty of Industrial Engineering and Management, Technion-Israel Institute of Technology, Haifa, Israel J. D. Barrett, Western Forest Products Laboratory, Vancouver, British Columbia, Canada R. S. Dembo, School of Organization and Management, Yale University, New Haven, Connecticut J. G. Ecker, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York W. Gochet, Department of Applied Economics, Katholieke Universiteit Leuven; and Center for Operations Research and Econometrics, Catholic University of Louvain, Louvain, Belgium M. Hamala, Comenius University, Matematicky Pavilon PFUK, Mlynska dolina, Bratislava, Czechoslovakia A. Jain, Stanford Research Institute, Menlo Park, California T. R. Jefferson, School of Mechanical and Industrial Engineering, University of New South Wales, Kensington, New South Wales, Australia L. S. Lasdon, Departments of General Business and Mechanical Engineering, University of Texas, Austin, Texas G. Lidor, Department of Computer Sciences, The City College, New York, New York L. J. Mancini, Computer Services Department, Standard Oil Company, San Francisco, California x. M. Martens, Instituut voor Chemie-Ingenieurstechniek, Katholieke Universiteit Leuven, Leuven, Belgium U. Passy, Faculty of Industrial Engineering and Management, Technion-Israel Institute of Technology, Haifa, Israel E. L. Peterson, Department of Mathematics and Graduate Program in Operations Research, North Carolina State University, Raleigh, North Carolina v vi Contributors M. Ratner, Computer Science Department, Case Western Reserve University, Cleveland, Ohio G. V. Reklaitis, School of Chemical Engineering, Purdue University, West Lafayette, Indiana M. J. Rijckaert, Instituut voor Chemie-Ingenieurstechniek, Katholieke Universiteit Leuven, Leuven, Belgium P. V. L. N. Sanna, Selas Corporation of America, Dresher, Pennsylvania C. H. Scott, School of Mechanical and Industrial Engineering, University of New South Wales, Kensington, New South Wales, Australia Y. Smeers, Department of Engineering, Universite Catholique de Louvain; and Center for Operations Research and Econometrics, Catholic University of Louvain, Louvain, Belgium R. D. Wiebking, Unternehmensberatung Schumann, GmbH, Cologne, West Germany D. J. Wilde, Department of Mechanical Engineering, Stanford University, Stanford, California C. T. Wu, School of Business Administration, University of Wisconsin Milwaukee, Milwaukee, Wisconsin Preface In 1961, C. Zener, then Director of Science at Westinghouse Corpora tion, and a member of the U.S. National Academy of Sciences who has made important contributions to physics and engineering, published a short article in the Proceedings of the National Academy of Sciences entitled" A Mathe matical Aid in Optimizing Engineering Design." In this article Zener considered the problem of finding an optimal engineering design that can often be expressed as the problem of minimizing a numerical cost function, termed a "generalized polynomial," consisting of a sum of terms, where each term is a product of a positive constant and the design variables, raised to arbitrary powers. He observed that if the number of terms exceeds the number of variables by one, the optimal values of the design variables can be easily found by solving a set of linear equations. Furthermore, certain invariances of the relative contribution of each term to the total cost can be deduced. The mathematical intricacies in Zener's method soon raised the curiosity of R. J. Duffin, the distinguished mathematician from Carnegie Mellon University who joined forces with Zener in laying the rigorous mathematical foundations of optimizing generalized polynomials. Interes tingly, the investigation of optimality conditions and properties of the optimal solutions in such problems were carried out by Duffin and Zener with the aid of inequalities, rather than the more common approach of the Kuhn-Tucker theory. One of the inequalities that they found useful in studying the optimality properties of generalized polynomials is the classical inequality between the arithmetic and geometric means. Because of this inequality, and some more general ones, called "geometric inequalities," Duffin coined the term "geometric programming" for the problem of optimizing generalized polynomials. In 1963, E. L. Peterson, a student of Duffin, started to work on developing the theory of constrained geometric programming problems. Thus a new branch of optimization was born. The significance of the theory developed by Duffin, Peterson, and Zener was recognized very early by D. J. Wilde, then Professor of Chemical Engineering at Stanford University, who was equally interested in optimiz ing engineering design and in the theoretical aspects of optimization. He was fascinated by the simplicity and the potential usefulness of geometric vii Preface programming and urged his two doctoral students M. A vriel and U. Passy to devote parts of their dissertations to geometric programming. These were completed in 1966 and contained topics that served as a kernel from which many future developments have sprouted. In the book Geometric Pro gramming' published in 1967, Duffin, Peterson, and Zener collected their pioneering work. Their book was instrumental in inspiring continued research on theory, computational aspects, and applications. Since the mid-60's, geometric programming has gradually developed into an important branch of nonlinear optimization. The developments include first of all significant extensions of the type of problems that were considered 10 years ago as geometric programs. Also, two-sided relation ships with convex, generalized convex, and non convex programming, separable programming, conjugate functions, and Lagrangian duality were established. Numerical solution methods and their convergence properties were studied. Subsequently, computer software that can handle large con strained problems were developed. Applications of geometric programming to more and more problems of engineering optimization and design and problems from many other diverse areas were demonstrated. In recognition of the important role of geometric programming in optimization, the Journal of Optimization Theory and Applications devoted two special issues to this subject. The majority of works appearing in this volume were first published there. In order to make this book as self contained as possible, three earlier works on geometric programming are also reprinted here. These include (i) the 1968 paper of M. Hamala relating geometric programming duality to conjugate duality, which was originally published as a research report; (ii) the comprehensive survey paper of E. L. Peterson that appeared in 1976 in SIAM Review, and on which his other articles in this book are based; and (iii) the 1975 paper of M. Avriel, R. Dembo, and U. Passy that appeared in the International Journal of Numeri cal Methods in Engineering, describing the GGP algorithm that serves as a prototype of several condensation and linearization-based methods. The permission granted to reprint these works is gratefully acknowledged. (For a more detailed description of the articles in this volume, see the Intro duction.) I wish to express my appreciation to Professor Angelo Miele, Editor-in Chief of the Journal of Optimization Theory and Applications, and Series Editor of the Mathematical Concepts and Methods in Science and Engineer ing texts and monogr~phs, for inviting me to edit the two special issues of JOTA and also this book. Thanks are also due to Mrs. Batya Maayan for assisting me in these projects. Haifa Mordecai Avriel Contents Introduction 1 M Avriel 1. Geometric Programming in Terms of Conjugate Functions 5 M Hamala 2. Geometric Programming . . . . . . . . . . . . . . . 31 E. L. Peterson 3. Optimality Conditions in Generalized Geometric Programming 95 E. L. Peterson 4. Saddle Points and Duality in Generalized Geometric Programming 107 E. L. Peterson 5. Constrained Duality via Unconstrained Duality in Generalized Geometric Programming . . . . . . . . 135 E. L. Peterson 6. Fenchel's Duality Theorem in Generalized Geometric Programming 143 E. L. Peterson 7. Generalized Geometric Programming Applied to Problems of Optimal Control: I. Theory . . . . . . . . . . . . . . . . . . . . . .. 151 T. R. Jefferson and C. H Scott 8. Projection and Restriction Methods in Geometric Programming and Related Problems . . . . . . . . . . . . . . . . . . . . . .. 165 R. A. Abrams and C. T. Wu 9. Transcendental Geometric Programs 183 G. Lidor and D. J. Wilde 10. Solution of Generalized Geometric Programs 203 M Avriel, R. Dembo, and U. Passy 11. Current State of the Art of Algorithms and Computer Software for Geometric Programming . . . . . . . . . . . . . . . . . .. 227 R. S. Dembo 12. A Comparison of Computational Strategies for Geometric Programs 263 P. V. L. N. Sarma, X. M Martens, G. V. Reklaitis, and M. J. Rijckaert 13. Comparison of Generalized Geometric Programming Algorithms 283 M. J. Rijckaert and X. M Martens 14. Solving Geometric Programs Using GRG: Results and Comparisons 321 M. Ratner, L. S. Lasdon, and A. Jain ix x Contents 15. Dual to Primal Conversion in Geometric Programming . . . . . .. 333 R. S. Dembo 16. A Modified Reduced Gradient Method for Dual Posynomial Program- ming ............................ 343 1. G. Ecker, W. Gochet, and Y. Smeers 17. Global Solutions of Mathematical Programs with Intrinsically Concave Functions ....................... 355 U. Passy 18. Interval Arithmetic in Unidimensional Signomial Programming 375 L. 1. Mancini and D. 1. Wilde 19. Signomial Dual Kuhn-Tucker Intervals 389 L. 1. Mancini and D. 1. Wilde 20. Optimal Design of Pitched Laminated Wood Beams . . . . . . .. 407 M. Avriel and 1. D. Barrett 21. Optimal Design of a Dry-Type Natural-Draft Cooling Tower by Geometric Programming . . . . . . . . . . . . . . . . . . 421 1. G. Ecker and R. D. Wiebking 22. Bibliographical Note on Geometric Programming 441 M. 1. Rijckaert and X. M. Martens Index 455