Abstract
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, espcially the inversion routines and their data structures, the dynamic setting of tolerances in Newton’s algorithm, and the user features in the overal packaging. The difficulties with implementing a practical GRG algorithm are described in detail. Computational experience with some medium to large models is presented, idicating the viability of CONOPT for certain real-life problems, particularly those involving almost as many constraints as variables.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
J. Abadie, “Optimization problems with coupled blocks”,Economic Cybernetics Studies and Research (1970b).
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.
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.
P.O. Beck and L.S. Lasdon, “Scaling nonlinear programs”,Operations Research Letters 1 (1981) 6–9.
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.
T. Cauchois, “The world coffee model”, M.Sc. Diss.,Massachusetts Institute of Technology (Cambridge, MA, 1980).
C.F. Coleman and J.J. More. “Estimation of sparse jacobian matrices and graph coloring problems”,SIAM Journal of Numerical Analysis (1983) 187–209.
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).
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.
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).
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.
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).
R. Fourer, “Solving staircase linear programs by the simplex method, Part UI: Inversion”,Mathematical Programming 23 (1983) 274–313.
C.B. Garcia and W.I. Zangwill,Pathways to solutions, fixed points, and equilibria (Prentice-Hall, NJ, 1983).
A. Gelb, “Oil rent and development strategies: A model for Indonesia”, Development Research Department, World Bank (Washington, DC, 1983).
P.M.J. Harris, “Pivot selection methods of the devex LP code”,Mathematical Programming 5 (1973) 1–28.
E. Hellerman and D. Rarick, “Reinversion with the preassigned pivot procedure”,Mathematical Programming 1 (1971) 195–216.
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.
J.E. Kalan, “Aspects of large-scale in-core linear programming”, in:Proceedings of ACM conference, Chicago, 1971, pp. 304–313.
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.
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).
J.B. Mantell and L.S. Lasdon, “A GRG algorithm for econometric control problems”,Annals of Economic and Social Measurement 6 (1978) 581–597.
B.A. Murtagh and M.A. Saunder, “Large-scale linearly constrained optimization”,Mathematical Programming 14 (1978) 41–72.
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.
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.
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.
R.S. Pindyck, “Gains to producers from the cartelization of exhaustible resources”,Review of Economics and Statistics 60 (1978) 238–251.
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).
K. Schittkowski,Nonlinear programming codes. Lecture Note in Economics and Mathematical Systems, vol. 183 (Springer-Verlag, Berlin, Heidelberg, New York, 1980).
“APEX III Reference Manual Version 1.2”, CDC Manual 76070000.
“Mathematical Programming System-Extended (MPSX), and Generalized Upper Bounding (GUB)”, IBM manual SH20-0968-1.
Author information
Authors and Affiliations
Additional information
The views and interpretations in this document are those of the author and should not be attributed to the World Bank, to its affiliated organizations or to any individual acting in their behalf.
Rights and permissions
About this article
Cite this article
Drud, A. CONOPT: A GRG code for large sparse dynamic nonlinear optimization problems. Mathematical Programming 31, 153–191 (1985). https://doi.org/10.1007/BF02591747
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591747