Warmstarting Techniques for Stochastic Programming Problems solved by Interior Point Methods

数据的不确定性是应用程序背景下优化问题中常见的现象。不确定性的常见情况是使用预测的价格或需求。可以说，几乎所有实际的优化问题都显示出数据的不确定性，即使这在选择的解决方法中没有明确说明。我们对电信网络优化、生产计划和投资组合优化等应用特别感兴趣。不确定性下的随机规划优化方法旨在考虑所有可能的未来结果，用它们各自的概率对它们进行权衡。这是通过使用事件树来近似潜在的随机过程来实现的。它的优势在于有可能模拟风险暴露，从而导致更健壮的模型解决方案。它的缺点之一是随机规划导致的问题具有非常大的维度，使其解决具有挑战性。内点法（IPM）是求解随机规划问题的一种强大的方法，它适用于一般公式，并使非线性问题易于处理。加快随机规划问题求解速度的一个吸引人的想法是利用问题的结构来构造和求解一个近似（求解速度更快），并用它来指导整个问题的求解过程。不幸的是，ipms在利用这些高级起点信息方面的困难是众所周知的。尽管暖启动IPMs的理论和实践取得了进展，但还需要进一步的工作；我们相信，只有利用随机规划等应用中的问题结构才能实现重大改进。本项目的目的是通过一种崩溃启动方案来加速ipm对随机方案的解决，该方案使用原始问题的简化来构造完整问题的近最优解，并使用该方案来启动内点方法。所开发的方法还将应用于在求解过程中动态地调整事件树。第一个粗略近似的解可用于识别需要对事件树进行细化的区域，并且可以使用前面开发的技术从粗略解中快速求解这个细化模型。我们的重点将是开发一种实用的算法来快速解决随机程序，以及理论分析，从而得出所得到的热启动算法的复杂性界限，改进已知的，更一般的结果。随着微处理器制造商被迫转向多核架构而不是提高处理器速度，在求解算法中利用并行性将变得越来越重要。因此，所开发算法的高效并行化将是我们研究的重点。预计本研究将为大型随机规划问题提供更快的解决方法，同时保持使用内点方法解决问题所提供的建模灵活性。本研究的进一步结果将是更好地理解内点法的热启动特性。该领域与许多相关研究领域直接相关，如集成规划、非线性规划和多准则优化，在这些领域，由于IPM的热启动困难，它们尚未产生如此大的影响。最终，对于大型非线性随机规划问题更好的解决方法的可用性将导致该方法在应用中得到更广泛的采用，从而导致更健壮的解决方案被实现。

Uncertainty in the data is a commonly observed phenomenon inoptimization problems with an application background. Commonlyoccurrences of uncertainty is the use of forecasted prices ordemands. It can be argued that nearly all practical optimizationproblems display uncertainty in the data, even if this is not madeexplicit in the chosen solution method. Applications such as networkoptimization in telecommunications, production planning and portfoliooptimization are of special interest to us.The stochastic programming approach to optimization under uncertaintyaims to take all possible future outcomes into account, weighing themwith their respective probabilities. This is achieved by use of anevent tree to approximate the underlying stochastic process. Itsstrength lies in the possibility to model risk-exposure, leading tomore robust model solutions. One of its weaknesses is the fact thatstochastic programming leads to problems with very large dimensions,making their solution challenging.Interior point methods (IPM) have emerged as a powerful solutionapproach for stochastic programming problems, being applicable togeneral formulations and making nonlinear problems tractable. Anappealing idea to speed up the solution of stochastic programmingproblems is to exploit the structure of the problem to construct andsolve an approximation (which is faster to solve) and use this toguide the solution process of the full problem. Unfortunately IPMsare well known for their difficulty in exploiting such advancedstarting point information. Despite progress in the theory andpractice of warmstarting IPMs further work is needed; it is our beliefthat major improvements can only be achieved by exploiting the problemstructure in applications like stochastic programming.The aim of this project is to speed up the solution of stochasticprograms by IPMs through a crash-starting scheme that uses asimplification of the original problem to construct a near-optimalsolution of the full problem and uses this to warmstart the interiorpoint method.The developed methodology will also be applied to dynamically adaptthe event tree during the solution process. The solution of a first coarseapproximation can be used to identify regions in which the event treeneeds to be refined and this refined model can be solved quickly fromthe coarse solution using the techniques developed earlier.Our emphasis will be on the development of a practical algorithm forthe fast solution of stochastic programms as well as theoreticalanalysis leading to a bound on the complexity of the resultingwarmstarted algorithm, improving on the known, more general results.The exploitation of parallelism in solution algorithms will becomeincreasingly more important as microprocessor manufacturers are forcedto move to multi-core architectures rather than increasing processorspeed. Therefore the efficient parallelisation of the developedalgorithms will be a focus point of our research.It is anticipated that this research will lead to faster solutionmethods for large stochastic programming problems while keeping theflexibility in modelling offered by using an interior point approachto solve the problem.A further consequence of this research will be a better understandingof the warmstarting properties of interior point methods. This area isof direct interest in many related research areas such as integerprogramming, nonlinear programming, and multicriteria optimization,where IPM have not yet had as large an impact due to theirwarmstarting difficulties.Ultimately the availability of better solution methods for largenonlinear stochastic programming problems will lead to wider adoptionof this methodology in applications, in turn leading to more robustsolutions being implemented.