Konferensartikel

Towards a Computer Algebra System with Automatic Differentiation for use with Object-Oriented modelling languages

Joel Andersson
Department of Electrical Engineering and Optimization in Engineering Center (OPTEC), K.U. Leuven, Belgium

Boris Houska
Department of Electrical Engineering and Optimization in Engineering Center (OPTEC), K.U. Leuven, Belgium

Moritz Diehl
Department of Electrical Engineering and Optimization in Engineering Center (OPTEC), K.U. Leuven, Belgium

Ladda ner artikel

Ingår i: 3rd International Workshop on Equation-Based Object-Oriented Modeling Languages and Tools; Oslo; Norway; October 3

Linköping Electronic Conference Proceedings 47:11, s. 99-105

Visa mer +

Publicerad: 2010-09-21

ISBN: 978-91-7519-824-8

ISSN: 1650-3686 (tryckt), 1650-3740 (online)

Abstract

The Directed Acyclic Graph (DAG); which can be generated by object oriented modelling languages; is often the most natural way of representing and manipulating a dynamic optimization problem. With this representation; it is possible to step-by-step reformulate an (infinite dimensional) dynamic optimization problem into a (finite dimensional) non-linear program (NLP) by parametrizing the state and control trajectories.

We introduce CasADi; a minimalistic computer algebra system written in completely self-contained C++. The aim of the tool is to offer the benifits of a computer algebra to developers of C++ code; without the overhead usually associated with such systems. In particular; we use the tool to implement automatic differentiation; AD.

For maximum efficiency; CasADi works with two different graph representations interchangeably: One supporting only scalar-valued; built-in unary and binary operations and no branching; similar to the representation used by today’s tools for automatic differentiation by operator overloading. Secondly; a representation supporting matrixvalued operations; branchings such as if-statements as well as function calls to arbitrary functions (e.g. ODE/DAE integrators).

We show that the tool performs favorably compared to CppAD and ADOL-C; two state-of-the-art tools for AD by operator overloading. We also show how the tool can be used to solve a simple optimal control problem; minimal fuel rocket flight; by implementing a simple ODE integrator with sensitivity capabilities and solving the problem with the NLP solver IPOPT. In the last example; we show how we can use the tool to couple the modelling tool Jmodelica with the optimal control software ACADO Toolkit.

Nyckelord

computer algebra system; automatic differentiation; algorithmic differentiation; dynamic optimization; Modelica

Referenser

[1] Johan Åkesson; Torbjörn Ekman; and Görel Hedin. Implementation of a modelica compiler using jastadd attributegrammars. Science of Computer Programming; 75(1-2):21 – 38; 2010. Special Issue on ETAPS 2006 and 2007 Workshops on Language Descriptions; Tools; and Applications (LDTA ’06 and ’07).

[2] Andrei Alexandrescu. Modern C++ Design. Addison- Wesley; 2008.

[3] Andreas Griewank and David Juedes and Jean Utke. Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++. ACM Trans. Math. Softw.; 22(2):131–167; 1996.

[4] Lorenz T. Biegler. An overview of simultaneous strategies for dynamic optimization. Chemical Engineering and Processing: Process Intensification; 46(11):1043–1053; 2007. Special Issue on Process Optimization and Control in Chemical Engineering and Processing.

[5] Christian H. Bischof and Paul D. Hovland and Boyana Norris. Implementation of automatic differentiation tools (invited talk). j-SIGPLAN; 37(3):98–107; March 2002. Proceedings of the 2002 ACM SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation (PEPM’02).

[6] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; and Clifford Stein. Introduction to Algorithms. MIT Press and McGraw-Hill; 2001.

[7] M. Grant and S. Boyd. Graph implementations for nonsmooth convex programs. In V. Blondel; S. Boyd; and H. Kimura; editors; Recent Advances in Learning and Control; Lecture Notes in Control and Information Sciences; pages 95–110. Springer-Verlag Limited; 2008.

[8] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming; version 1.21. http: //cvxr.com/cvx; May 2010.

[9] Andreas Griewank and Andrea Walther. Evaluating Derivatives. SIAM; 2008.

[10] A. C. Hindmarsh; P. N. Brown; K. E. Grant; S. L. Lee; R. Serban; D. E. Shumaker; and C. S. Woodward. Sundials: Suite of nonlinear and differential/algebraic equation solvers. ACM Transactions on Mathematical Software; 2005.

[11] Boris Houska; Hans Joachim Ferreau; and Moritz Diehl. Acado toolkit - an open-source framework for automatic control and dynamic optimization. Optimal Control Methods and Application; 2010.

[12] Jan Albersmeyer and Moritz Diehl. The Lifted Newton Method and Its Application in Optimization. SIAM J. Optim; 20(3):1655–1684; 2010.

[13] Monagan; Michael B. and Neuenschwander; Walter M. GRADIENT: algorithmic differentiation inMaple. In ISSAC ’93: Proceedings of the 1993 international symposium on Symbolic and algebraic computation; pages 68–76; New York; NY; USA; 1993. ACM.

[14] Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer; August 2000.

[15] Lee Thomason; Yves Berquin; and Andrew Ellerton. Tinyxml; version 2.6.0. http://www.grinninglizard. com/tinyxml/; May 2010.

[16] A. Wächter and L. T. Biegler. On the implementation of an interior-point filter line-search algorithm for largescale nonlinear programming. Mathematical Programming; 106(1):25–57; 2006.

Citeringar i Crossref