Loading...
Please wait, while we are loading the content...
Similar Documents
A multi-step interior point warm-start approach for large-scale stochastic linear programming ∗
| Content Provider | Semantic Scholar |
|---|---|
| Author | Grothey, Andreas Colombo, Marco |
| Copyright Year | 2009 |
| 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 block-angular 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 warm-start the solver on the full problem. In this paper we present a multi-step warm-start scheme for stochastic programming problems, where a sequence of problems defined over scenario trees of differing sizes is given and an IPM warm-start 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 two-step scheme, and give numerical results. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.optimization-online.org/DB_FILE/2009/10/2438.pdf |
| Alternate Webpage(s) | http://www.maths.ed.ac.uk/ERGO/pubs/ERGO-09-007.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
