edoc-Server der Humboldt-Universität zu Berlin

SPEPS Preprint

Author(s): Tito Homem-de-Mello, Northwestern University
Title: On Rates of Convergence for Stochastic Optimization Problems Under Non-I.I.D. Sampling
Date of Acceptance: 18.12.2006
Submission Date: 12.09.2006
Series Title: Stochastic Programming E-Print Series
(SPEPS)
Editors: Julie L. Higle; Werner Römisch; Surrajeet Sen
Complete Preprint: pdf (urn:nbn:de:kobv:11-10072999)
Metadata export: To export the complete metadata set as Endote or Bibtex format please click to the appropriate link. Endnote   Bibtex  
print on demand: If you click on this icon you can order a print copy of this publication. Bestellung als gedruckte und gebundene Version bei epubli.de, Ausführung der Bestellung erst nach Bestätigung auf den epubli.de-Seiten

Abstract (eng):
In this paper we discuss the issue of solving stochastic optimization problems by means of sample average approximations. Our focus is on rates of convergence of estimators of optimal solutions and optimal values with respect to the sample size. This is a well studied problem in case the samples are independent and identically distributed (i.e., when standard Monte Carlo is used); here, we study the case where that assumption is dropped. Broadly speaking, our results show that, under appropriate assumptions, the rates of convergence for pointwise estimators under a sampling scheme carry over to the optimization case, in the sense that convergence of approximating optimal solutions and optimal values to their true counterparts has the same rates as in pointwise estimation. Our motivation for the study arises from two types of sampling methods that have been widely used in the Statistics literature. One is Latin Hypercube Sampling (LHS), a stratified sampling method originally proposed in the seventies by McKay, Beckman, and Conover (1979). The other is the class of quasi-Monte Carlo (QMC) methods, which have become popular especially after the work of Niederreiter (1992). The advantage of such methods is that they typically yield pointwise estimators which not only have lower variance than standard Monte Carlo but also possess better rates of convergence. Thus, it is important to study the use of these techniques in sampling-based optimization. The novelty of our work arises from the fact that, while there has been some work on the use of variance reduction techniques and QMC methods in stochastic optimization, none of the existing work — to the best of our knowledge — has provided a theoretical study on the effect of these techniques on rates of convergence for the optimization problem. We present numerical results for some two-stage stochastic programs from the literature to illustrate the discussed ideas.
Access Statistics: These data concerning access statistics for individual documents have been compiled using the webserver log files aggregated by AWSTATS. They refer to a monthly access count to the full text documents as well as to the entry page.
 
As for format versions of a document which consist of multiple files (such as HTML) the highest monthly access number to one of the files (chapters) is shown respectivly.
 
To see the detailled access numbers please move the mouse pointer over the single bars of the digaram.
Startseite: 2 Zugriffe PDF: 6 Zugriffe Startseite: 2 Zugriffe PDF: 2 Zugriffe Startseite: 1 Zugriffe PDF: 4 Zugriffe Startseite: 3 Zugriffe PDF: 6 Zugriffe Startseite: 1 Zugriffe PDF: 7 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe Startseite: 3 Zugriffe PDF: 5 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe Startseite: 1 Zugriffe PDF: 13 Zugriffe PDF: 4 Zugriffe Startseite: 2 Zugriffe PDF: 8 Zugriffe Startseite: 1 Zugriffe PDF: 6 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 4 Zugriffe PDF: 12 Zugriffe Startseite: 1 Zugriffe PDF: 10 Zugriffe PDF: 23 Zugriffe PDF: 3 Zugriffe Startseite: 1 Zugriffe PDF: 12 Zugriffe PDF: 10 Zugriffe Startseite: 1 Zugriffe PDF: 21 Zugriffe Startseite: 1 Zugriffe PDF: 20 Zugriffe PDF: 18 Zugriffe PDF: 19 Zugriffe PDF: 14 Zugriffe PDF: 10 Zugriffe PDF: 8 Zugriffe Startseite: 2 Zugriffe PDF: 11 Zugriffe Startseite: 2 Zugriffe PDF: 7 Zugriffe PDF: 13 Zugriffe PDF: 11 Zugriffe Startseite: 2 Zugriffe PDF: 81 Zugriffe Startseite: 6 Zugriffe PDF: 424 Zugriffe Startseite: 4 Zugriffe PDF: 227 Zugriffe Startseite: 5 Zugriffe PDF: 14 Zugriffe Startseite: 2 Zugriffe PDF: 13 Zugriffe PDF: 13 Zugriffe Startseite: 2 Zugriffe PDF: 20 Zugriffe Startseite: 6 Zugriffe PDF: 17 Zugriffe Startseite: 6 Zugriffe PDF: 37 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Jan
12
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Jan
12
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Startseite 2 2 1 3 1 2 3 2 1   2 1 2 4 1     1   1 1           2 2     2 6 4 5 2   2 6 6
PDF 6 2 4 6 7 6 5 6 13 4 8 6 10 12 10 23 3 12 10 21 20 18 19 14 10 8 11 7 13 11 81 424 227 14 13 13 20 17 37

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 67 (1.72 pro Monat)
  • PDF – 1151 (29.51 pro Monat)
 
 
Generated at 27.11.2014, 02:31:44