|
The goal of this work is to propose a tractable theory
for optimization under uncertainty.
The first motivation for robust optimization is data uncertainty for structured mathematical programming problems. Under this perspective, we investigate different choices of uncertainty sets to model data uncertainty and characterize the structure of the resulting robust counterparts. We particularly focus on uncertainty sets for which the robust problem inherits the computational complexity of the underlying deterministic problem. Examples of concrete results in this direction include: (a) the robust counterpart of a linear programming problem (LP) is still an LP and of a mixed integer programming problem (MIP) is still a MIP of comparable size. (b) The robust counterpart of a polynomially solvable $0-1$ discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. (c) Robust network flows can also be solved as a polynomial number of modified network flow problems. (d) The robust counterpart of an $NP$-hard $\alpha$-approximable $0-1$ discrete optimization problem, remains $\alpha$-approximable. (e) Robust conic optimization problems retain their original structure. Specifically, robust second order cone problems (SOCPs) remain SCOPs and robust semidefinite optimization problems (SDPs) remain SDPs.
The second motivation of robust optimization is to model stochastic and dynamic optimization problems using uncertainty sets as opposed to probability distributions. Unlike dynamic and stochastic programming this robust approach does not suffer from the curse of dimensionality. As a test case, we apply this perspective to classical supply chain optimization problems under uncertainty, and show (a) the proposed approach is computationally tractable for high dimensions and in many cases leads to stronger solutions, (b) the optimal robust policies have the same structure as optimal policies obtained via dynamic programming; moreover, the robust approach is capable of characterizing the structure of the optimal policy even in cases where the structure of the optimal policy obtained via dynamic programming is unknown.
Current work has focused on constructing uncertainty sets from data, solving multistage adaptive optimization problems, as well as a great variety of applications in energy, operations management, finance and health care.
In this work we aspire to develop methods for personalized medicine using a variety of analytics tools. So far, we have developed methods to a) personalized diabetes management and b) design of clinical trials for cancer. Current work focuses on a variety of other diseases.
We have developed a system to make personalized lifestyle and health decisions for diabetes management, as well as for general health and diet management. In particular, we address the following components of the system: (a) efficiently learning preferences through a dynamic questionnaire that accounts for human behavior; (b) modeling blood glucose behavior and updating these models to match individual measurements; and (c) using the learned preferences and blood glucose models to generate an overall diet and exercise plan using mixed-integer robust optimization. We have implemented our system as an online application called LIA (Lifestyle Analytics).
We have also developed a system for the analysis and design of clinical trials that provides insights into what is the best currently available drug combination to treat a particular form of cancer and how to design new clinical trials that can discover improved drug combinations. We developed semi-automated extraction techniques to build a comprehensive database of data from clinical trials. We use this database to develop statistical models from earlier trials that are capable of predicting the efficacy and toxicity of the combination of the drugs used, when the drugs used have been seen in earlier trials, but in different combinations. Then, using these statistical models, we developed optimization models that select novel treatment regimens that could be tested in clinical trials, based on the totality of data available on existing combinations. We have presented our work in the context of gastric cancer, one of the leading causes of cancer death worldwide. Ultimately, our approach offers promise for improving life expectancy and quality of life for cancer patients at low cost.
Modern probability theory, whose foundation is based on the axioms set forth by Kolmogorov, is currently the major tool for performance analysis in stochastic systems. While it offers insights in understanding such systems, probability theory is really not a computationally tractable theory in high dimensions. Correspondingly, some of its major areas of application remain unsolved when the underlying systems become multidimensional: Queueing networks, network information theory, pricing multi-dimensional financial contracts, auction design in multi-item, multi-bidder auctions among others.
We have proposed a new approach to analyze stochastic systems based on robust optimization. The key idea is to replace the Kolmogorov axioms as primitives of probability theory, with some of the asymptotic implications of probability theory: the central limit theorem and law of large numbers and to define appropriate robust optimization problems to perform performance analysis. In this way, the performance analysis questions become highly structured optimization problems (linear, conic, mixed integer) for which there exist efficient, practical algorithms that are capable of solving truly large scale systems.
We have demonstrated that the proposed approach achieves computationally tractable methods for (a) analyzing queueing systems in the transient domain and queueing networks in the steady-state domain, (b) characterizing the capacity region of network information theory and associated coding and decoding methods generalizing the work of Shannon, (c) pricing multi-dimensional financial contracts generalizing the work of Black, Scholes and Merton, (d) designing multi-item, multi-bidder auctions generalizing the work of Myerson.
Our overall objective is to develop an alternative to the classical theory of probability for performance analysis of stochastic systems that scales with dimension.
Key problems of classification and regression can naturally be written as optimization problems. While continuous optimization approaches has had a significant impact in statistics, discrete optimization has played a very limited role, primarily based on the belief that mixed integer optimization models are computationally intractable. While such beliefs were accurate two decades ago, the field of discrete optimization has made very substantial progress.
We apply modern first order optimization methods to find feasible solutions for classical problems in statistics, and mixed integer optimization to improve the solutions and to prove optimality by finding matching lower bounds.
Specifically, we report results for the classical variable selection problem in regression currently solved by LASSO heuristically, least quantile regression, factor analysis. Furthermore, we present an approach to build regression models based on mixed integer optimization. In all cases we demonstrate that the solutions found by modern optimization methods outperform the classical approaches. Most importantly, this body of work suggests that the belief widely held in statistics that mixed integer optimization is not practically relevant for statistics applications needs to be revisited.
Our objective is develop the theory of statistics under a modern optimization lens. We will be offering a new doctoral level class in the spring of 2016 that revisits the major statistical problems under this lens.
Air Transportation
Analytics
Applied Probability
Approximation Algorithms
Fairness and Resource Allocation
Finance
Health Care
Large Deviations
Machine Learning under a Modern Optimization Lens
Moment problems
Operations Management
Optimization
Queuing Theory
Revenue Management
Robust Optimization
Stochastic Networks
Stochastic Scheduling
Vehicle Routing
Earlier Papers |
