Optimization Online


Fully Polynomial Time $(\Sigma,\Pi)$-Approximation Schemes for Continuous Stochastic Convex Dynamic Programs

Nir Halman(halman***at***huji.ac.il)
Giacomo Nannicini(giacomo.n***at***gmail.com)

Abstract: We develop fully polynomial time $(\Sigma,\Pi)$-approximation schemes for stochastic dynamic programs with continuous state and action spaces, when the single-period cost functions are convex Lipschitz-continuous functions that are accessed via value oracle calls. That is, for every given additive error parameter $\Sigma>0$ and multiplicative error factor $\Pi=1+\epsilon>1$, the scheme returns a feasible solution whose value is no more that $\Sigma + \Pi v^*$, where $v^* \ge 0$ is the optimal value, and it runs in time polynomial in the input size and in $\log (\frac{1}{\Sigma})+ \frac{1}{\eps}$. We show that this result is best possible in the sense that in general it is not possible to compute in polynomial time $(\Sigma,\Pi)$-approximations for stochastic dynamic programs with continuous state and action spaces, whenever either $\Sigma=0$ or $\Pi=1$. Our results are achieved by extending to the continuous setting the technique of $K$-approximation sets and functions introduced by Halman et al. [{\em Math. Oper. Res.}, 34, (2009), pp. 674--685]. This extension requires a completely new set of analytical and algorithmic tools that may be useful in their own right for further development of approximation algorithms. A preliminary computational evaluation shows that the proposed approximation scheme is orders of magnitude faster than solving the discretized problem exactly, and finds solutions of better quality than approximate solution approaches taken from the literature for comparable computational effort.

Keywords: Approximation algorithms, stochastic dynamic programming, $K$-approximation sets and functions, $(\Sigma,\Pi)$-approximation sets and functions.

Category 1: Other Topics (Dynamic Programming )

Category 2: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 07/07/2015
Entry Accepted: 07/07/2015
Entry Last Modified: 07/07/2015

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