6-optimizaition-under-uncertainty

Firstly consider that in the previous (conic) linear programming discussion, \[ \tag{Problem} \begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & \hat a_i^T x \le \hat b_i, i=1,2,\dots,m \end{aligned} \] The coefficients \(\hat a_i, \hat b, \hat c\) are given data. They correspond to the measurements in the real world. But it is highly likely that these measurements are not 100% accurate. How do we take into account these uncertainties?

Without loss of generality, we may assume that \(\hat c\) is deterministic, since the above is equivalent to \[ \begin{aligned} \min \quad & t \\ \text{s.t.} \quad & \hat c^T x \le t \\ & \hat a_i^T x \le \hat b_i, i=1,2,\dots,m \end{aligned} \] In this new problem, we bring all uncertainties into the constraint and the coefficient \([0,\dots,0,1]\) for the variable \([x^T, t]\) is deterministic.

The problem remains how to handle the uncertainty in the constraint in \(\text{(Problem)}\). There are several viable methods:

• Stochastic optimization

  Stochastic optimization assumes that data follow a probability distribution \(\mathbb{P}\) (unknown). The constraint becomes \[ \Pr(\hat a_i^T x \le \hat b_i) \ge 1 - \delta \] for some \(\delta > 0\). This method is non-trivial, due to the integral of multi-dimensional probability distribution function.

• Robust optimization

  The assumption is that data is drawn from a ambiguity set \(\mathcal{U}\). We require that \[ \hat a_i^T x \le \hat b_i, \forall i=1,2,\dots, \forall (\hat a_i, \hat b_i) \in \mathcal{U} \]

• Distributionally-robust optimization

  This is kind of the combination of the above two methods. The assumption is that data follow a probability distribution \(\mathbb{P}\), which in turn belongs to some ambiguity set \(\mathcal{U}\). The constraint becomes \[ \inf_{\mathbb{P} \in \mathcal{U}} \Pr(\hat a_i^T x \le \hat b_i) \ge 1 - \delta, \forall i=1,2,\dots \] for some \(\delta > 0\).

Robust Linear Programming

Consider the problem \[ \label{rp} \tag{R} \begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & \underbrace{[\hat \alpha_i^T, \hat b_i]}_{\hat a_i^T} \underbrace{[x^T, x']^T}_z \le 0, \\ & \quad \hat a_i \in \mathcal{U}_i, i=1,\dots,m \\ & \underbrace{x'}_{z_{n+1}} = -1 \end{aligned} \] where \(\mathcal{U}_i \triangleq \{ y \in \R^{n+1}: y = u_i + B_i v, B_i \in \mathcal{S}_{++}^{n+1}, \|v\| \le 1 \}\) is an ellipsoid.

Note that \(\eqref{rp}\) is not LP actually, as it may contain infinitely-many linear constraints. This is usually hard. Just imagine its dual problem. For a primal that has infinitely-many constraints, its dual has infinitely-many variables.

The key question now is how to tackle \(\hat a_i^T z \le 0, \forall \hat a_i \in \mathcal{U}_i\) (ignoring \(z_{n+1} = -1\) for now). In essence, it is equivalent to \[ \begin{aligned} \left[ \sup_{\hat a_i \in \mathcal{U}_i} \hat a_i^T z \right] &\le 0 \iff \\ \left[ \sup_{\|v\| \le 1} (u_i + B_i v)^T z \right] &\le 0 \iff \\ u_i^T z + \left[ \sup_{\|v\| \le 1} v^T B_i z \right] &\le 0 \iff \\ y_i^T z + \|B_i z\|_2 &\le 0 \end{aligned} \] This is exactly an SOCP constraint.