University of Hertfordshire Research Archive

        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UHRABy Issue DateAuthorsTitlesThis CollectionBy Issue DateAuthorsTitles

        Arkivum Files

        My Downloads
        View Item 
        • UHRA Home
        • University of Hertfordshire
        • Research publications
        • View Item
        • UHRA Home
        • University of Hertfordshire
        • Research publications
        • View Item

        Cheap Newton steps for optimal control problems: automatic differentiation and Pantoja's algorithm

        View/Open
        903843.pdf (PDF, 163Kb)
        Author
        Christianson, B.
        Attention
        2299/4342
        Abstract
        In this paper we discuss Pantoja's construction of the Newton direction for discrete time optimal control problems. We show that automatic differentiation (AD) techniques can be used to calculate the Newton direction accurately, without requiring extensive re-writing of user code, and at a surprisingly low computational cost: for an N-step problem with p control variables and q state variables at each step, the worst case cost is 6(p + q + 1) times the computational cost of a single target function evaluation, independent of N, together with at most p3/3 + p2(q + 1) + 2p(q + 1)2 + (q + l)3, i.e. less than (p + q + l)3, floating point multiply-and-add operations per time step. These costs may be considerably reduced if there is significant structural sparsity in the problem dynamics. The systematic use of checkpointing roughly doubles the operation counts, but reduces the total space cost to the order of 4pN floating point stores. A naive approach to finding the Newton step would require the solution of an Np Np system of equations together with a number of function evaluations proportional to Np, so this approach to Pantoja's construction is extremely attractive, especially if q is very small relative to N. Straightforward modifications of the AD algorithms proposed here can be used to implement other discrete time optimal control solution techniques, such as differential dynamic programming (DDP), which use state-control feedback. The same techniques also can be used to determine with certainty, at the cost of a single Newton direction calculation, whether or not the Hessian of the target function is sufficiently positive definite at a point of interest. This allows computationally cheap post-hoc verification that a second-order minimum has been reached to a given accuracy, regardless of what method has been used to obtain it.
        Publication date
        1999
        Published in
        Optimization Methods and Software
        Published version
        https://doi.org/10.1080/10556789908805736
        Other links
        http://hdl.handle.net/2299/4342
        Metadata
        Show full item record
        Keep in touch

        © 2019 University of Hertfordshire

        I want to...

        • Apply for a course
        • Download a Prospectus
        • Find a job at the University
        • Make a complaint
        • Contact the Press Office

        Go to...

        • Accommodation booking
        • Your student record
        • Bayfordbury
        • KASPAR
        • UH Arts

        The small print

        • Terms of use
        • Privacy and cookies
        • Criminal Finances Act 2017
        • Modern Slavery Act 2015
        • Sitemap

        Find/Contact us

        • T: +44 (0)1707 284000
        • E: ask@herts.ac.uk
        • Where to find us
        • Parking
        • hr
        • qaa
        • stonewall
        • AMBA
        • ECU Race Charter
        • disability confident
        • AthenaSwan