Application of statistical criteria to optimality testing in stochastic programming

Abstract

In this paper the stochastic adaptive method has been developed to solve stochastic linear problems by a finite sequence of Monte‐Carlo sampling estimators. The method is grounded on adaptive regulation of the size of Monte‐Carlo samples and the statistical termination procedure, taking into consideration the statistical modeling error. Our approach distinguishes itself by treatment of the accuracy of the solution in a statistical manner, testing the hypothesis of optimality according to statistical criteria, and estimating confidence intervals of the objective and constraint functions. The adjustment of sample size, when it is taken inversely proportional to the square of the norm of the Monte‐Carlo estimate of the gradient, guarantees the convergence a. s. at a linear rate. We examine four estimators for stochastic gradient: by the differentiation of the integral with respect to x, the finite difference approach, the Simulated Perturbation Stochastic Approximation approach, the Likelihood Ratio approach. The numerical study and examples in practice corroborate the theoretical conclusions and show that the procedures developed make it possible to solve stochastic problems with a sufficient agreeable accuracy by means of the acceptable amount of computations.

Stochastinio programavimo statistinių kriterijų taikymas optimalumui testuoti

Santrauka. Išnagrinėtas stochastinis taikomasis metodas stochastiniams tiesiniams uždaviniams spręsti naudojant baigtines Monte Karlo imtis. Šis metodas remiasi Monte Karlo imties reguliavimo taisykle ir statistine stabdymo procedūra, naudojančia statistinę modeliavimo paklaidą. Metodas skiriasi nuo kitų sprendinio tikslumo statistiniu tyrimu, optimalumo hipotezės tikrinimu, remiantis statistiniais kriterijais, ir tikslo funkcijos bei ribojimų funkcijų pasikliautinųjų intervalų įvertinimu. Imties ilgis nustatomas atvirkščiai proporcingai gradiento Monte Karlo įverčio normos kvadratui, ir tai garantuoja konvergavimą tiesiniu greičiu. Nagrinėjami keturi stochastinio gradiento įverčiai: analitiškai diferencijuojant integralą x atžvilgiu, skirtuminiu, modeliuojamojo pokyčio ir tikėtinumo santykio metodais. Skaitinis tyrimas ir pavyzdžiai praktiškai patvirtina teorines prielaidas ir parodo, kad sukurtos procedūros leidžia spręsti stochastinius uždavinius gana tiksliai naudojant priimtiną skaičiavimų apimtį.

Reikšminiai žodžiai: tiesinis programavimas, stochastinis programavimas, optimizavimas, statistiniai kriterijai, Monte Karlo metodas.

First Published Online: 21 Oct 2010

Keyword : linear programming, stochastic programming, optimality, statistical criteria, Monte-Carlo method