  Efficient Riccati equation based techniques for the approximate solution of
discrete time linear regulator problems are restricted in their application to
problems with quadratic terminal payoffs. Where non-quadratic terminal payoffs
are required, these techniques fail due to the attendant non-quadratic value
functions involved. In order to compute these non-quadratic value functions, it
is often necessary to appeal directly to dynamic programming in the form of
grid- or element-based iterations for the value function. These iterations
suffer from poor scalability with respect to problem dimension and time
horizon. In this paper, a new max-plus based method is developed for the
approximate solution of discrete time linear regulator problems with
non-quadratic payoffs. This new method is underpinned by the development of new
fundamental solutions to such linear regulator problems, via max-plus duality.
In comparison with a typical grid-based approach, a substantial reduction in
computational effort is observed in applying this new max-plus method. A number
of simple examples are presented that illustrate this and other observations.
