SQG

Information about SQG

Published on February 4, 2008

Author: Susett

Source: authorstream.com

Content

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)

Related presentations


Other presentations created by Susett

India presentation
31. 01. 2008
0 views

India presentation

deltas with changes
09. 01. 2008
0 views

deltas with changes

kosovo
09. 01. 2008
0 views

kosovo

Phthalates
10. 01. 2008
0 views

Phthalates

mathsproblems
10. 01. 2008
0 views

mathsproblems

predicateAndArgument
10. 01. 2008
0 views

predicateAndArgument

NRCCWDT DataAbuse
13. 01. 2008
0 views

NRCCWDT DataAbuse

barrie jpc06
16. 01. 2008
0 views

barrie jpc06

gama pgb 18mar03 nofigs
14. 01. 2008
0 views

gama pgb 18mar03 nofigs

Conducting a Hazard Assessment
20. 01. 2008
0 views

Conducting a Hazard Assessment

gravity07
22. 01. 2008
0 views

gravity07

Jtaylor99
22. 01. 2008
0 views

Jtaylor99

Witches part1
04. 02. 2008
0 views

Witches part1

pedmalls
04. 02. 2008
0 views

pedmalls

16janellerose
17. 01. 2008
0 views

16janellerose

plant exercise
11. 02. 2008
0 views

plant exercise

Moira Chan Yeung ENG PTT
07. 02. 2008
0 views

Moira Chan Yeung ENG PTT

303lec27
15. 01. 2008
0 views

303lec27

philanthrony
18. 02. 2008
0 views

philanthrony

PHYS1311 101706 bw
11. 01. 2008
0 views

PHYS1311 101706 bw

MRCME Sciatica
28. 02. 2008
0 views

MRCME Sciatica

Mr I Noy
05. 03. 2008
0 views

Mr I Noy

twri 06
12. 01. 2008
0 views

twri 06

Garbage
11. 01. 2008
0 views

Garbage

2005110803450707
21. 01. 2008
0 views

2005110803450707

sres blended 2006
19. 03. 2008
0 views

sres blended 2006

State Contract Airfares
21. 03. 2008
0 views

State Contract Airfares

EU eurosceptic view
22. 01. 2008
0 views

EU eurosceptic view

lozen
12. 02. 2008
0 views

lozen

Manatee
03. 04. 2008
0 views

Manatee

InfoDay2 IST
28. 03. 2008
0 views

InfoDay2 IST

20071107 TECO 3Q07 v4
08. 04. 2008
0 views

20071107 TECO 3Q07 v4

vgtu prezentacija
16. 04. 2008
0 views

vgtu prezentacija

influensa051110
07. 02. 2008
0 views

influensa051110

tara 2008 content area reading
11. 03. 2008
0 views

tara 2008 content area reading

schultz testbed overview lecture
23. 04. 2008
0 views

schultz testbed overview lecture

305
24. 04. 2008
0 views

305

C5 trade2
07. 05. 2008
0 views

C5 trade2

Chapman2
02. 05. 2008
0 views

Chapman2

200611 Wolski DampingRings
25. 02. 2008
0 views

200611 Wolski DampingRings

com611
13. 01. 2008
0 views

com611

ProphetMuhammad PBUH
04. 02. 2008
0 views

ProphetMuhammad PBUH

Chong Roots
06. 02. 2008
0 views

Chong Roots

ene29 11 02
23. 01. 2008
0 views

ene29 11 02

partnersinaredesignn etwork
13. 02. 2008
0 views

partnersinaredesignn etwork

cotton2
24. 01. 2008
0 views

cotton2

New Apps 2006A
24. 01. 2008
0 views

New Apps 2006A

2005funding
07. 03. 2008
0 views

2005funding

nbi03 rangod
16. 01. 2008
0 views

nbi03 rangod

Roadshow 6 03 AM
22. 01. 2008
0 views

Roadshow 6 03 AM