# SQG

Published on February 4, 2008

Author: Susett

Source: authorstream.com

Stochastic Quasi-Gradient Methods:  Stochastic Quasi-Gradient Methods Roger J-B Wets University of California, Davis February 15, 2005 Stochastic optimization:  Stochastic optimization Formulation Properties: S Subgradients of convex fcns:  Subgradients of convex fcns Minimization algorithms:  Minimization algorithms Step type 1 Minimization algorithms:  Minimization algorithms Step type 2 proj “repeated” projections:  “repeated” projections Convex program: quadratic objective function quadratic program if S is a polyhedral set Many applications: projection is a simple/efficient non-negative, convex, bounded away from 0 SQG Iterates:  SQG Iterates basic strategy: SQG: Stochastic Optimization:  SQG: Stochastic Optimization . sqg: justification: SQG: Stochastic Optimization:  SQG: Stochastic Optimization . value estimate: justification: A (simple) location problem:  A (simple) location problem Pop. Size of 12 districts: 11 # 26. Probabilistic choice of shopping district: shortage cost: 4, holding cost: 0.5 (excess) decision: location of facilities (shopping malls) “preferences” table:  “preferences” table Formulation:  Formulation from objective: probability of sample determined by customer behavior Objective Value: iterates :  Objective Value: iterates Estimate of the objective per iterate Objective Value (2): iterates :  Objective Value (2): iterates Estimate of the objective per iterate Facilities: 18.57 15.90 19.13 16.35 27.25 20.75 21.88 17.81 19.11 17.52 18.62 19.60 Distr.Pop: 14 11 14 13 26 23 22 11 14 12 18 10 Objective Value (3): iterates :  Objective Value (3): iterates Facilities: 24 22 23 20 26 22 23 22 22 20 22 25 : 271 Distr.Pop: 19 16 19 16 27 21 22 18 19 18 19 20 : 234 a.s. Convergence:  a.s. Convergence For now presumed optimal sol’n at iteration  projection implies: a.s Convergence:  a.s Convergence taking condition expectation w.r.t. F assumption(a.): with a.s Convergence:  a.s Convergence Hence Assumption(b.): where with a.s. Convergence:  a.s. Convergence recursively from (a) a.s. Convergence:  a.s. Convergence Thus assumption (c.) and there exists a subsequence such that Review of assumptions:  Review of assumptions (a.) (b.) (c.) “stumbling” blocks:  “stumbling” blocks Projection Step size: adaptive, adjust (increase, decrease) based on the variance of the stochastic quasi-gradient Stopping criterion: like for step-size, but more generally comparison of the values of the objective: A short history:  A short history Stochastic approximation methods Robbins & Monro, Kiefer & Wolfowitz (‘50) SQG: Theory Shor, Poljak, Ermoliev, Fabian (‘60), Kushner(‘70),Pflug, Ruszczynski (‘80), Implementation: Gaivoronski, Gupal, Norkin (‘80 … 2005)

31. 01. 2008
0 views

09. 01. 2008
0 views

09. 01. 2008
0 views

10. 01. 2008
0 views

10. 01. 2008
0 views

10. 01. 2008
0 views

13. 01. 2008
0 views

16. 01. 2008
0 views

14. 01. 2008
0 views

20. 01. 2008
0 views

22. 01. 2008
0 views

22. 01. 2008
0 views

04. 02. 2008
0 views

04. 02. 2008
0 views

17. 01. 2008
0 views

11. 02. 2008
0 views

07. 02. 2008
0 views

15. 01. 2008
0 views

18. 02. 2008
0 views

20. 02. 2008
0 views

11. 01. 2008
0 views

28. 02. 2008
0 views

05. 03. 2008
0 views

12. 01. 2008
0 views

11. 01. 2008
0 views

21. 01. 2008
0 views

19. 03. 2008
0 views

21. 03. 2008
0 views

22. 01. 2008
0 views

12. 02. 2008
0 views

03. 04. 2008
0 views

28. 03. 2008
0 views

08. 04. 2008
0 views

16. 04. 2008
0 views

07. 02. 2008
0 views

11. 03. 2008
0 views

23. 04. 2008
0 views

24. 04. 2008
0 views

07. 05. 2008
0 views

02. 05. 2008
0 views

25. 02. 2008
0 views

13. 01. 2008
0 views

04. 02. 2008
0 views

06. 02. 2008
0 views

23. 01. 2008
0 views

13. 02. 2008
0 views

24. 01. 2008
0 views

21. 01. 2008
0 views

24. 01. 2008
0 views

07. 03. 2008
0 views

16. 01. 2008
0 views

22. 01. 2008
0 views