
Monte Carlo estimators Stochastic Differentiation

tarix  05.10.2018  ölçüsü  0,63 Mb.   #72201 

Introduction Introduction Stochastic Differentiation feasible gradient approach for twostage SLP Testing optimality Convergence analysis Counterexample
We examine several estimators for stochastic gradient: We examine several estimators for stochastic gradient:  Analytical approach (AA);
 Finite difference approach (FD);
 Simulated perturbation stochastic approach (SPSA);
 Likelihood ratio approach (LR).
Gradient is expressed as where is given by the a set of solutions of the dual problem
Let us define the set of feasible directions as follows:
Denote, as projection of vector g onto the set U. Denote, as projection of vector g onto the set U. Since the objective function is differentiable, the solution
The starting point can be obtained as the solution of the deterministic linear problem: The starting point can be obtained as the solution of the deterministic linear problem: The iterative stochastic procedure of gradient search could be used further: where is the steplength multiplier and is the projection of gradient estimator to the ε feasible set.
There is no a great necessity to compute estimators with a high accuracy on starting the optimisation, because then it suffices only to approximately evaluate the direction leading to the optimum. There is no a great necessity to compute estimators with a high accuracy on starting the optimisation, because then it suffices only to approximately evaluate the direction leading to the optimum. Therefore, one can obtain not so large samples at the beginning of the optimum search and, later on, increase the size of samples so as to get the estimate of the objective function with a desired accuracy just at the time of decision making on finding the solution to the optimisation problem.
Twostage stochastic linear optimisation problem. Twostage stochastic linear optimisation problem. Dimensions of the task are as follows:  the first stage has 10 rows and 20 variables;
 the second stage has 20 rows and 30 variables.
 http://www.math.bme.hu/~deak/twostage/ l1/20x20.1/
 (20060120).
The estimate of the optimal value of the objective function given in the database is 182.94234 0.066 N0=Nmin=100 Nmax=10000. Maximal number of iterations , generation of trials was broken when the estimated confidence interval of the objective function exceeds admissible value . Initial data were as follows:
The stochastic adaptive method has been developed to solve stochastic linear problems by a finite sequence of MonteCarlo sampling estimators The stochastic adaptive method has been developed to solve stochastic linear problems by a finite sequence of MonteCarlo sampling estimators The method is grounded by adaptive regulation of the size of MonteCarlo samples and the statistical termination procedure, taking into consideration the statistical modeling accuracy The proposed adjustment of sample size, when it is taken inversely proportional to the square of the norm of the MonteCarlo estimate of the gradient, guarantees the convergence a. s. at a linear rate
Dostları ilə paylaş: 

