Inverse problems, Robust Optimization and Mathematical Programs with Equilibrium Constraints: Algorithms and Applications

Columbia University, New York NY

Investigators

Abstract

This project involves the study and development of optimization methods for modeling and solving inverse problems, robust optimization problems, and mathematical programs with equilibrium constraints (MPECs). The goal of inverse problems is to determine the most likely causes for an observed or desired effect. Such problems arise in a number of important military, imaging, signal processing, biomedical, remote-sensing, and geological applications. Inverse problems are ill-posed in the sense that a small error in measurement can lead to large errors in the estimated quantities. The regularization techniques used to obtain stable solutions to inverse problems give rise to general nonlinear programming problems. In special cases, such as imaging and signal processing, the inverse problem can be reformulated as a tractable convex programming problem. In most cases, e.g. shape optimization, however, a non-convex optimization problem needs to be solved. Robust optimization is an approach for modeling and managing uncertainty in an optimization context. Here, rather than solving a parameter identification problem, one is concerned with constrained optimization problems in which the parameters are data and, due to measurement or estimation errors, are only known to lie within bounded uncertainty sets. In ambiguous chance-constrained (robust) optimization it is assumed the parameters are random variables with an uncertain distribution that is only known to lie within an uncertainty set of probability measures. Fortunately, for certain classes of uncertainty sets, robust optimization problems give rise to tractable convex programming problems as long as the non-robust versions of the problems are themselves convex. These problems arise in areas as diverse as engineering design, portfolio selection, and the design of service networks. MPECs have their roots in game theory and bi-level optimization. They are optimization problems in which some of the constraints are parametric variational inequalities or complementarity systems that arise from the optimality conditions for a lower-level optimization problem. MPECs are a good model for a number of important economic problems, where the equilibrium constraints arise from competitive forces, and optimal engineering design problems. Consequently, developing scalable solution algorithms for MPECs is of considerable practical importance. In general, solving problems from any of these three classes is quite difficult and requires significant computational resources. At first glance, these three modeling paradigms appear quite distinct. Consequently, there has been very little interaction between the algorithmic developments that have occurred in these three areas. While all of the paradigms have a unique structure and a special set of issues, they have much in common. Besides their formal analytical similarity, depending on the context all three paradigms are often used to model the same application. A goal of this project is to leverage the common features of these paradigms to develop new and more efficient solution methods. A second goal is to provide interdisciplinary training in inverse problems, robust optimization, and MPECs through the development of new doctoral courses and involvement of students in theoretical research and software development.