Object library of algorithms for dynamic optimization problems: benchmarking SQP and nonlinear interior point methods

Jacek Błaszczyk; Andrzej Karbowski; Krzysztof Malinowski

International Journal of Applied Mathematics and Computer Science (2007)

  • Volume: 17, Issue: 4, page 515-537
  • ISSN: 1641-876X

Abstract

top
The main purpose of this paper is to describe the design, implementation and possibilities of our object-oriented library of algorithms for dynamic optimization problems. We briefly present library classes for the formulation and manipulation of dynamic optimization problems, and give a general survey of solver classes for unconstrained and constrained optimization. We also demonstrate methods of derivative evaluation that we used, in particular automatic differentiation. Further, we briefly formulate and characterize the class of problems solved by our optimization classes. The solution of dynamic optimization problems with general constraints is performed by transformation into structured large-scale nonlinear programming problems and applying methods for nonlinear optimization. Two main algorithms of solvers for constrained dynamic optimization are presented in detail: the sequential quadratic programming (SQP) exploring the multistage structure of the dynamic optimization problem during the solution of a sequence of quadratic subproblems, and the nonlinear interior-point method implemented in a general-purpose large-scale optimizer IPOPT. At the end, we include a typical numerical example of the application of the constrained solvers to a large-scale discrete-time optimal control problem and we use the performance profiles methodology to compare the efficiency and robustness of different solvers or different options of the same solver. In conclusions, we summarize our experience gathered during the library development.

How to cite

top

Błaszczyk, Jacek, Karbowski, Andrzej, and Malinowski, Krzysztof. "Object library of algorithms for dynamic optimization problems: benchmarking SQP and nonlinear interior point methods." International Journal of Applied Mathematics and Computer Science 17.4 (2007): 515-537. <http://eudml.org/doc/207856>.

