Problem conditioning in convex optimization: theory and algorithms

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

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.