From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs in which the performance of the approximation is quantied explicitly. To this end, we adopt the recent developments in two areas of randomized optimization and first order methods, leading to a priori as well as a posteriori performance guarantees. We illustrate the generality and implications of our theoretical results in the special case of the long-run average cost and discounted cost optimal control problems for Markov decision processes on Borel spaces. The applicability of the theoretical results is demonstrated through a constrained linear quadratic optimal control problem and a fisheries management problem.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Daniel Kuhn, John Lygeros, Peyman Mohajerin Esfahani, Tobias Sutter
2018
Article

Résumé

Official source

https://infoscience.epfl.ch/record/227408?ln=fr

À propos de ce résultat

Concepts associés (12)

Concepts associés

Chargement

Publications associées (45)

Chargement

Afficher plus

Publications associées

Chargement

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur

Processus de décision markovien

En théorie de la décision et de la théorie des probabilités, un processus de décision markovien (en anglais Markov decision process, MDP) est un modèle stochastique où un agent prend des décisions et

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble

Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations

Daniel Kuhn, Peyman Mohajerin Esfahani

We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of the worst-case distribution within this Wasserstein ball. The state-of-the-art methods for solving the resulting distributionally robust optimization problems rely on global optimization techniques, which quickly become computationally excruciating. In this paper we demonstrate that, under mild assumptions, the distributionally robust optimization problems over Wasserstein balls can in fact be reformulated as finite convex programs---in many interesting cases even as tractable linear programs. Leveraging recent measure concentration results, we also show that their solutions enjoy powerful finite-sample performance guarantees. Our theoretical results are exemplified in mean-risk portfolio optimization as well as uncertainty quantification.

2018

Chargement

Decision rules for information discovery in multi-stage stochastic programming

Daniel Kuhn

Stochastic programming and robust optimization are disciplines concerned with optimal decision-making under uncertainty over time. Traditional models and solution algorithms have been tailored to problems where the order in which the uncertainties unfold is independent of the controller actions. Nevertheless, in numerous real-world decision problems, the time of information discovery can be influenced by the decision maker, and uncertainties only become observable following an (often costly) investment. Such problems can be formulated as mixed-binary multi-stage stochastic programs with decision-dependent non-anticipativity constraints. Unfortunately, these problems are severely computationally intractable. We propose an approximation scheme for multi-stage problems with decision-dependent information discovery which is based on techniques commonly used in modern robust optimization. In particular, we obtain a conservative approximation in the form of a mixed-binary linear program by restricting the spaces of measurable binary and real-valued decision rules to those that are representable as piecewise constant and linear functions of the uncertain parameters, respectively. We assess our approach on a problem of infrastructure and production planning in offshore oil fields from the literature.

IEEE2011

Chargement

Dual Approach for Two-Stage Robust Nonlinear Optimization

Jianzhe Zhen

Adjustable robust minimization problems where the objective or constraints depend in a convex way on the adjustable variables are generally difficult to solve. In this paper, we reformulate the original adjustable robust nonlinear problem with a polyhedral uncertainty set into an equivalent adjustable robust linear problem, for which all existing approaches for adjustable robust linear problems can be used. The reformulation is obtained by first dualizing over the adjustable variables and then over the uncertain parameters. The polyhedral structure of the uncertainty set then appears in the linear constraints of the dualized problem, and the nonlinear functions of the adjustable variables in the original problem appear in the uncertainty set of the dualized problem. We show how to recover linear decision rules to the original primal problem and how to generate bounds on its optimal objective value.

INFORMS2022

Chargement

Afficher plus