@article{Błaszczyk2007,
abstract = {The main purpose of this paper is to describe the design, implementation and possibilities of our object-oriented library of algorithms for dynamic optimization problems. We briefly present library classes for the formulation and manipulation of dynamic optimization problems, and give a general survey of solver classes for unconstrained and constrained optimization. We also demonstrate methods of derivative evaluation that we used, in particular automatic differentiation. Further, we briefly formulate and characterize the class of problems solved by our optimization classes. The solution of dynamic optimization problems with general constraints is performed by transformation into structured large-scale nonlinear programming problems and applying methods for nonlinear optimization. Two main algorithms of solvers for constrained dynamic optimization are presented in detail: the sequential quadratic programming (SQP) exploring the multistage structure of the dynamic optimization problem during the solution of a sequence of quadratic subproblems, and the nonlinear interior-point method implemented in a general-purpose large-scale optimizer IPOPT. At the end, we include a typical numerical example of the application of the constrained solvers to a large-scale discrete-time optimal control problem and we use the performance profiles methodology to compare the efficiency and robustness of different solvers or different options of the same solver. In conclusions, we summarize our experience gathered during the library development.},
author = {Błaszczyk, Jacek, Karbowski, Andrzej, Malinowski, Krzysztof},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {dynamic optimization; object-oriented numerical computations; large-scale optimization; nonlinear interior-point methods; performance data analysis; automatic differentiation; sequential quadratic programming},
language = {eng},
number = {4},
pages = {515-537},
title = {Object library of algorithms for dynamic optimization problems: benchmarking SQP and nonlinear interior point methods},
url = {http://eudml.org/doc/207856},
volume = {17},
year = {2007},
}

TY - JOUR
AU - Błaszczyk, Jacek
AU - Karbowski, Andrzej
AU - Malinowski, Krzysztof
TI - Object library of algorithms for dynamic optimization problems: benchmarking SQP and nonlinear interior point methods
JO - International Journal of Applied Mathematics and Computer Science
PY - 2007
VL - 17
IS - 4
SP - 515
EP - 537
AB - The main purpose of this paper is to describe the design, implementation and possibilities of our object-oriented library of algorithms for dynamic optimization problems. We briefly present library classes for the formulation and manipulation of dynamic optimization problems, and give a general survey of solver classes for unconstrained and constrained optimization. We also demonstrate methods of derivative evaluation that we used, in particular automatic differentiation. Further, we briefly formulate and characterize the class of problems solved by our optimization classes. The solution of dynamic optimization problems with general constraints is performed by transformation into structured large-scale nonlinear programming problems and applying methods for nonlinear optimization. Two main algorithms of solvers for constrained dynamic optimization are presented in detail: the sequential quadratic programming (SQP) exploring the multistage structure of the dynamic optimization problem during the solution of a sequence of quadratic subproblems, and the nonlinear interior-point method implemented in a general-purpose large-scale optimizer IPOPT. At the end, we include a typical numerical example of the application of the constrained solvers to a large-scale discrete-time optimal control problem and we use the performance profiles methodology to compare the efficiency and robustness of different solvers or different options of the same solver. In conclusions, we summarize our experience gathered during the library development.
LA - eng
KW - dynamic optimization; object-oriented numerical computations; large-scale optimization; nonlinear interior-point methods; performance data analysis; automatic differentiation; sequential quadratic programming
UR - http://eudml.org/doc/207856
ER -

References

top
  1. Arnold E. and Puta H. (1994): An SQP-type solution method for constrained discrete-time optimal control problems. In: Computational Optimal Control (R. Bulirsch and D. Kraft, Eds.), Birkhauser Verlag, Basel, Switzerland, pp. 127-136. Zbl0811.49025
  2. Arnold E., Tatjewski P. and Wolochowicz P. (1994): Two methods for large-scale nonlinear optimization and their comparison on a case study of hydropower optimization. Journal of Optimization Theory and Applications, Vol. 81, No. 2, pp. 221-248. Zbl0819.90091
  3. Benson H. Y., Shanno D. F. and Vanderbei R. J. (2001): Interior-point methods for nonconvex nonlinear programming: Filter methods and merit functions. Technical Report ORFE-00-06, Operations Research and Financial Engineering, Princeton University. Available athttp://www.princeton.edu/rvdb/tex/loqo4/loqo4_4.pdf Zbl1022.90017
  4. Benson H. Y., Shanno D. F. and Vanderbei R. J. (2002): A comparative study of large-scale nonlinear optimization algorithms. Technical Report ORFE-01-04, Operations Research and Financial Engineering, Princeton University. Available athttp://www.princeton.edu/rvdb/tex/loqo5/loqo5_5.pdf Zbl1066.90138
  5. Bertsekas D. P. (1982): Projected Newton methods for optimization problems with simple constraints. SIAM Journal on Control and Optimization, Vol. 20, No. 2, pp. 221-246. Zbl0507.49018
  6. Błaszczyk J., Karbowski A. and Malinowski K. (2002a): Object library of algorithms for unconstrained dynamic optimization problems. Proceedings of the 14-th National Conference on Automatic Control (KKA), Vol. I, Zielona Góra, Poland, pp. 451-456. Zbl1234.90022
  7. Błaszczyk J., Karbowski A. and Malinowski K. (2002b): Object library of algorithms for dynamic optimization problems without constraints or with simple bounds on control. Proceedings of the 8th IEEE International Conference on Methods and Models in Automation and Robotics, Vol. 1, Szczecin, Poland, pp. 257-262. 
  8. Błaszczyk J., Karbowski A. and Malinowski K. (2003): Object library of algorithms for dynamic optimization problems with general constraints. Proceedings of the 9th IEEE International Conference on Methods and Models in Automation and Robotics, Vol. 1, Międzyzdroje, Poland, pp. 271-276. 
  9. Bryson A. E. (1998): Dynamic Optimization. Menlo Park CA: Addison-Wesley, p. 550. 
  10. Byrd R. H., Hribar M. E. and J. Nocedal (1999): An interior point algorithm for large scale nonlinear programming. SIAM Journal on Optimization, Vol. 9, No. 4, pp. 877-900. Zbl0957.65057
  11. Byrd R. H., Gilbert J. Ch. and Nocedal J. (2000): A trust region method based on interior point techniques for nonlinear programming. Mathematical Programming, Vol. 89, pp. 149-185. Zbl1033.90152
  12. Chamberlain R. M., Powell M.J.D., Lemarechal C. and Pedersen H.C. (1982): The watchdog technique for forcing convergence in algorithms for constrained optimization. Mathematical Programming Study, Vol. 16, pp. 1-17. Zbl0477.90072
  13. Dolan E. D. and More J. J. (2002): Benchmarking optimization software with performance profiles. Mathematical Programming, Vol. 91, No. 2, pp. 201-213. Zbl1049.90004
  14. Fiacco A. V. and McCormick G. P. (1968): Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley and Sons, New York/London. Zbl0193.18805
  15. Findeisen W., Szymanowski J. and Wierzbicki A. (1980): Theory and Computational Methods of Optimization. Polish Scientific Publishers, Warsaw (in Polish). Zbl0455.49001
  16. Fletcher R. (1987): Practical Methods of Optimization. John Wiley and Sons, New York, NY, USA. Zbl0905.65002
  17. Fletcher R. (1995): An optimal positive definite update for sparse Hessian matrices. SIAM Journal on Optimization, Vol. 5, No. 1, pp. 192-218. Zbl0824.65038
  18. Fletcher R. and Leyffer S. (2002): Nonlinear programming without a penalty function. Mathematical Programming, Vol. 91, No. 2, pp. 239-269. Zbl1049.90088
  19. Fletcher R., Leyffer S. and Toint Ph. L. (2006): A brief history of filter methods. Technical Report ANL/MCS-P1372-0906, Mathematics and Computer Science Division, Argonne National Laboratory. Available at http://www.optimization-online.org/DB_FILE/2006/10/1489.pdf 
  20. Franke R. (1994): Anwendung von Interior-Point-Methoden zur Losung zediskreter Optimalsteuerungsprobleme. M. S. thesis, Techniche Universitat Ilmenau, Fakultat fur Informatik und Automatsierung, Institut fur Automatisierungs- und Systemtechnik Fachgebiet Dynamik und Simulation okologischer Systeme, Ilmenau, Germany, (in German). 
  21. Franke R. (1998): OMUSES - A tool for the optimization of multistage systems and HQP - A solver for sparse nonlinear optimization. Version 1. 5. Department of Automation and Systems Engineering, Technical University of Ilmenau, Germany. Available at ftp://ftp.systemtechnik.tu-ilmenau.de/pub/reports/omuses.ps.gz 
  22. Franke R. and Arnold E. (1997): Applying new numerical algorithms to the solution of discrete-time optimal control problems. In: Computer-Intensive Methods in Control and Signal Processing: The Curse of Dimensionaly, (Warwick K. and Karny M., Eds.), Birkhauser Verlag, Basel, Switzerland, pp. 105-118. 
  23. The solver Omuses/HQP for structured large-scale constrained optimization: Algorithm, implementation, and example application. Proceedings of the 6-th SIAM Conference on Optimization, Atlanta. 
  24. Goldfarb D. and Idnani A. (1983): A numerically stable dual method for solving strictly convex quadratic programs. Mathematical Programming, Vol. 27, No. 1, pp. 1-33. Zbl0537.90081
  25. Gondzio J. (1994): Multiple centraly corrections in a primal-dual method for linear programming. Technical Report. 20, Department of Management Studies, University of Geneva, Geneva, Switzerland. Available at http://www.maths.ed.ac.uk/gondzio/software/correctors.ps 
  26. Griewank A., Juedes D., Mev H., Utke J., Vogel O. and Walther A. (1999): ADOL-C: A package for the automatic differentiation of algorithms written in C/C++, Version 1. 8. 2, March 1999. Available at http://www.math.tu-dresden.de/adol-c/ 
  27. Karmarkar N. (1984): A new polynomial-time algorithm for linear programming. Combinatorica, Vol. 4, No. 4, pp. 373-395. Zbl0557.90065
  28. Luus R. (2000): Iterative Dynamic Programming. CRC Press, Inc., Boca Raton, FL, USA. Zbl1070.49001
  29. Mehrotra S. (1992): On the implementation of a primal-dual interior point method. SIAM Journal on Optimization, Vol. 2, No. 4, pp. 575-601. Zbl0773.90047
  30. Misc J. -P. (2003): Large scale nonconvex optimization. SIAM's SIAG/OPT Newetter Views-and-News, Vol. 14, No. 1, pp. 1-25. Available at http://fewcal.uvt.nl/sturm/siagopt/vn14_1.pdf 
  31. Morales J. L., Nocedal J., Waltz R. A., Liu G. and Goux J. -P. (2001): Assessing the potential of interior methods for nonlinear optimization. Technical Report OTC 2001/4, Optimization Technology Center of Northwestern University. Available at http://www.ece.northwestern.edu/morales/PSfiles/assess.ps Zbl1062.65063
  32. Nocedal J. and Wright S. J. (1999): Numerical Optimization. Berlin: Springer-Verlag. Zbl0930.65067
  33. De O. Pantoja J.F.A. (1988): Differential dynamic programming and Newton's method. International Journal of Control, Vol. 47, No. 5, pp. 1539-1553. Zbl0669.49014
  34. Powell M. J. D. (1978): A fast algorithm for nonlinearly constrained optimization calculations. In: Numerical Analysis, Dundee (G. A. Watson, Ed.), Dundee: Springer-Verlag, pp. 144-157. Zbl0374.65032
  35. Powell M. J. D. (1985): On the quadratic programming algorithm of Goldfarb and Idnani. Mathematical Programming Study, Vol. 25, pp. 46-61. Zbl0584.90069
  36. Salahi M., Peng J. and Terlaky T. (2005): On Mehrotra-type predictor-corrector algorithms. Technical report, Advanced Optimization Lab, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada. Available at http://www.optimization-online.org/DB_FILE/2005/03/1104.pdf Zbl1165.90569
  37. Schittkowski K. (1980): Nonlinear Programming Codes: Information, Tests, Performance. Berlin: Springer-Verlag. Zbl0435.90063
  38. Schittkowski K. (1983): On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function. Mathematishe Operations Forschung und Statistik, Ser. Optimization, Vol. 14, No. 2, pp. 197-216. Zbl0523.90075
  39. Schwartz A. and Polak E. (1997): Family of projected descent methods for optimization problems with simple bounds. Journal of Optimization Theory and Applications, Vol. 92, No. 1, pp. 1-31. Zbl0886.90140
  40. Tenny M. J., Wright S. J. and Rawlings J. B. (2002): Nonlinear model predictive control via feasibility-perturbed sequential quadratic programming. Technical Report TWMCC-2002-02, Texas-Wisconsin Modeling and Control Consortium. Available at http://jbrwww.che.wisc.edu/jbr-group/tech-reports/twmcc-2002-02.pdf 
  41. Tits A. L., Wachter A., Bakhtiari S., Urban T. J. and Lawrence C. T. (2002): A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties. Technical Report TR 2002-29, Institute for Systems Research, University of Maryland. Available at http://www.ee.umd.edu/andre/pdiprev.ps Zbl1075.90078
  42. Ulbrich M., Ulbrich S. and Vicente L. N. (2004): A globally convergent primal-dual interior-point filter method for nonlinear programming. Mathematical Programming, Vol. 100, No. 2, pp. 379-410. Zbl1070.90110
  43. Vanderbei R. J. and Shanno D. F. (1997): An interior-point algorithm for non-convex nonlinear programming. Technical Report SOR-97-21, Statistics and Operations Research, Princeton University. Available at http://www.sor.princeton.edu/rvdb/ps/nonlin.ps.gz 
  44. Wachter A. (2002): An Interior Point Algorithm forLarge-Scale Nonlinear Optimization with Applications in Process Engineering. Ph. D. dissertation, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA. Available at http://www.research.ibm.com/people/a/andreasw/papers/thesis.pdf 
  45. Wachter A. and Biegler L. T. (2000): Failure of global convergence for a class of interior point methods for nonlinear programming. Mathematical Programming, Vol. 88, No. 3, pp. 565-574. Zbl0963.65063
  46. Wachter A. and Biegler L. T. (2005): Line search filter methods for nonlinear programming: Motivation and global convergence. SIAM Journal on Optimization, Vol. 16, No. 1, pp. 1-31. Zbl1114.90128
  47. Wachter A. and Biegler L. T. (2006): On the implementation of a primal-dual interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, Vol. 106, No. 1, pp. 25-57. Zbl1134.90542
  48. Waltz R. A. and Plantenga T. (2006): KNITRO 5. 0 User's Manual. Available at http://www.ziena.com/docs/knroman.pdf. 
  49. Wierzbicki A. (1984): Models and Sensitivy of Control Systems. Elsevier, Amsterdam. 
  50. Wright S. J. (1993): Interior point methods for optimal control of discrete time systems. Journal of Optimization Theory and Applications, Vol. 77, No. 1, pp. 161-187. Zbl0796.49034
  51. Wright S. J. (1997): Primal-Dual Interior-Point Methods. SIAM, Philadelphia, PA. Zbl0863.65031
  52. Yakowz S. and Rutherford B. (1984): Computational aspects of discrete-time optimal control. Applied Mathematics and Computation, Vol. 15, No. 1, pp. 29-45 Zbl0554.90098

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.