Problem conditioning in convex optimization: theory and algorithms

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

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.