logging in or signing up SQG Susett Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 75 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: February 04, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Stochastic Quasi-Gradient Methods: Stochastic Quasi-Gradient Methods Roger J-B Wets University of California, Davis February 15, 2005Stochastic optimization: Stochastic optimization Formulation Properties: SSubgradients of convex fcns: Subgradients of convex fcnsMinimization algorithms: Minimization algorithms Step type 1Minimization 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 0SQG 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” tableFormulation: 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 10Objective 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 : 234a.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) You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
SQG Susett Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 75 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: February 04, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Stochastic Quasi-Gradient Methods: Stochastic Quasi-Gradient Methods Roger J-B Wets University of California, Davis February 15, 2005Stochastic optimization: Stochastic optimization Formulation Properties: SSubgradients of convex fcns: Subgradients of convex fcnsMinimization algorithms: Minimization algorithms Step type 1Minimization 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 0SQG 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” tableFormulation: 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 10Objective 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 : 234a.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)