A shrinkage path heuristic is proposed that reduces the solution of a DRO problem to a one-dimensional search over the line segment connecting the sample average approximation (SAA) and the (more demanding but practically solvable) classical robust optimization solution.
Abstract
Wasserstein distributionally robust optimization (DRO) is a versatile and widely adopted framework for decision-making under uncertainty, yet its standard deterministic reformulations generally contain non-convex inner subproblems that are challenging to solve. To address this issue, we propose a shrinkage path heuristic that reduces the solution of a DRO problem to a one-dimensional search over the line segment connecting the (typically benign) sample average approximation (SAA) and the (more demanding but practically solvable) classical robust optimization solution. We derive a priori suboptimality bounds in stylized settings and, for the general case, a posteriori bounds obtained by applying a similar heuristic to a dual formulation. Numerical experiments on a multi-item newsvendor and an appointment scheduling problem show that the shrinkage path heuristic attains 85-110% (resp. 45-70%) of the out-of-sample performance improvements of Wasserstein DRO over SAA, at a fraction of the computational cost.
This paper reduces the inner worst-case expectation problem exactly to a scalar budget allocation task, and embeds this procedure within an oracle-based distributional best-response framework to directly compute an approximate primal-dual solution to the overall DRO problem.
Guixian Chen, S. Fattahi, Soroosh Shafiee· 1 citation
It is shown that BiCS is applicable to standard DRO, almost-sure DRO, DRO with various chance constraints, and DRO with ambiguity sets strengthened by local information, and demonstrates superior performance, including solving cases where the examined compact reformulations are unavailable or computationally difficult.
We develop a certified, scalable approximation for high-dimensional Wasserstein distributionally robust portfolio optimization. For expected-utility maximization under order-one Wasserstein ambiguity, standard duality yields a semi-infinite convex program. For long-only portfolios with box support under the one-norm ground metric, an exact sample-specific vertex reformulation provides an exponential-size computational benchmark. We then majorize the utility by supporting hyperplanes and dualize the support subproblems, obtaining a finite hyperplane--dual formulation over compact polyhedral supports. Under the one-norm ground metric and polyhedral portfolio constraints, this formulation is a polynomial-size linear program. The uniform utility-approximation error bounds both the robust-value error and the near-optimality gap for the original robust problem. Experiments validate the certified approximation and demonstrate monthly 476-asset rebalancing and computational scalability to 1,000 assets.
We consider stochastic multi-objective optimization over a nonempty closed convex set, where every objective is an expectation and only sample-gradient information is available. We develop a line-search-free and function-value-free adaptive projected-gradient algorithm for the sample-average approximation (SAA) problem. Each iteration computes a feasible regularized multi-gradient step and updates the regularization parameter from the projected step length. A normal-cone-based certificate yields descent estimates and an explicit complexity bound for the Pareto-stationarity residual of the SAA problem. The consistency of SAA gradients then transfers vanishing SAA residuals to Pareto stationarity for the population problem, while an additional concentration argument gives a finite-sample residual bound on compact sets. Experiments on synthetic problems, classification, portfolio selection, multi-task learning, and robot control illustrate the practical performance of our algorithm.
We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independent-sample SEG (I-SEG) and assume either that the domain is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes.
An algorithm for composite optimization problems of the form min x f (x) + g(T x), where f is smooth and g may be non-smooth is proposed, which leverages the Moreau envelope to smooth the non-smooth component while adapting to problem geometry through linear minimization oracles.
Farid Najar· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
