Tractable Approximations of Chance Constrained Optimization Problems

点击翻译按钮获取中文摘要

This grant provides funding to develop algorithms for optimization problems with chance constraints. Uncertainty is an integral part of planning and decision making in a wide variety of applications. The research will study decision models that involve the possibility of a rare but costly event. A novel approach will be applied to chance constrained optimization problems, where computationally intractable chance constraints are approximated by efficiently computable convex constraints, thus ending up with an efficiently solvable approximating problems. The approach is especially attractive when the approximation is safe, in the sense that its feasible set is contained in the feasible set of the chance constrained problem, so that every feasible solution of the approximation is feasible for the original problem. Safe tractable approximations make it possible to treat chance constraints in a computationally efficient and reliable fashion; in numerous applications, especially large scale ones, these advantages significantly outweigh the intrinsic shortcoming of the approach -- its conservatism.If successful, the research will result in an in-depth investigation of safe tractable approximations of convex problems with stochastic data. It will enhance the building and processing of mathematical models of decision making, and will extend significantly the scope and the performance of computational tools supporting real-life decision making, thus improving its quality. The research will also result in improved algorithms for difficult combinatorial optimization problems. Applications of the research arise in areas such as manufacturing, transportation logistics, and financial engineering. In general, the research will contribute to the computational tools and methodologies available for stochastic optimization problems.