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

1. Complexity of the robust constraint depends on $\mathcal U$
2. duality theory is helpful in reformulating robust constraints into finite system of constraints
3. even for robust linear constraints, their reformulations may not be linear $\rightarrow$ need nonlinear optimization techniques