Warmstarting Techniques for Stochastic Programming Problems solved by Interior Point Methods
内点法求解随机规划问题的热启动技术
基本信息
- 批准号:EP/E036910/1
- 负责人:
- 金额:$ 22.17万
- 依托单位:
- 依托单位国家:英国
- 项目类别:Research Grant
- 财政年份:2007
- 资助国家:英国
- 起止时间:2007 至 无数据
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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.
数据的不确定性是最优化问题中的一种常见现象,具有应用背景.不确定性的常见情况是使用预测价格或需求。可以说,几乎所有的实际优化问题都显示出数据的不确定性,即使这在所选择的解决方法中没有明确表示。我们对电信网络优化、生产计划和投资组合优化等应用特别感兴趣。在不确定性条件下进行优化的随机规划方法旨在考虑所有可能的未来结果,用它们各自的概率来衡量它们。这是通过使用事件树来近似潜在的随机过程来实现的。它的优势在于可以对风险敞口进行建模,从而带来更强大的模型解决方案。内点法(IPM)是随机规划问题的一种强有力的求解方法,它不仅适用于一般形式,而且使非线性问题变得容易处理。加快随机规划问题求解速度的一个吸引人的想法是利用问题的结构来构造和求解一个近似(这是更快的解决),并使用它来指导整个问题的求解过程。不幸的是,IPM是众所周知的,他们很难利用这种先进的起点信息。尽管在热启动IPM的理论和实践方面取得了进展,但还需要进一步的工作;我们相信,主要的改进只能通过利用随机规划等应用中的问题结构来实现。本项目的目的是通过一个崩溃启动方案来加速IPM对随机规划的解决,该方案使用原始问题的简化来构造一个近似的最优的解决方案的完整问题,并使用这一暖启动的边界点方法。开发的方法也将被应用到动态adaptthe事件树在解决方案的过程中。第一个粗近似的解可以用来确定事件树需要细化的区域,而这个细化的模型可以使用以前开发的技术从粗解快速求解。我们的重点将是发展一个实用的算法,用于快速求解随机规划以及理论分析,从而导致对所得到的warmstarted算法的复杂性的限制。随着微处理器制造商被迫转向多核架构而不是提高处理器速度,解决方案算法中的并行性开发将变得越来越重要。因此,有效的并行算法将是我们的研究重点,预计这项研究将导致更快的解决方法,为大型随机规划问题,同时保持灵活的建模所提供的使用内点方法来解决问题。进一步的结果,这项研究将是一个更好地了解内点方法的热启动属性。这一领域与许多相关的研究领域有着直接的联系,如整数规划、非线性规划和多目标优化,而IPM由于其热启动困难而尚未产生如此大的影响。最终,大型非线性随机规划问题更好的解决方法的出现将导致该方法在应用中得到更广泛的采用,从而导致更鲁棒的解决方案得到实施。
项目成果
期刊论文数量(2)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Andreas Grothey其他文献
A decomposition-based crash-start for stochastic programming
- DOI:
10.1007/s10589-012-9530-7 - 发表时间:
2013-01-24 - 期刊:
- 影响因子:2.000
- 作者:
Marco Colombo;Andreas Grothey - 通讯作者:
Andreas Grothey
Approximate dynamic programming with Bézier Curves/Surfaces for Top-percentile Traffic Routing
- DOI:
10.1016/j.ejor.2011.11.041 - 发表时间:
2012-05-01 - 期刊:
- 影响因子:
- 作者:
Andreas Grothey;Xinan Yang - 通讯作者:
Xinan Yang
Solving security constrained optimal power flow problems by a structure exploiting interior point method
- DOI:
10.1007/s11081-014-9250-1 - 发表时间:
2014-02-12 - 期刊:
- 影响因子:1.700
- 作者:
Naiyuan Chiang;Andreas Grothey - 通讯作者:
Andreas Grothey
Andreas Grothey的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
相似国自然基金
EstimatingLarge Demand Systems with MachineLearning Techniques
- 批准号:
- 批准年份:2024
- 资助金额:万元
- 项目类别:外国学者研究基金
相似海外基金
CAREER: Using Stochastic Techniques to Understand and Predict the Flow of Non-spherical Particles
职业:使用随机技术来理解和预测非球形颗粒的流动
- 批准号:
2145871 - 财政年份:2022
- 资助金额:
$ 22.17万 - 项目类别:
Continuing Grant
CRII: CIF: Unifying Scheduling and Optimization Techniques to Speed-up Distributed Stochastic Gradient Descent
CRII:CIF:统一调度和优化技术来加速分布式随机梯度下降
- 批准号:
1850029 - 财政年份:2019
- 资助金额:
$ 22.17万 - 项目类别:
Standard Grant
Novel techniques for stochastic modelling of time-dependent multivariate relationships with application to primary visual cortex
时间依赖性多元关系随机建模的新技术及其应用于初级视觉皮层
- 批准号:
EP/S005692/1 - 财政年份:2019
- 资助金额:
$ 22.17万 - 项目类别:
Research Grant
Modelling and Analysis of Reliability and Availability by stochastic modelling techniques considering continuously the statistical quality of the initial data
通过随机建模技术对可靠性和可用性进行建模和分析,持续考虑初始数据的统计质量
- 批准号:
405325157 - 财政年份:2018
- 资助金额:
$ 22.17万 - 项目类别:
Research Grants
Theory and Techniques for Controlling the Collective Behavior of Dynamical Systems under Stochastic Uncertainty
随机不确定性下动力系统集体行为的控制理论与技术
- 批准号:
1665031 - 财政年份:2016
- 资助金额:
$ 22.17万 - 项目类别:
Standard Grant
Computational techniques on the stochastic excitation of rolling tires from the rough road surface contact
粗糙路面接触滚动轮胎随机激励计算技术
- 批准号:
317553749 - 财政年份:2016
- 资助金额:
$ 22.17万 - 项目类别:
Research Grants
Theory and Techniques for Controlling the Collective Behavior of Dynamical Systems under Stochastic Uncertainty
随机不确定性下动力系统集体行为的控制理论与技术
- 批准号:
1509387 - 财政年份:2015
- 资助金额:
$ 22.17万 - 项目类别:
Standard Grant
Uncertainty quantification techniques and stochastic models for superconducting radio frequency cavities
超导射频腔的不确定性量化技术和随机模型
- 批准号:
262959891 - 财政年份:2014
- 资助金额:
$ 22.17万 - 项目类别:
Scientific Networks
Efficient Calibration Techniques for Stochastic Traffic Simulators
随机交通模拟器的高效校准技术
- 批准号:
1334304 - 财政年份:2013
- 资助金额:
$ 22.17万 - 项目类别:
Standard Grant
SHF: Small: Stochastic Computing Techniques for Real-Time Image-Processing Applications
SHF:小型:实时图像处理应用的随机计算技术
- 批准号:
1318091 - 财政年份:2013
- 资助金额:
$ 22.17万 - 项目类别:
Standard Grant