Dynamic programming/optimal control in AMPL

[deepak rajagopal]

Hi,
I am new to AMPL and wondering if I it can solve Dynamic programming/
optimal control problems. If so please let me know where I can find
instructions and some sample programs
Thanks
Deepak

[Robert Fourer]

For a problem to be handled in AMPL, it must be formulated as the
minimization or maximization of a function of decision variables, subject to
equalities or inequalities between other functions of the variables. The
functions used in the formulation must be built from common algebraic
operators and elementary functions like logs or sines.

AMPL is not specifically designed for optimal control problems. It may be
able to handle them if they can be reformulated in the above way, but I do
not have any examples at hand. AMPL is not designed for dynamic
programming.

Bob Fourer
4...@ampl.com

[Paul]

Adding to Bob's response, if you google "generalized linear program"
and "optimal control" together (quoting the phrases may help), you'll
find a link to a paper by George Dantzig. He used the phrase
"generalized linear program" to describe a model built from an optimal
control problem that meets certain specific conditions (such as there
being a finite basis in some function space for the class of
admissible control functions, the objective being a linear functional,
the state equations being linear, ...). Under those conditions, the
solution can be written as a linear combination of basis functions
and, after computing definite integrals of anything that can't outrun
you, you can turn the problem into a linear program where the
variables are the weights assigned to the basis functions. If your
model fits that paradigm (and you have software to do the
integrations, or can do them manually -- AMPL is not designed to
integrate things), you can use AMPL to build the GLP and pass it to a
solver.

/Paul

[paule...@gmail.com]

I'm not sure about dynamic programming, but optimal control type
problems of a finite horizon can be solved with AMPL if you discretize
the states and the inputs (it's called simultaneous dynamic
optimization/direct transcription/control vector parameterization of
both states and inputs). Many groups have been doing this for years,
and in practice, it works very well (with some caveats). As I
understand it, the NLP solver IPOPT was originally developed to solve
these types of problems. They are called "dynamic optimization"
problems -- and they do not involve Pontryagin's Max. principle or
solving Hamilton-Jacobi-Bellman equations.

See here for an AMPL example:
http://www.mcs.anl.gov/~vzavala/dynopt.html

The basic idea is to convert the differential equations into algebraic
equations using some sort of quadrature method. The simplest is of
course, to simply apply forward Euler.

Consider this ODE:

x' = -ax + u, x(0) = 0.

where a=0.2 is a parameter; x = state variable, between 0 and 9; u =
input variable, between 0 and 5. You can write this in AMPL as follows
(using textbook forward Euler):

param N := 10; # no. of integration steps
param dt := 0.01; # integration step size
param a := 0.2;
set kset ordered := 0..N;
var x{kset}, >= 0, <= 9;
var u{kset}, >= 0, <= 5;
minimize obj: 0;
subject to
c1{k in 1..N}: (x[k] - x[k-1])/dt = -a*x[k-1] + u[k-1];
option solver ipopt;
solve;
display x, u;

This is just a made-up example, but you get the idea. If you need a
more accurate or more stable integration scheme than Euler, you can
use Implicit Runge-Kutta (which can handle stiffness, and has good
stability properties). The idea is the same -- convert your
differential equations into a bunch of algebraic ones. You'll get a
sparse structured system that you can solve very efficiently using
large-scale sparse NLP solvers. Check out the research here:
http://numero.cheme.cmu.edu/Papers/
They've done a lot of work in this area. You may want to start there.

Paul

[pablo...@gmail.com]

Hi Paul,

I was wondering if you could post the link again, it is dead. Thanks for the advise!

Pablo