×

Active set strategies in an ellipsoid algorithm for nonlinear programming. (English) Zbl 1061.90106

Summary: The classical ellipsoid algorithm solves convex nonlinear programming problems having feasible sets of full dimension. Convergence is certain only for the convex case [H.-J. Lüthi, Math. Oper. Res. 10, 515– (1985; Zbl 0586.49016)], but the algorithm often works in practice for nonconvex problems as well [SIAM J. Control Optim. 23, 657 (1985)]. Shah’s algorithm [Comput. Oper. Res. 20, 85 (2001)] modifies the classical method to permit the solution of nonlinear programs including equality constraints. This paper describes a robust restarting procedure for Shah’s algorithm and investigates two active set strategies to improve computational efficiency. Experimental results are presented to show the new algorithm is effective, and usually faster than Shah’s algorithm, for a wide variety of convex and nonconvex nonlinear programs with inequality and equality constraints. We also demonstrate that the algorithm can be used to solve systems of nonlinear equations and inequalities, including Karush-Kuhn-Tucker conditions.

MSC:

90C30 Nonlinear programming
90C51 Interior-point methods

Citations:

Zbl 0586.49016
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shor, N. Z., Cut-off method with space extension in convex programming problems, Cybernetics, 12, 94-96 (1977)
[2] Ecker, J. G.; Kupferschmid, M., Introduction to operations research (1988), Krieger: Krieger Malabar, FL · Zbl 0647.90053
[3] Shah S. An ellipsoid algorithm for equality-constrained nonlinear programs. Phd dissertation, Rensselaer Polytechnic Institute, Troy, NY, 1998.; Shah S. An ellipsoid algorithm for equality-constrained nonlinear programs. Phd dissertation, Rensselaer Polytechnic Institute, Troy, NY, 1998.
[4] Rugenstein EK. Active set strategies and an ellipsoid algorithm for general nonlinear programming problems. Phd dissertation, Rensselaer Polytechnic Institute, Troy, NY, 2002.; Rugenstein EK. Active set strategies and an ellipsoid algorithm for general nonlinear programming problems. Phd dissertation, Rensselaer Polytechnic Institute, Troy, NY, 2002.
[5] Dziuban ST. Ellipsoid algorithm variants in nonlinear programming. Phd dissertation, Rensselaer Polytechnic Institute, Troy, NY, 1983.; Dziuban ST. Ellipsoid algorithm variants in nonlinear programming. Phd dissertation, Rensselaer Polytechnic Institute, Troy, NY, 1983.
[6] Fang, S.-. C.; Puthenpura, S., Linear optimization and extensions: theory and algorithms (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[7] Eason ED, Fenton RG. Testing and evaluation of numerical methods for design optimization. UTME-TP 7204. Toronto, Ont., Canada: University of Toronto, 1972.; Eason ED, Fenton RG. Testing and evaluation of numerical methods for design optimization. UTME-TP 7204. Toronto, Ont., Canada: University of Toronto, 1972.
[8] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Programming Ser. A, 91, 201-213 (2002) · Zbl 1049.90004
[9] Crowder, H.; Dembo, R. S.; Mulvey, J. M., On reporting computational experiments with mathematical software, ACM Trans Math Software, 5, 193-203 (1979)
[10] Hock, W.; Schittkowski, K., Test examples for nonlinear programming, Lecture notes in economics and mathematical systems, vol. 187 (1981), Springer: Springer New York · Zbl 0452.90038
[11] Colville AR. A comparative study on nonlinear programming codes. New York Scientific Center Report 320-2949. New York: International Business Machines, 1968.; Colville AR. A comparative study on nonlinear programming codes. New York Scientific Center Report 320-2949. New York: International Business Machines, 1968.
[12] Dembo, R. S., A set of geometric programming test problems and their solutions, Math Programming, 10, 192-213 (1976) · Zbl 0349.90066
[13] Himmelblau, D. M., Applied nonlinear programming (1972), McGraw-Hill: McGraw-Hill New York · Zbl 0521.93057
[14] Rijckaert, M. J.; Martens, X. M., Comparison of generalized geometric programming algorithms. Advances in geometric programming (1980), Plenum Press: Plenum Press New York · Zbl 0444.49028
[15] Floudas, C.; Pardalos, P.; Adjiman, C.; Esposito, W.; Gumus, Z.; Harding, S.; Klepeis, J.; Meyer, C.; Schweiger, C., Handbook of test problems in local and global optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 0943.90001
[16] Ben-Israel, A.; Ben-Tal, A.; Zlobec, S., Optimality in nonlinear programming (1981), Wiley: Wiley New York
[17] Branin, F. H., Widely convergent method for finding multiple solutions of simultaneous equations, IBM J Res Dev, 16, 504-522 (1972) · Zbl 0271.65034
[18] Bracken, J.; McCormick, G. P., Selected applications of nonlinear programming (1968), Wiley: Wiley New York
[19] Bazaraa, M. S.; Sherali, H. D.; Shetti, C. M., Nonlinear programming theory and algorithms (1993), Wiley: Wiley New York
[20] Ben-Tal, A.; Eiger, G.; Gershovitz, V., Global minimization by reducing the duality gap, Math Programming, 63, 193-212 (1994) · Zbl 0807.90101
[21] Hald, J.; Madsen, K., Methods for minimax optimization, Math Programming, 20, 49-62 (1981) · Zbl 0441.90097
[22] Ecker, J. G., A geometric programming model for optimal allocation of stream dissolved oxygen, Manage Sci, 21, 658-668 (1975) · Zbl 0305.90060
[23] Wong KP. Decentralized planning by vertical decomposition of an economic system: a nonlinear programming approach. Phd dissertation, National Economic Planning Institute, University of Birmingham, Birmingham, England, 1970.; Wong KP. Decentralized planning by vertical decomposition of an economic system: a nonlinear programming approach. Phd dissertation, National Economic Planning Institute, University of Birmingham, Birmingham, England, 1970.
[24] Ecker, J. G.; Kupferschmid, M., A computational comparison of the ellipsoid algorithm with several nonlinear programming algorithms, SIAM J Control Optim, 23, 657-674 (1985) · Zbl 0581.90078
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.