کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10523886 957133 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on sample complexity of multistage stochastic programs
ترجمه فارسی عنوان
یک یادداشت در مورد پیچیدگی نمونه از برنامه های تصادفی چند مرحله ای
کلمات کلیدی
برنامه ریزی تصادفی، نمونه برداری مونت کارلو، روش متوسط ​​نمونه پیچیدگی،
ترجمه چکیده
ما یک مرز پایین برای پیچیدگی نمونه میانگین تقریبی نمونه برای یک کلاس خاص از چندین مشکل بهینه سازی تصادفی را دریافت می کنیم. در آثار قبلی، مرزهای بالایی برای چنین مسائلی مشتق شده است. ما نشان می دهیم که وابستگی مرز پایین به نسبت پارامترهای پیچیدگی و داده های مربوط به مسئله قابل مقایسه با برآوردهای بالاتری است. همانند نتایج قبلی، مرزی پایین ما فاکتور چند ضلعی را نشان می دهد که برای برخی مشکلات احتمالی خاص اجتناب ناپذیر است.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We derive a lower bound for the sample complexity of the Sample Average Approximation method for a certain class of multistage stochastic optimization problems. In previous works, upper bounds for such problems were derived. We show that the dependence of the lower bound with respect to the complexity parameters and the problem's data are comparable to the upper bound's estimates. Like previous results, our lower bound presents an additional multiplicative factor showing that it is unavoidable for certain stochastic problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 44, Issue 4, July 2016, Pages 430-435
نویسندگان
,