  


A multistep interior point warmstart approach for largescale stochastic linear programming
Marco Colombo(M.Colomboed.ac.uk) Abstract: Interior point methods (IPM) have been recognised as an efficient approach for the solution of large scale stochastic programming problems due to their ability of exploiting the blockangular structure of the augmented system particular to this problem class. Stochastic programming problems, however, have exploitable structure beyond the simple matrix shape: namely the scenarios are typically a discrete sampling of an underlying (continuous) probability distribution. An appealing way of exploiting this would be to initially use a coarser discretisation, i.e. less scenarios, to obtain an approximate solution, which could then be used to warmstart the solver on the full problem. In this paper we present a multistep warmstart scheme for stochastic programming problems, where a sequence of problems defined over scenario trees of differing sizes is given and an IPM warmstart point is constructed by successively finding approximations to the central path of the problems defined over the given trees. We analyse the resulting algorithm, argue that it yields improved complexity over either the coldstart or a naive twostep scheme, and give numerical results. Keywords: Stochastic Programming, Interiorpoint Methods, Warmstarting Category 1: Stochastic Programming Citation: Technical report ERGO 09007, School of Mathematics, University of Edinburgh, Edinburgh EH9 3JZ, UK, June 2009, revised October 2009. Download: [PDF] Entry Submitted: 10/26/2009 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  