Optimization Online


Inexact cuts for Deterministic and Stochastic Dual Dynamic Programming applied to convex nonlinear optimization problems

Vincent Guigues (vincent.guigues***at***gmail.com)

Abstract: We introduce an extension of Dual Dynamic Programming (DDP) to solve convex nonlinear dynamic programming equations. We call Inexact DDP (IDDP) this extension which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error. We show that any accumulation point of the sequence of decisions is an approximate solution to the dynamic programming equations. When these errors tend to zero as the number of iterations goes to infinity, we show that IDDP solves the dynamic programming equations. We extend the analysis to stochastic convex nonlinear dynamic programming equations, introducing Inexact Stochastic Dual Dynamic Programming (ISDDP), an inexact variant of SDDP corresponding to the situation where some or all problems to be solved in the forward and backward passes of SDDP are solved approximately. We also show the almost sure convergence of ISDDP for vanishing errors.

Keywords: Stochastic programming; Inexact cuts for value functions; Bounding epsilon-optimal dual solutions; SDDP; Inexact SDDP

Category 1: Stochastic Programming

Category 2: Other Topics (Dynamic Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 07/03/2017
Entry Accepted: 07/04/2017
Entry Last Modified: 11/21/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society