PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributionally Robust Optimization with Decision Dependent Ambiguity Sets

Fengqiao Luo, Sanjay Mehrotra

arXiv:1806.09215v1math.OC

TL;DR

Endogenous uncertainty arises when a system’s uncertain characteristics depend on decisions, but standard ambiguity sets need not capture that dependence. This paper extends dual reformulations to decision-dependent ambiguity sets across five families; the resulting models are generally non-convex and may require further investigation for efficient algorithms.

  • Problem

    The paper addresses distributionally robust optimization when the ambiguity set of candidate distributions depends on decisions, as occurs with endogenous uncertainty.

    Source: §1 · p. 1

  • Method

    The framework dualizes the inner worst-case expectation for five decision-dependent ambiguity-set families, using linear, conic, or Lagrangian duality.

    Source: §1 · p. 2, §3 · p. 7

  • Results

    The analysis suggests that DRO settings admitting dual reformulations also admit dual reformulations in the decision-dependent case.

    Source: §4 · p. 15

  • Takeaways & Limitations

    The reformulations provide models for endogenous uncertainty, while their non-convex structure leaves room for further tailored reformulations and algorithms.

    Source: §1 · p. 1, §4 · p. 15

    The main text considers finite support for simplicity, and the reformulated problems are generally non-convex and require further investigation toward efficient algorithms.

    Source: §1 · p. 2, §4 · p. 15

Abstract

from arXiv · show

We study decision dependent distributionally robust optimization models, where the ambiguity sets of probability distributions can depend on the decision variables. These models arise in situations with endogenous uncertainty. The developed framework includes two-stage decision dependent distributionally robust stochastic programming as a special case. Decision dependent generalizations of five types of ambiguity sets are considered. These sets are based on bounds on moments, Wasserstein metric, $\phi$-divergence and Kolmogorov-Smirnov test. For the finite support case, we use linear, conic or Lagrangian duality to give reformulations of the models with a finite number of constraints. These reformulations allow solutions of such problems using global optimization techniques. Certain reformulations give rise to non-convex semi-infinite programs. Techniques from global optimization and semi-infinite programming can be used to solve these reformulations.

1 Introduction

The paper models endogenous uncertainty by allowing the ambiguity set of distributions to depend on decisions, a setting that includes two-stage decision-dependent stochastic programs. It extends dual reformulations to this setting across several ambiguity-set specifications.

1 Introduction

  • Decision-dependent ambiguity sets model systems whose uncertain performance characteristics depend on design decisions.The framework includes two-stage decision-dependent distributionally robust stochastic programs, assuming complete recourse for the recourse formulation.Source: §1 · pp. 1–2
  • Five decision-dependent ambiguity-set families are reformulated using linear, conic, or Lagrangian duality as appropriate.The families cover component-wise moment and scenario-probability bounds, mean and covariance inequalities, Wasserstein distance, φ-divergence, and the multivariate Kolmogorov-Smirnov test.Source: §1 · p. 2
  • For finite support, the reformulations have finitely many constraints and can be approached with global optimization techniques.Some continuous-support cases instead yield semi-infinite reformulations that can use cutting-surface and other algorithms.Source: §1 · pp. 2–3
  • The paper prioritizes modeling frameworks over computational complexity or developing more efficient algorithms.The authors leave algorithm development for future studies.Source: §1 · p. 2

2 Literature Review

The literature review first surveys optimization with decision-dependent uncertainty, then reviews distributionally robust optimization work relevant to the paper.

2.1 Literature review on optimization with decision dependent uncertainty

  • The review spans decision-dependent uncertainty in stochastic and robust optimization, including applications in networks, resource management, finance, and process design.Prior approaches include scenario-distribution models, multistage disjunctive formulations, and decision-dependent uncertainty sets.Source: §2.1 · pp. 3–4

2 Literature Review

  • The review covers DRO as a min-max framework over an ambiguity set of candidate distributions and previews the literature areas addressed.It identifies optimization with decision-dependent parameters and recent DRO developments as the two review topics.Source: §2 · p. 3, §2.2 · p. 5

2.2 Literature review on distributionally robust optimization

  • Prior DRO ambiguity sets use moment constraints or statistical distances, including Wasserstein metrics and φ-divergence.The review also describes tractability results and reformulations for several such models.Source: §2.2 · pp. 5–6

3 Reformulation of (D3RO)

Under a decision-independent finite-support assumption, the section derives reformulations of decision-dependent DRO for five ambiguity-set specifications. The formulations use duality and, for moment bounds, minimax and strong-duality arguments.

3 Reformulation of (D3RO)

  • The reformulations assume decision-independent finite support, while allowing the support and scenario count to change with decisions through zero-probability scenarios.The candidate distributions are represented by probability-mass vectors, and the inner problem is dualized for the five ambiguity-set types.Source: §3 · pp. 6–7

3.1 Ambiguity sets defined by simple measure and moment inequalities

  • Simple measure and moment inequalities yield a nonlinear-program reformulation when the decision-dependent ambiguity set is nonempty.The framework permits lower and upper measure bounds and standard or generalized moment functions; a two-stage recourse case is also formulated.Source: §3.1 · pp. 7–8

