发表在 Operations Research, 2022. DOI: https://doi.org/10.1287/opre.2021.2238.
Area of Review: Optimization
Keywords: robust optimization; robust satisficing; data-driven; discrete optimization; stochastic optimization; fragility measure
这篇文章提出了 robust satisficing 这一鲁棒优化的 framework。
In this paper, we introduce a new target-oriented model for robust data-driven optimization termed robust satisficing.
The goal of robust satisficing is to maximize the robustness to uncertainty of achieving a satisfactory target.
以下公式编号均为论文中的公式编号。
对于一个带有不确定性的优化问题： $$ \begin{array}{rlr} Z^{\ast}=\min & \mathbb{E}_{\mathbb{P}^{\ast}}[f(x, \tilde{z})] \\ \text { s.t. } & x \in \mathcal{X}, \end{array}\tag{1} $$ 其中 $x$ 是决策变量，$\tilde{z} \sim \mathbb{P}^\ast$ . 事实上真实分布 $\mathbb{P}^\ast$ 我们是不知道的，我们只有一些 sample，有一个经验分布 $\hat{\mathbb{P}}$ 。
但是真实分布应该是接近经验分布的，给出一个度量我们可以找到以经验分布为中心的一个球： $$ \mathcal{B}(r):=\left\{\mathbb{P} \in \mathcal{P}_{0}(\mathcal{Z})\;\middle\vert\;\begin{array}{l} \tilde{\boldsymbol{z}} \sim \mathbb{P} \\ \Delta(\mathbb{P}, \hat{\mathbb{P}}) \leq r \end{array}\right\} $$ 所以 data-driven robust optimization 可以写成： $$ \begin{array}{rlr} Z_r=\min & \displaystyle\sup_{{\mathbb{P}}\in \mathcal{B}(r)} \mathbb{E}[f(x, \tilde{z})] \\ \text { s.t. } & x \in \mathcal{X}, \end{array} \tag{4} $$ 定义 type-1 Wasserstein metric: $$ \Delta_{W}(\mathbb{P}, \hat{\mathbb{P}}):=\inf _{\mathbb{Q} \in \mathcal{P}_{0}\left(\mathcal{Z}^{2}\right)}\left\{\mathbb{E}_{\mathbb{Q}}[\|\tilde{z}-\tilde{v}\|] \mid(\tilde{z}, \tilde{v}) \sim \mathbb{Q}, \tilde{z} \sim \mathbb{P}, \tilde{v} \sim \hat{\mathbb{P}}\right\} $$ 它是一个合适的度量。
Robust satisficing
文章提出了一个新的模型，叫做 robust satisficing: $$ \begin{aligned} \kappa_{\tau}=\min\; & k \\ \text {s.t. } & \mathbb{E}_{\mathbb{P}}[f(x, \tilde{z})]-\tau \leq k \Delta(\mathbb{P}, \hat{\mathbb{P}}) \quad \forall \mathbb{P} \in \mathcal{P}_{0}(\mathcal{Z}) \\ & x \in \mathcal{X}, k \geq 0 \end{aligned} \tag{6} $$ $\tau$ 是一个事先给定的 targeted level。
如果选择 $\tau = Z_r$，这意味着最优解满足： $$ \begin{array}{ll} \mathbb{E}_{\mathbb{P}}[f(x, \tilde{z})]-\tau \leq 0 & \forall \mathbb{P} \in \mathcal{B}(r) \\ \mathbb{E}_{\mathbb{P}}[f(x, \tilde{z})]-\tau \leq+\infty & \forall \mathbb{P} \in \mathcal{P}_{0}(\mathcal{Z}) \backslash \mathcal{B}(r) \end{array} $$ 我个人感觉这样建模的思想与 Generalized Robust Counterparts 相似（《Robust Optimization》 Ben-Tal, Chapter 11）。能在一定程度上缓解鲁棒优化保守型的缺点。
用经验分布解这个问题，得到 $Z_0$；用DRO方法解这个问题，得到 $Z_r$，一般来说 $Z_0 < Z_r$。
Robust satisficing 要求： $$ \mathbb{E}_{\mathbb{P}}[f(x, \tilde{z})]-\tau \leq k_\tau \Delta(\mathbb{P}, \hat{\mathbb{P}}) \quad \forall \mathbb{P} \in \mathcal{P}_{0}(\mathcal{Z}) $$ 意思是说，并不要求所有的 $\mathcal{B}(r)$ 中的分布满足 $$
Tractable reformation
如果不确定参数的 support $\\mathcal{Z}$ 是一个闭凸集，那么 robust satisficing 等价于： $$ \begin{aligned} \kappa_{\tau}=\min & k \ \text { s.t. } & \frac{1}{S} \sum_{s \in[S]} y_{s} \leq \tau \ & y_{s} \geq \sup {z{s} \in \mathcal{Z}}\left{f\left(x, z_{s}\right)-k\left|z_{s}-\hat{z}_{s}\right|\right} \quad \forall s \in[S] \ & x \in \mathcal{X}, k \geq 0, \end{aligned} \tag{9} $$ 分析的方法类似于 Wasserstein DRO 。
Stochastic-free robust optimization
把 $r$ 取成0，问题变成普通的经验损失函数最小化，而把 $r$ 取的足够大（把所有 $\\mathcal{Z}$ 上的分布都考虑进来）就是经典的鲁棒优化。 直接根据式(9)，对于名义值为 $\\hat{z}$ 的不确定参数和不确定集 $\\mathcal{Z}$，stochastic-free robust satisficing model 就是： $$ \begin{array}{ll} \min & k\ \text { s.t. } & f(x, z) \leq \tau+k|z-\hat{z}| \quad \forall z \in \mathcal{Z} \ & x \in \mathcal{X}, \quad k \geq 0, \end{array} $$
Fragility measure
fragility measure 可以理解为一种反向的 satisficing measure，satisficing measure 衡量的是满意测度，而 fragility measure 衡量的是不满意测度。$\\tau$ 是我们期望的 target，如果 $f(x, \\tilde{z}) \\leq \\tau$，说明符合期待，如果 $f(x, \\tilde{z}) > \\tau$ ，说明不符合我们的期待。所以，最小化我们的 discontentment，就是如下的优化问题： $$ \begin{array}{ll} \min & \rho(f(x, \tilde{z})-\tau) \ \text { s.t. } & x \in \mathcal{X} \end{array} \tag{12} $$ 为了契合这种思想，文章定义了一种 satisficing measure，叫做 fragility measure。 \ast\astDefinition (Fragility Measure).\ast\ast The functional $\\rho: \\mathcal{L}$ $\\longmapsto[0,\+\\infty]$ is a fragility measure associated with the probability distribution $\\hat{\\mathbb{P}} \\in \\mathcal{P}\_{0}$ if and only if it has the following representation $$ \begin{aligned} \rho(\tilde{v})= \min; & k \ \text { s.t. } & \mathbb{E}{\mathbb{P}}[\tilde{v}] \leq k \Delta(\mathbb{P}, \hat{\mathbb{P}}) \quad \forall \mathbb{P} \in \mathcal{P}{0} \ & k \geq 0 \end{aligned} $$ for some probability distance function $\\Delta$ . 文章的第三章，就是在强调 robust satisficing 的 implications。
Satisficing Measures
论文：Satisficing Measures for Analysis of Risky Positions. DOI: https://doi.org/10.1287/mnsc.1080.0929
satisficing measure 是一个测度，它用来衡量一个人对自己 portfolio 的\ast\ast满意程度\ast\ast。
设 $\\tau$ 是投资者的 aspiration level，它是一个随机变量；一个投资组合的 uncertain payoff $X$ 也是随机的。\asttarget premium\ast $V=X\-\\tau$ 也是一个随机变量，它的正负反映了投资组合的收益是否达到投资者的期望。
\ast\astDEFINITION.\ast\ast A function $\\rho: \\mathcal{L} \\rightarrow[0, \\bar{\\rho}]$, where $\\bar{\\rho} \\in$ $\\{1, \\infty\\}$, is a \astsatisficing measure\ast defined on the target premium if it satisfies the following axioms for all $X, Y \\in \\mathscr{X}$ :
- Attainment content: If $X \\geq 0$, then $\\rho(X)=\\bar{\\rho}$
- Nonattainment apathy: If $X<0$, then $\\rho(X)=0$
- Monotonicity: If $X \\geq Y$, then $\\rho(X) \\geq \\rho(Y)$
- Gain continuity: $\\lim \_{a \\downarrow 0} \\rho(X\+a)=\\rho(X)$
最显然、最简单的一个 satisficing measure 就是 $\\rho(X) = \\mathbb{P}(X \\geq 0)$ 。
Simulation Study I: Portfolio Optimization
文章的第一个 simulation 的例子，是非常经典的投资组合优化。假设历史收益率数据 $(\\hat{z}\_1, \\dots, \\hat{z}\_n)$，则名义的投资组合优化优化是： $$ \begin{aligned} Z_{0}=\max ;& \mathbb{E}{\hat{\mathbb{P}}}\left[\boldsymbol{x}^{\top} \tilde{\boldsymbol{z}}\right] \ \text {s.t. } & \mathbb{C}{\hat{\mathbf{P}}}^{\epsilon}\left[-\boldsymbol{x}^{\top} \tilde{\boldsymbol{z}}\right] \leq \beta \ & \mathbf{1}^{\top} \boldsymbol{x}=1 \ & \boldsymbol{x} \in \mathbb{R}{+}^{N} \end{aligned} $$ 这里 $\\mathbb{C}\_{\\hat{\\mathbf{P}}}^{\\epsilon}$ 表示 CVaR，第一个约束就是 CVaR 约束。 DRO的优化模型是： $$ \begin{aligned} Z{r}=\max & \inf {\mathbb{P} \in \mathcal{B}(r)} \mathbb{E}{\mathbb{P}}\left[\boldsymbol{x}^{\top} \tilde{\boldsymbol{z}}\right] \ \text { s.t. } & \alpha+\frac{1}{\epsilon} \mathbb{E}{\mathbb{P}}\left[\left(-\boldsymbol{x}^{\top} \tilde{\boldsymbol{z}}-\alpha\right)^{+}\right] \leq \beta \quad \forall \mathbb{P} \in \mathcal{B}(r) \ & \boldsymbol{1}^{\top} \boldsymbol{x}=1 \ & \boldsymbol{x} \in \mathbb{R}{+}^{N}, ,\alpha \in \mathbb{R}, \end{aligned} $$ 而 RS (robust satisficing) 的模型是： $$ \begin{array}{rcl} \kappa_{\tau}= & \min & k_{0}+w k_{1} \ & \text { s.t. } & \mathbb{E}{\mathbb{P}}\left[x^{\top} \tilde{\boldsymbol{z}}\right] \geq \tau-k{0} \Delta_{W}(\mathbb{P}, \hat{\mathbb{P}}) \quad \forall \mathbb{P} \in \mathcal{P}{0}(\mathcal{Z}) \ & & \alpha+\displaystyle\frac{1}{\epsilon} \mathbb{E}{\mathbb{P}}\left[\left(-x^{\top} \tilde{\boldsymbol{z}}-\alpha\right)^{+}\right] \leq \beta+k_{1} \Delta_{W}(\mathbb{P}, \hat{\mathbb{P}}) & \forall \mathbb{P} \in \mathcal{P}{0}(\mathcal{Z}) \ & & \mathbf{1}^{\top} x=1, , x \in \mathbb{R}{+}^{N} \end{array} \tag{33} $$ 文章的定理8给出了最终版： $$ \begin{aligned} \min ;& |x|{\infty} \ \text { s.t. } & \frac{1}{S} \sum{s \in[S]} y_{1 s} \geq \tau & \ & y_{1 s} \leq \boldsymbol{x}^{\top} \hat{\boldsymbol{z}}{s} & \forall s \in[S] \ & \alpha+\frac{1}{\epsilon S} \sum{s \in[S]} y_{2 s} \leq \beta & \ & y_{2 s} \geq-\boldsymbol{x}^{\top} \hat{\boldsymbol{z}}{s}-\alpha & \forall s \in[S] \ & y{2 s} \geq 0 & \forall s \in[S] \ & \mathbf{1}^{\top} \boldsymbol{x}=1 & \ & \boldsymbol{x} \in \mathbb{R}_{+}^{N}, \alpha \in \mathbb{R} . & \end{aligned} $$
【未完待续】