Problem conditioning in convex optimization: theory and algorithms

凸优化中的问题调节：理论与算法

• 批准号: 0306240
• 负责人: Marina Epelman
• 金额: --
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-06-15 至 2008-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0306240&HistoricalAwards=false
• 关键词: Problem; conditioning; convex; optimization; theory

Convex optimization is an important area of mathematical optimization. Recently a new and powerful theory of condition numbers for convex conic linear optimization problems has been developed. These numbers capture the intuitive notion of problem conditioning as a measure of problem sensitivity to perturbations in the input data. They are important in studying many of the behavioral characteristics of these problems. This research investigates the role that conditioning plays in problem behavior. Of particular interest is the performance of algorithms for solving the problem, and the ability to perform meaningful sensitivity analysis on the problem data. Two distinct but related avenues of this research are developing methods of preconditioning of optimization problems (i.e., finding an equivalent reformulation of the problem at hand which possesses better properties) with the eventual goal to explore and quantify various preprocessing methods in practical optimization algorithms, and extending the notion of problem conditioning to practical problems which often lie outside the conic linear form, leading to better understanding of problem behavior, ability to perform meaningful sensitivity analysis, and potential improvement in performance of algorithms. The broad goal is to improve the modeling and solution capabilities of optimization, which is a fundamental tool of operations research. The specific focus is on exploring the methods to measure and improve the so-called "conditioning" of optimization problems, i.e., identifying the underlying properties of the problem at hand that dictate problem behavior, such as sensitivity of the solutions to perturbation in the problem data, the relative ease or difficulty of solving the problem via numerical algorithms, etc. Recognition of these properties motivates obtaining improved formulations and solution techniques of many optimization problems of great practical importance.

凸优化是数学优化的一个重要领域。最近，一个新的和强大的理论条件数的凸锥线性优化问题已经发展。这些数字捕捉了问题条件反射的直观概念，作为对输入数据中扰动的问题敏感性的度量。它们在研究这些问题的许多行为特征方面很重要。本研究探讨了条件反射在问题行为中的作用。特别感兴趣的是解决问题的算法的性能，以及对问题数据执行有意义的敏感性分析的能力。这项研究的两个不同但相关的途径是开发优化问题的预处理方法（即，找到具有更好性质的手头问题的等价重新表述），最终目标是探索和量化实际优化算法中的各种预处理方法，并将问题调节的概念扩展到通常位于圆锥线性形式之外的实际问题，导致更好地理解问题行为，执行有意义的灵敏度分析的能力，以及算法性能的潜在改进。广泛的目标是提高优化的建模和求解能力，这是运筹学的基本工具。具体的重点是探索方法来衡量和改善所谓的“条件”的优化问题，即，识别当前问题的基本属性，这些属性决定了问题的行为，例如解决方案对问题数据中的扰动的敏感性，通过数值算法解决问题的相对容易或困难等。