  


Inexact Stochastic Mirror Descent for twostage nonlinear stochastic programs
Vincent Guigues (vincent.guiguesgmail.com) Abstract: We introduce an inexact variant of Stochastic Mirror Descent (SMD), called Inexact Stochastic Mirror Descent (ISMD), to solve nonlinear twostage stochastic programs where the second stage problem has linear and nonlinear coupling constraints and a nonlinear objective function which depends on both first and second stage decisions. Given a candidate first stage solution and a realization of the second stage random vector, each iteration of ISMD combines a stochastic subgradient descent using a proxmapping with the computation of approximate (instead of exact for SMD) primal and dual second stage solutions. We propose two variants of ISMD and show the convergence of these variants to the optimal value of the stochastic program. We show in particular that under some assumptions, ISMD has the same convergence rate as SMD. The first variant of ISMD and its convergence analysis are based on the formulas for inexact cuts of value functions of convex optimization problems shown recently in [6]. The second variant of ISMD and the corresponding convergence analysis rely on new formulas that we derive for inexact cuts of value functions of convex optimization problems assuming that the dual function of the second stage problem for all fixed first stage solution and realization of the second stage random vector, is strongly concave. We show that this assumption of strong concavity is satisfied for some classes of problems and present the results of numerical experiments on two simple twostage problems which show that solving approximately the second stage problem for the first iterations of ISMD can help us obtain a good approximate first stage solution quicker than with SMD. Keywords: Inexact cuts for value functions; Inexact Stochastic Mirror Descent; Strong Concavity of the dual function; Stochastic Programming Category 1: Stochastic Programming Citation: Download: [PDF] Entry Submitted: 05/29/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  