We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time when and place where the survey is conducted, and the level of comfort the interviewee has in sharing information with the interviewer. We propose a method for learning optimal robust classification trees based on mixed-integer robust optimization technology. In particular, we demonstrate that the problem of learning an optimal robust tree can be cast as a single-stage mixed-integer robust optimization problem with a highly nonlinear and discontinuous objective. We reformulate this problem equivalently as a two-stage linear robust optimization problem for which we devise a tailored solution procedure based on constraint generation. We evaluate the performance of our approach on numerous publicly available datasets, and compare the performance to a regularized, non-robust optimal tree. We show an increase of up to 12.48\% in worst-case accuracy and of up to 4.85\% in average-case accuracy across several datasets and distribution shifts from using our robust solution in comparison to the non-robust one.

We present a new algorithm for convex separable quadratic programming (QP) called NysPCG-IP-PMM, a regularized interior-point solver that uses low-rank structure to accelerate solution of the Newton system. The algorithm combines the interior point proximal method of multipliers (IP-PMM) with the randomized Nyström preconditioned conjugate gradient (NysPCG) method as the inner linear system solver. Our algorithm is matrix-free: it accesses the input matrices solely through matrix-vector products, as opposed to methods involving matrix factorization. It works particularly well for separable QP instances with dense constraint matrices. We establish convergence of NysPCG-IP-PMM. Numerical experiments demonstrate its superior performance in terms of wall clock time compared to previous matrix-free IPM-based approaches.

Distributionally robust optimization (DRO) has become ubiquitous to address uncertainties inherent in many operations management (OM) problems. Recently, an alternative goal-driven framework, robust satisficing (RS), is proposed. Robust satisficing aims to attain a prescribed target, such as avoiding overshooting the cost budget as much as possible under uncertainty. The goal-driven modeling philosophy naturally fits many OM problems, yet there is a lack of direct comparisons between DRO and RS in OM applications. In this paper, we uncover connections between DRO and RS. Suppose both models are based on the Wasserstein metric and consider a risk-aware convex objective function affected by uncertain parameters. We demonstrate that they share the same solution family. We establish the correspondence between the radius parameter in DRO and the target parameter in RS such that the optimal solutions to the two models are the same. Inspired by the globalized distributionally robust counterpart (GDRC), we extend the analysis to GDRC and the globalized robust satisficing (GRS). We reveal that GDRC and GRS have the same solution families as DRO and RS, respectively, indicating that globalized models do not necessarily enhance model performance. More importantly, we establish novel results on the equivalence of DRO, GDRC, RS, and GRS models under previously stated conditions. To illustrate our findings, we conduct numerical studies on adaptive network lot-sizing, facility location, and portfolio management problems. Although the equivalence result holds, the performance of the DRO and RS models can vary depending on how the model parameters are selected. The experiment results show that different operations management problems exhibit different model preferences. Additionally, the experiments provide insights for practitioners, such as the use of cross-validation can reflect the actual model preference when data is sufficient.

Optimal stopping is the problem of determining when to stop a stochastic system in order to maximize reward, which is of practical importance in domains such as finance, operations management and healthcare.

The majority of existing approximate dynamic programming methods for high-dimensional optimal stopping practice produce deterministic linear policies -- policies that deterministically stop based on the sign of a weighted sum of basis functions -- but are not guaranteed to find the optimal policy within this policy class given a fixed basis function architecture. The most popular of such methods is least squares Monte Carlo (LSM), which recurses backwards in time from the last period to the first, using least squares regression to predict the current continuation value at each period. Such an approach is motivated by the fact that least squares regression recovers conditional expectations exactly when one carries out the regression over an unrestricted function class and with an infinite sample of trajectories, leading to the optimal policy. However, when one restricts to a finite sample and a function class defined as the span of a finite set of basis functions, one is not guaranteed to obtain the best performing policy within that function class. This observation mirrors recent developments in contextual stochastic optimization, where it has been observed that predictive models chosen to optimize predictive performance (e.g., squared error) often do not yield good prescriptive performance when they are used within a downstream optimization problem (the "predict-then-optimize" paradigm).

In this paper, we propose a new methodology for optimal stopping based on randomized linear policies, which choose to stop with a probability that is determined by a weighted sum of basis functions. We motivate these policies by establishing that under mild conditions, given a fixed basis function architecture, optimizing over randomized linear policies is equivalent to optimizing over deterministic linear policies. We additionally motivate these policies by developing simple pathological instances in which LSM can be made to perform arbitrarily poorly relative to the optimal policy, while an exact optimization over deterministic/randomized policies either exactly recovers the optimal policy or otherwise perform arbitrarily closely to optimal.

We formulate the problem of learning randomized linear policies from data as a smooth non-convex sample average approximation (SAA) problem. We theoretically prove the almost sure convergence of our randomized policy SAA problem and establish bounds on the out-of-sample performance of randomized policies obtained from our SAA problem based on Rademacher complexity. While the SAA problem is in general NP-Hard, we develop a novel alternating maximization approach for solving it that is structurally distinct from the backward recursion technique that is typical of classical approaches such as LSM.

Through numerical experiments on a benchmark family of option pricing problem instances, we show that our approach can substantially outperform state-of-the-art methods.