Optimization under Variable Uncertainty

Sharma, Kartikey

doi:https://doi.org/10.21985/n2-d9kb-fm86

Work

Optimization under Variable Uncertainty

Public

Download PDF

Download All Files (.zip)

In this dissertation, we study models and methods to address uncertainties that can vary in optimization problems. Robust optimization is a popular approach for optimization under uncertainty, especially if limited information is available about the distribution of the uncertainty. It models the uncertainty through sets and finds a robust optimal solu- tion that is feasible for all realizations of the uncertainty within the set and is optimal for the worst-case realization. The structure of these sets determines the complexity of the resulting optimization problem. In most models, the uncertainty set is assumed to be exogenous i.e., pre-determined and is unaffected by decisions or other uncertainty realiza- tions in the problem. This thesis introduces endogenous uncertainty models, which may be affected by decisions that are made in the problem or by other uncertainty realizations within the problem. In the first chapter, we take a step towards generalizing robust linear optimization to problems with decision dependent uncertainties. We show these problems to be NP- complete in general settings. To alleviate these computational inefficiencies, we introduce a class of uncertainty sets whose sizes depend on binary decisions. We propose reformu- lations that improve upon alternative standard linearization techniques. To illustrate the advantages of this framework, a shortest path problem is discussed, where the uncertain arc lengths are affected by decisions. The proposed notion of proactive uncertainty con- trol provides modeling and performance advantages, and mitigates over conservatism of common robust optimization approaches. While the impact of the decisions on the uncertainty set was fixed in the first chap- ter, we extend the decision-dependent models to allow for uncertainty in the influence of decisions on the sets in the second chapter. Here, the exact impact of the decision on the uncertainty set itself may be uncertain. This situation arises in many practical settings where the decision’s impact may not be known a priori. It is especially relevant for prob- lems in which the decision is on the gathering of information. We leverage robust and stochastic optimization to incorporate uncertain influence into the optimization problem. We then evaluate the performance of these models on a power systems unit commitment problem. The third chapter discusses the topic of Connected Uncertainties, i.e., uncertainty mod- els in which past realizations influence future uncertainties. For this class of problems, we develop a novel modeling framework that naturally incorporates this dependence via connected uncertainty sets, whose parameters at each period depend on previous uncer- tainty realizations. To find optimal here-and-now solutions, we reformulate robust and distributionally robust constraints for popular set structures and demonstrate this mod- eling framework numerically on broadly applicable knapsack and portfolio optimization problems. In the fourth chapter of the thesis, we leverage the idea of connected uncertainty to de- velop robust adaptive classifiers for streaming data. Classification algorithms are effective, when data can be modeled by time-invariant distributions. In streaming settings, a classi- fier needs to be updated continuously, and hence static classifiers lose their reliability over time. We consider streaming data sets in which the behavior of each class can be mod- eled by a time series. For classification of such streaming data, we extend the Minimax Probability Machine to incorporate a time series model using the principles of connected uncertainty sets. We illustrate the new methods by numerical experiments on synthetic data. Overall, this thesis led to insights in two directions. First, we introduced uncertainty sets which depended on decisions. This enabled us to model reducing the uncertainty at a price, which is common in practical applications. This approach also allowed us to capture many problems in which the uncertainty naturally depends on decisions. In the second direction, we studied multi-period problems where today’s uncertainty can affect the uncertainty tomorrow. This led us to capture correlations over time, which are common in many applications. Our future goal is to further extend this work in both directions. Specifically, we want to solve larger unit commitment problems, solve the problem of continuous variables affecting uncertainty sets and merge decision dependent and connected uncertainties.

Creator