3.2 Ambiguity sets defined by bounds on moment constraints

  • For moment-bound ambiguity sets, the section derives reformulations using minimax and strong-duality arguments, with the stated theorem requiring Slater’s condition.The decision-dependent set generalizes the one of Delage and Ye; the paper also gives a two-stage formulation.Source: §3.2 · pp. 8–10

3.3 Ambiguity sets defined by Wasserstein metric

  • For decision-dependent Wasserstein ambiguity, a finite-support linear-program dual yields a reformulation, with a continuous-support generalization given in the appendix.The two-stage case has a separate corollary.Source: §3.3 · pp. 10–11

3.4 Ambiguity sets defined using φ-divergence

  • For φ-divergence ambiguity, the paper gives two reformulations, including a semi-infinite program under a Slater condition.The alternative reformulation uses KKT optimality conditions and strong duality.Source: §3.4 · pp. 12–13

3.5 Ambiguity sets defined based on the Kolmogorov-Smirnov test

  • For KS-distance ambiguity, the paper gives a reformulation and a two-stage corollary, and notes that the reformulation extends to continuous support.The KS-distance definition is introduced for univariate distributions and can be generalized to finite-support random vectors.Source: §3.5 · pp. 13–15

4 Concluding Remarks

The paper extends DRO dual reformulations to decision-dependent ambiguity sets and discusses how such sets can be estimated from data. The resulting models are generally non-convex, though additional structure may arise under further assumptions.

4 Concluding Remarks

  • Trial-decision samples can support empirical decision-dependent ambiguity sets by learning how ambiguity parameters vary with decisions.The learned analytical relation can be extrapolated to a general decision.Source: §4 · p. 15
  • The reformulated models are generally non-convex and require further investigation to develop efficient algorithms.Additional assumptions on decision-dependent parameters and the feasible set may expose structure for refined reformulations and algorithms.Source: §4 · p. 15
  • The paper shows that DRO dual formulations can be extended to decision-dependent ambiguity sets.Source: §4 · p. 15

Appendix A Reformulation of (D3RO) with Wasserstein metric and continuous support of random pa-

For Wasserstein ambiguity sets with continuous support, the paper gives a semi-infinite reformulation based on observed samples and an empirical distribution as the center of the Wasserstein ball.

Appendix A Reformulation of (D3RO) with Wasserstein metric and continuous support

  • The decision-dependent Wasserstein ambiguity set uses the empirical distribution from N observed samples at a decision as the Wasserstein-ball center.Source: rameters · p. 16
  • Theorem 6 reformulates the continuous-support Wasserstein model as a semi-infinite program with constraints over support points and observed samples.The constraints include h(x, s) − v_i − v_{N+1} · d(s, ξ_i) ≤ 0 for all s ∈ Ξ and i ∈ [N].Source: rameters · p. 16
  • The proof obtains the reformulation by dualizing an inner conic linear program and combining it with the outer minimization over decisions.Source: rameters · p. 16

Appendix B Reformulation of (D3RO) with K-S distance and continuous support of the random parame-

For continuous support contained in a hyper-rectangle, the paper reformulates the decision-dependent K-S ambiguity model as a semi-infinite program using a partition based on observed samples.

Appendix B Reformulation of (D3RO) with K-S distance and continuous support

  • The hyper-rectangle is partitioned into (N + 1)^d cells using intervals formed from the sorted observed sample components.Source: ters · p. 17
  • The reformulation converts K-S ambiguity constraints into expectation constraints on cell indicator functions, then applies conic duality.Source: ters · pp. 17–18
  • Theorem 7 gives a semi-infinite reformulation of the K-S model when h(x, s) is continuous over the hyper-rectangle.Its constraints require j-indexed variables plus γ to bound h(x, s) over the closures of the partition cells.Source: ters · pp. 17–18

Appendix C A cutting-surface algorithm for solving

The passage identifies the subject as reformulation of D3RO with continuous support.

Appendix C A cutting-surface algorithm for solving

of the random parameters

For continuous support, the reformulations of (D3RO) are special cases of semi-infinite programs. A cutting-surface algorithm solves these programs through finite relaxations, with finite termination under stated compactness and continuity conditions.

  • For continuous support Ξ, the reformulations of (D3RO) are special cases of semi-infinite programs.Source: of the random parameters · p. 18
  • The cutting-surface method repeatedly solves a finite master relaxation and adds a constraint violated by its current solution, using master and separation oracles.The master problem uses a finite subset T′ of T; Algorithm 1 initializes the constraint set as empty and updates it with identified cuts.Source: of the random parameters · p. 19
  • Under compactness of X × T and continuity of g(x, t), Algorithm 1 terminates finitely and returns an ε-optimal solution.The paper defines ε-optimality as ε-feasibility with objective value no greater than Val(gen-SIP).Source: of the random parameters · p. 19
  • In the decision-dependent finite-support case, the separation oracle is a function evaluation, enabling sequential addition of cuts for violated inequalities.Source: of the random parameters · p. 20
Loading 1806.09215v1…