Warmstarting Techniques for Stochastic Programming Problems solved by Interior Point Methods

数据的不确定性是最优化问题中的一种常见现象，具有应用背景.不确定性的常见情况是使用预测价格或需求。可以说，几乎所有的实际优化问题都显示出数据的不确定性，即使这在所选择的解决方法中没有明确表示。我们对电信网络优化、生产计划和投资组合优化等应用特别感兴趣。在不确定性条件下进行优化的随机规划方法旨在考虑所有可能的未来结果，用它们各自的概率来衡量它们。这是通过使用事件树来近似潜在的随机过程来实现的。它的优势在于可以对风险敞口进行建模，从而带来更强大的模型解决方案。内点法（IPM）是随机规划问题的一种强有力的求解方法，它不仅适用于一般形式，而且使非线性问题变得容易处理。加快随机规划问题求解速度的一个吸引人的想法是利用问题的结构来构造和求解一个近似（这是更快的解决），并使用它来指导整个问题的求解过程。不幸的是，IPM是众所周知的，他们很难利用这种先进的起点信息。尽管在热启动IPM的理论和实践方面取得了进展，但还需要进一步的工作;我们相信，主要的改进只能通过利用随机规划等应用中的问题结构来实现。本项目的目的是通过一个崩溃启动方案来加速IPM对随机规划的解决，该方案使用原始问题的简化来构造一个近似的最优的解决方案的完整问题，并使用这一暖启动的边界点方法。开发的方法也将被应用到动态adaptthe事件树在解决方案的过程中。第一个粗近似的解可以用来确定事件树需要细化的区域，而这个细化的模型可以使用以前开发的技术从粗解快速求解。我们的重点将是发展一个实用的算法，用于快速求解随机规划以及理论分析，从而导致对所得到的warmstarted算法的复杂性的限制。随着微处理器制造商被迫转向多核架构而不是提高处理器速度，解决方案算法中的并行性开发将变得越来越重要。因此，有效的并行算法将是我们的研究重点，预计这项研究将导致更快的解决方法，为大型随机规划问题，同时保持灵活的建模所提供的使用内点方法来解决问题。进一步的结果，这项研究将是一个更好地了解内点方法的热启动属性。这一领域与许多相关的研究领域有着直接的联系，如整数规划、非线性规划和多目标优化，而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.