A primal-dual Newton-type algorithm for geometric programs with equality constraints. (English) Zbl 0573.90078
An augmented Lagrangian algorithm is used to find local solutions of geometric programming problems with equality constraints (GPE). The algorithm is Newton’s method for unconstrained minimization. The complexity of the algorithm is defined by the number of multiplications and divisions. By analyzing the algorithm we obtain results about the influence of each parameter in the GPE problem on the complexity of an iteration. An attempt is made to estimate the number of iterations needed for convergence. Practically, certain hypotheses are tested, such as the influence of the penalty coefficient update formula, the distance of the starting point from the optimum, and the stopping criterion. For these tests, a random problem generator was constructed, plenty of problems were run, and the results were analyzed by statistical methods.
MSC:
| 90C30 | Nonlinear programming |
| 90C99 | Mathematical programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
computational experience; augmented Lagrangian algorithm; local solutions of geometric programming; equality constraints; Newton’s method; complexity of the algorithm; random problem generatorSoftware:
SPSSReferences:
| [1] | Tapia, R. A.,Diagonalized Multiplier Methods and Quasi-Newton Methods for Constrained Optimization, Journal of Optimization Theory and Applications, Vol. 22, pp. 135-194, 1977. · Zbl 0336.65034 · doi:10.1007/BF00933161 |
| [2] | Blau, G. E., andWilde, D. J.,A Lagrangian Algorithm for Equality Constrained Generalized Polynomial Optimization, AIChE Journal, Vol. 17, pp. 235-240, 1971. · doi:10.1002/aic.690170145 |
| [3] | Rijckaert, M. J.,Engineering Applications of Geometric Programming, Part 2, Optimization and Design, Edited by M. Avriel, M. J. Rijckaert, and D. J. Wilde, Prentice-Hall, Englewood Cliffs, New Jersey, 1971. |
| [4] | Rijckaert, M. J., andMartens, X. M.,A Comparison of Generalized Geometric Programming Algorithms, Journal of Optimization Theory and Applications, Vol. 26, pp. 205-242, 1978. · Zbl 0369.90112 · doi:10.1007/BF00933404 |
| [5] | Abrams, R. A.,Consistency, Superconsistency, and Dual Degeneracy in Posynomial Geometric Programming, Operations Research, Vol. 24, pp. 325-335, 1976. · Zbl 0348.90119 · doi:10.1287/opre.24.2.325 |
| [6] | Beightler, C. S., andPhilips, D. T.,Applied Geometric Programming, John Wiley and Sons, New York, New York, 1976. · Zbl 0344.90034 |
| [7] | Bertsekas, D. P.,Multiplier Methods: A Survey, Automatica, Vol. 12, pp. 133-145, 1976. · Zbl 0321.49027 · doi:10.1016/0005-1098(76)90077-7 |
| [8] | Tapia, R. A.,A Stable Approach to Newton’s Method for General Mathematical Programming Problems in R n , Journal of Optimization Theory and Applications, Vol. 14, pp. 453-476, 1974. · Zbl 0272.65045 · doi:10.1007/BF00932842 |
| [9] | Buys, J. D.,Dual Algorithms for Constrained Optimization, University of Leiden, PhD Thesis, 1972. |
| [10] | Hestenes, M. R.,Multiplier and Gradient Methods, Journal of Optimization Theory and Applications, Vol. 4, pp. 303-320, 1969. · Zbl 0174.20705 · doi:10.1007/BF00927673 |
| [11] | Avriel, M.,Nonlinear Programming, Prentice-Hall, Englewood Cliffs, New Jersey, 1976. · Zbl 0361.90035 |
| [12] | Powell, M. J. D.,A Method for Nonlinear Constraints in Minimization Problems, Optimization, Edited by R. Fletcher, Academic Press, London, England, 1969. · Zbl 0194.47701 |
| [13] | Powell, M. J. D.,Algorithm for Nonlinear Constraints That Use Lagrangian Functions, Mathematical Programming, Vol. 14, pp. 224-248, 1978. · Zbl 0383.90092 · doi:10.1007/BF01588967 |
| [14] | Kort, B. W.,Combined Primal-Dual and Penalty Function Algorithms for Nonlinear Programming, Stanford University, PhD Thesis, 1975. |
| [15] | Rockafellar, R. T.,Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming, SIAM Journal of Control, Vol. 12, pp. 268-284, 1974. · doi:10.1137/0312021 |
| [16] | Glad, T., andPolak, E.,A Multiplier Method with Automatic Limitation on Penalty Growth, Mathematical Programming, Vol. 17, pp. 140-155, 1979. · Zbl 0414.90078 · doi:10.1007/BF01588240 |
| [17] | Bunch, J. R., Kaufman, L., andParlett, B. N.,Decomposition of a Symmetric Matrix, Numerische Mathematik, Vol. 27, pp. 95-109, 1976. · Zbl 0342.65026 · doi:10.1007/BF01399088 |
| [18] | Ortega, J. M., andRheinboldt, W. C.,Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970. · Zbl 0241.65046 |
| [19] | More, J. J., andSorensen, D. C.,Newton’s Method, Argonne National Laboratory, Argonne, Illinois, Report No. ANL-82-8, 1982. |
| [20] | Crowder, H. P., Dembo, R. S., andMulvey, J. M.,Reporting Computational Experiments in Mathematical Programming, Mathematical Programming, Vol. 15, pp. 316-329, 1978. · Zbl 0389.65031 · doi:10.1007/BF01609036 |
| [21] | Ratner, M., Lasdon, L. S., andJain, A.,Solving Geometric Programs Using GRG: Results and Comparisons, Advances in Geometric Programming, Edited by M. Avriel, Plenum Press, New York, New York, 1980. · Zbl 0442.49024 |
| [22] | Colville, A. R.,A Comparative Study of Nonlinear Programming Codes, IBM, New York Scientific Center, Report No. 320-2949, 1968. · Zbl 0224.90069 |
| [23] | Lidor, G.,Test Problem Generator for Nonlinear Programming Algorithms, City College, New York, New York, Department of Computer Sciences, 1979. |
| [24] | Nie, N. E., Hull, C. H., Jenkins, J. G., Steinbrenner, K., andBent, O. H.,SPSS?Statistical Package for the Social Sciences, McGraw-Hill, New York, New York, 1975. |
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.
