×

CONOPT: A GRG code for large sparse dynamic nonlinear optimization problems. (English) Zbl 0557.90088

Summary: The paper presents CONOPT, an optimization system for static and dynamic large-scale nonlinearly constrained optimization problems. The system is based on the GRG algorithm. All computations involving the Jacobian of the constraints use sparse-matrix algorithms from linear programming, modified to deal with the nonlinearity and to take maximum advantage of the periodic structure in dynamic models. The paper presents the main features of the system, especially the inversion routines and their data structures, the dynamic setting of tolerances in Newton’s algorithm, and the user features in the overall packaging. The difficulties with implementing a practical GRG algorithm are described in detail. Computational experience with some medium to large models is presented, indicating the viability of CONOPT for certain real-life problems, particularly those involving almost as many constraints as variables.

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
49M37 Numerical methods based on nonlinear programming
90C52 Methods of reduced gradient type
90C06 Large-scale problems in mathematical programming

Software:

MINOS; CONOPT; DEVEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Abadie, ”Optimization problems with coupled blocks”,Economic Cybernetics Studies and Research (1970b). · Zbl 0249.90068
[2] J. Abadie, ”Application of the GRG algorithm to optimal control problems”, in: J. Abadie, ed.,Nonlinear and integer programming (North-Holland, Amseterdam, 1972) pp. 191–211.
[3] J. Abadie and J. Carpentier, ”Generalization of the Wolfe reduced gradient method to the cases of nonlinear constraints”, in R. Fletcher, ed.,Optimization (Academic Press, New York, 1969), pp. 37–47. · Zbl 0254.90049
[4] P.O. Beck and L.S. Lasdon, ”Scaling nonlinear programs”,Operations Research Letters 1 (1981) 6–9. · Zbl 0491.90083 · doi:10.1016/0167-6377(81)90016-X
[5] J. Bisschop and A. Meeraus, ”On the development of a general algebraic modeling system in a strategic planning environment”,Mathematical Programming Study 20 (1982) 1–29.
[6] T. Cauchois, ”The world coffee model”, M.Sc. Diss.,Massachusetts Institute of Technology (Cambridge, MA, 1980).
[7] C.F. Coleman and J.J. More. ”Estimation of sparse jacobian matrices and graph coloring problems”,SIAM Journal of Numerical Analysis (1983) 187–209. · Zbl 0527.65033
[8] A.R. Colville, ”A comparative study of nonlinear programming codes”, in: H.W. Kuhn, ed.,Proceedings of the princeton Symposium on Mathematical Programming (Princeton University Press, 1970). · Zbl 0224.90069
[9] A.R. Curtis, M.J.D. Powell and J.K. Reid, ”On the estimation of sparse jacobian matrices”,Journal of the Institute of Mathematics and its Applications 13 (1974) 117–119. · Zbl 0273.65036
[10] R.S. Dembo and S. Sahi, ”A globally convergent framework for linearly constrained nonlinear optimization”, Working Paper B69, Yale School of Organization and Management, Yale University (New Haven, CT, 1983).
[11] A. Drud, ”Optimization in large partly nonlinear systems”, in: J. Cea, ed.,Optimization techniques. Modeling and optimization in the service of Man, Part 2, Lecture notes in computer science, Vol. 41 (Springer-Verlag, Berlin, Heidelberg, New York, 1976) 312–329.
[12] A. Drud and A. Meeraus, ”CONOPT–A system for large-scale dynamic optimization–User’s guide”, Technical note 16, Development Research Center, World Bank (Washington, DC, 1980).
[13] R. Fourer, ”Solving staircase linear programs by the simplex method, Part UI: Inversion”,Mathematical Programming 23 (1983) 274–313. · Zbl 0487.90076 · doi:10.1007/BF01583795
[14] C.B. Garcia and W.I. Zangwill,Pathways to solutions, fixed points, and equilibria (Prentice-Hall, NJ, 1983).
[15] A. Gelb, ”Oil rent and development strategies: A model for Indonesia”, Development Research Department, World Bank (Washington, DC, 1983).
[16] P.M.J. Harris, ”Pivot selection methods of the devex LP code”,Mathematical Programming 5 (1973) 1–28. · Zbl 0261.90031 · doi:10.1007/BF01580108
[17] E. Hellerman and D. Rarick, ”Reinversion with the preassigned pivot procedure”,Mathematical Programming 1 (1971) 195–216. · Zbl 0246.65022 · doi:10.1007/BF01584086
[18] E. Hellerman and D. Rarick, ”The partitioned preassigned pivot procedure”, in: D.J. Rose and R.A. Willoughby, eds.,Sparse matrices and their applications (Plenum Press, New York, 1972) pp. 67–76. · Zbl 0246.65022
[19] J.E. Kalan, ”Aspects of large-scale in-core linear programming”, in:Proceedings of ACM conference, Chicago, 1971, pp. 304–313.
[20] L.S. Lasdon, A.D. Waren, A. Jain and M. Ratner, ”Design and testing of a generalized reduced gradient code for nonlinear programming”,ACM Transactions on Mathematical Software 4 (1978) 34–50. · Zbl 0378.90080 · doi:10.1145/355769.355773
[21] L.S. Lasdon and N.H. Kim, ”SLP User’s Guide”, Department of General Business, School of Business Administration, University of Texas, (Austin, Texas, 1983).
[22] J.B. Mantell and L.S. Lasdon, ”A GRG algorithm for econometric control problems”,Annals of Economic and Social Measurement 6 (1978) 581–597.
[23] B.A. Murtagh and M.A. Saunder, ”Large-scale linearly constrained optimization”,Mathematical Programming 14 (1978) 41–72. · Zbl 0383.90074 · doi:10.1007/BF01588950
[24] B.A. Murtagh and M.A. Saunders, ”MINOS/AUGMENTED user’s manual”, Report SOL 80-14 (1980), Department of Operations Research, Stanford University, Stanford, CA.
[25] B.A. Murtagh and M.A. Saunders, ”A projected larrangian algorithm and its implementation for sparse nonlinear constraints”,Mathematical Programming Study 16 (1982) 84–117. · Zbl 0477.90069 · doi:10.1007/BFb0120949
[26] B.A. Murtagh and M.A. Sauders, MINOS 5.0 User’s Guide”, Report SOL 83-20 (1983). Department of Operations Research, Stanford University, Stanford, CA.
[27] R.S. Pindyck, ”Gains to producers from the cartelization of exhaustible resources”,Review of Economics and Statistics 60 (1978) 238–251. · doi:10.2307/1924977
[28] M.J.D. Powell, ”A hybrid method for nonlinear equations”, and ”AFortran subrotine for solving systems of nonlinear algebraic equations”, in: P. Rabinowitz, ed.,Numerical methods for nonlinear algebraic equations (Gordon and Breach, London, 1970).
[29] K. Schittkowski,Nonlinear programming codes. Lecture Note in Economics and Mathematical Systems, vol. 183 (Springer-Verlag, Berlin, Heidelberg, New York, 1980). · Zbl 0435.90063
[30] ”APEX III Reference Manual Version 1.2”, CDC Manual 76070000.
[31] ”Mathematical Programming System-Extended (MPSX), and Generalized Upper Bounding (GUB)”, IBM manual SH20-0968-1.
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.