Article | 3rd International Workshop on Equation-Based Object-Oriented Modeling Languages and Tools; Oslo; Norway; October 3 | Towards a Computer Algebra System with Automatic Differentiation for use with Object-Oriented modelling languages

Title:
Towards a Computer Algebra System with Automatic Differentiation for use with Object-Oriented modelling languages
Author:
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
Download:
Full text (pdf)
Year:
2010
Conference:
3rd International Workshop on Equation-Based Object-Oriented Modeling Languages and Tools; Oslo; Norway; October 3
Issue:
047
Article no.:
011
Pages:
99-105
No. of pages:
7
Publication type:
Abstract and Fulltext
Published:
2010-09-21
ISBN:
978-91-7519-824-8
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press; Linköpings universitet


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.

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

3rd International Workshop on Equation-Based Object-Oriented Modeling Languages and Tools; Oslo; Norway; October 3

Author:
Joel Andersson, Boris Houska, Moritz Diehl
Title:
Towards a Computer Algebra System with Automatic Differentiation for use with Object-Oriented modelling languages
References:

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

3rd International Workshop on Equation-Based Object-Oriented Modeling Languages and Tools; Oslo; Norway; October 3

Author:
Joel Andersson, Boris Houska, Moritz Diehl
Title:
Towards a Computer Algebra System with Automatic Differentiation for use with Object-Oriented modelling languages
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment