DRO-1 Introduction to DRO
关于分布式鲁棒优化的学习note，用的是沙田苏文藻老师的notes。
Introduction : Optimization Under Uncertainty
Traditional Approach : Deterministic Problem
Given optimization problem
$$
\begin{array}{ll}
\inf _{x \in C} f(x) & f: \mathbb{R}^n \rightarrow \mathbb{R} \\
& C \subseteq \mathbb{R}^n
\end{array}
$$
Typically, data are deterministic. However, in reality, data are often uncertain.
Example:
Consider manufacturing problem:
$c_j=$ cost of $j^{\text {th }}$ activity
$a_{i j}=$ amount of $i$ ch commodity per unit of $j^{t h}$ activity
$b_i=$ output requirement of $i^{\text {th }}$ commodity
$$
\begin{aligned}
\min && \quad & c^{\top} x \\
\text { s.t. } && A x&=b \\
&& x &\geq 0
\end{aligned}
$$
But , $c,A$ can be uncertain !
Q: How to incoporate such data uncertainty into the optimization model?
Idea: Consider the uncertainty as a pertubation vector $\xi \in \mathbb{R}^{\ell}$
$$
\begin{aligned}
\min&& \quad c(\xi)^{\top}& x \\
\text { s.t. }&& A(\xi) x&=b \\
&& x &\geq 0
\end{aligned}
$$
Different Points of View
1. Stochastic Optimization
假设pertubation vector $\xi$ 服从一个特定的分布
$$
\begin{aligned}
\min&& \mathbb{E}_{\xi \sim \mathbb{P}}&\left[c(\xi)^{\top} x\right]\\
\text { s.t. }&& \operatorname{Pr}_\xi[A(\xi) x=b(\xi)] &\geqslant 1-\delta\\
&& x &\geqslant 0
\end{aligned}
$$
- Contraint 变为chance constraint ，with confidence level $1-\delta$
Difficulties:
- Hard to evaluate $\mathbb{E}_{\xi \sim \mathbb{P}}$ or $\operatorname{Pr}_\xi$ , high dimensional calculation
- Usually the distribution is unknown
2. Robust Optimization
与随机优化不同，鲁棒优化不假设一个具体的分布，而是假设一个“可行空间”
$\xi$ belongs to a (bounded) set $\mathcal{U} \subseteq \mathbb{R}^l$ (uncertainty set)
$$
\begin{align*}
\min \quad & t \\
\text{s.t.} \quad & c^{\top}(\xi) x \leqslant t \quad && \forall \xi \in \mathcal{U} \\
& A(\xi) x = b(\xi) \quad && \forall \xi \in \mathcal{U} \\
& x \geqslant 0
\end{align*}
$$
- Thus, a solution $\left(x^*, t^*\right)$ is robust against all possible $\xi \in \mathcal{U}$.
Difficulties:
- How to chosse $\mathcal{U}$?
- The solution usually too conservative.
3. Distributional Robust Optimization
Somewhere in-between! 即结合了一些随机优化的性质又有robust optimization的鲁棒性
$\xi$ : random vector with distribution$\mathbb{P}^*$ , $\mathbb{P}^*$ not exactly known, but some information about it is known.
Consider an uncertainty set of distributions $\mathscr{P}$ :
E.g. :
$$
\begin{align*}
&\min_x \max_{\mathbb{P} \in \mathscr{P}} \mathbb{E}_{\xi \sim \mathbb{P}}[c^{\top}(\xi) x] \\
&\operatorname{inf}_{\mathbb{P} \in \mathscr{P}} \operatorname{Pr}_{\xi \sim \mathbb{P}}[A(\xi) x=b(\xi)] \geqslant 1-\delta
\end{align*}
$$
Difficulties:
- How to chosse $\mathscr{P}$ ?
- Can the resulting problem be solved ?
Example: Robust Linear Constraint
考虑一个简单的robust constrain的例子，体验 “robust” 如何影响并改变constraint
RLC：
$a^{\top} x \leq b$
$\forall(a, b)=\underbrace{\left(a^0, b_0\right)}_{\substack{\text { nominal } \\ \text { value }}}+\underbrace{\sum_{j=1}^l \xi_j\left(a^j, b_j\right)}_{\text {perturbation }} ; \qquad \xi \in \mathcal{U}\subseteq \mathbb{R}^l$
where $a^j, b_j(j=0,1, \cdots, l)$ are given.
Choice 1 : $\mathcal{U} = $ normal ball
$U=\left\{y \in \mathbb{R}^{\ell},\|y\|_{\infty} \leq 1\right\}$
$$
\begin{aligned}
(R L C) &\Leftrightarrow \quad\left(a^0\right)^{\top} x+\sum_{j=1}^{\ell} \xi_j\left(a^j\right)^{\top} x \leqslant b_0+\sum_{j=1}^{\ell} \xi_j b_j \quad \forall\|\xi\|_{\infty} \leq 1\\
& \Leftrightarrow \quad \sum_{j=1}^l \xi_j\left(\left(a^j\right)^{\top} x-b_j\right) \leqslant b_0-\left(a^0\right)^{\top} x \quad \forall\|\xi\|_{\infty} \leq 1 \\
& \Leftrightarrow \quad \max _{\xi:\|\xi\|_{\infty} \leq 1} \sum_{j=1}^l \xi_j\left(\left(a^j\right)^{\top} x-b_j\right) \leqslant b_0-\left(a^0\right)^{\top} x \\
& \Leftrightarrow \quad \sum_{j=1}^l\left|\left(a^j\right)^{\top} x-b_j\right| \leq b_0-\left(a^0\right)^{\top} x
\end{aligned}
$$
This can be converted into a finite system linear inequalities
Choice 2 : $\mathcal{U} = \left\{y<\mathbb{R}^l:\|y\|_2 \leqslant 1\right\}$
$$
\begin{aligned}
& (R L C) \Leftrightarrow \quad \max _{\xi:\|\xi\|_2 \leq 1} \underbrace{\xi_j\left(\left(a^j\right)^{\top} x-b_j\right)}_{u^{\top} \xi \quad u_j=\left(a^j\right)^{\top} x-b_j} \leqslant b_0-\left(a^0\right)^{\top} x \\
& \leqslant\|u\|_2 \cdot\|\xi\|_2 \quad \text { (Cauchy-Schwarz) } \\
& \leqslant\|u\|_2 \quad\left(\|\xi\|_2 \leqslant 1\right) \\
& \Leftrightarrow \quad\left[\sum_{j=1}^l\left(\left(a^j\right)^{\top} x-b_j\right)^2\right]^{1 / 2} \leqslant b_0-\left(a^0\right)^{\top} x \\
&
\end{aligned}
$$
So far, we seem to be lucky in that $\max _{\xi \in u}[\cdots]$ has a closed form. In general, we do not expect this
Choice 3 $U=\left\{y \in \mathbb{R}^l: P y \leqslant q\right\}$ (a polyhedron)
$$
\begin{aligned}
(R L C) & \Leftrightarrow \max _{\xi: P \xi \leq q} \sum_{j=1}^l \xi_j\left(\left(a^j\right)^{\top} x-b_j\right) \leq b_0-\left( a^0\right)^{\top} x \\
& \Leftrightarrow \quad ? ? ?
\end{aligned}
$$
Perhaps LP duality can be applied here.
Summary
Lessons learned
- Complexity of the robust constraint depends on $\mathcal U$
- duality theory is helpful in reformulating robust constraints into finite system of constraints
- even for robust linear constraints, their reformulations may not be linear $\rightarrow$ need nonlinear optimization techniques