Skip to main content
SpringerLink
Log in

CONOPT: A GRG code for large sparse dynamic nonlinear optimization problems

  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Abadie, “Optimization problems with coupled blocks”,Economic Cybernetics Studies and Research (1970b).

  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.

    Google Scholar 

  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.

    Google Scholar 

  4. P.O. Beck and L.S. Lasdon, “Scaling nonlinear programs”,Operations Research Letters 1 (1981) 6–9.

    Article  MATH  Google Scholar 

  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.

    Google Scholar 

  6. T. Cauchois, “The world coffee model”, M.Sc. Diss.,Massachusetts Institute of Technology (Cambridge, MA, 1980).

    Google Scholar 

  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.

  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).

  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.

    MATH  Google Scholar 

  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).

    Google Scholar 

  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.

    Google Scholar 

  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).

    Google Scholar 

  13. R. Fourer, “Solving staircase linear programs by the simplex method, Part UI: Inversion”,Mathematical Programming 23 (1983) 274–313.

    Article  MathSciNet  Google Scholar 

  14. C.B. Garcia and W.I. Zangwill,Pathways to solutions, fixed points, and equilibria (Prentice-Hall, NJ, 1983).

    Google Scholar 

  15. A. Gelb, “Oil rent and development strategies: A model for Indonesia”, Development Research Department, World Bank (Washington, DC, 1983).

    Google Scholar 

  16. P.M.J. Harris, “Pivot selection methods of the devex LP code”,Mathematical Programming 5 (1973) 1–28.

    Article  MATH  MathSciNet  Google Scholar 

  17. E. Hellerman and D. Rarick, “Reinversion with the preassigned pivot procedure”,Mathematical Programming 1 (1971) 195–216.

    Article  MATH  MathSciNet  Google Scholar 

  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.

    Google Scholar 

  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.

    Article  MATH  Google Scholar 

  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).

    Google Scholar 

  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.

    Google Scholar 

  23. B.A. Murtagh and M.A. Saunder, “Large-scale linearly constrained optimization”,Mathematical Programming 14 (1978) 41–72.

    Article  MATH  MathSciNet  Google Scholar 

  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.

    Google Scholar 

  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.

    MATH  MathSciNet  Google Scholar 

  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.

    Google Scholar 

  27. R.S. Pindyck, “Gains to producers from the cartelization of exhaustible resources”,Review of Economics and Statistics 60 (1978) 238–251.

    Article  Google Scholar 

  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).

    Google Scholar 

  29. K. Schittkowski,Nonlinear programming codes. Lecture Note in Economics and Mathematical Systems, vol. 183 (Springer-Verlag, Berlin, Heidelberg, New York, 1980).

    MATH  Google Scholar 

  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.

Download references

Author information

Authors and Affiliations

  1. Development Research Department, The World Bank, 1818 H Street, N.W., 20433, Washington, DC, USA

    Arne Drud

Authors
  1. Arne Drud
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02591747

Key words

Search

Navigation