【OR-notes】敏感度分析

Perturbation & Sensitivity analysis

$$\begin{array}{rlr}& \min & f_0(x)\\ & s.t.& f_i(x)\le 0,i=1,2,\dots ,m\\ & & h_i(x)=0,i=1,2,\dots ,p\end{array}$$

Add perturbation:
$$\begin{array}{rlr}& \min & f_0(x)\\ & s.t.& f_i(x)\le u_i,i=1,\dots ,m\\ & & h_i(x)=v_i,i=1,2,\dots ,p\end{array}$$
The dual problem is:
$$\begin{array}{rlr}& \max & g(\lambda ,\nu )-u^{\prime }\lambda -v^{\prime }\nu \\ & s.t.& \lambda \ge 0\end{array}$$
$x$ is primal variable, $u,v$ are parameters, $p^{\ast }(u,v)$ is the optimal value as a function of $u,v$.

global analysis

Assuming that strong duality hold for $u=0,v=0$, ${\lambda }^{\ast },{\nu }^{\ast }$ are dual optimal for unperturbed problem, that is
$$p^{\ast }(u,v)\ge g({\lambda }^{\ast },{\nu }^{\ast })-u^{\prime }{\lambda }^{\ast }-v^{\prime }{\nu }^{\ast }=p^{\ast }(0,0)-u^{\prime }{\lambda }^{\ast }-v^{\prime }{\nu }^{\ast }$$
Sensitivity analysis

1. If $\lambda$ is large, $u_i<0$, $p^{\ast }$ increase greatly.
2. If $\lambda$ is small, $u_i>0$, $p^{\ast }$ does not decrease too much.
3. If ${\nu }_i$ is large, $v_i<0$ or If ${\nu }_i<0$ is large, $v_i>0$, $p^{\ast }$ increase greatly.
4. If ${\nu }_i^{\ast }>0$ small and $v_i>0$ or If ${\nu }_i^{\ast }<0$ small and $v_i<0$, $p^{\ast }$ does not decrease too much.

local sensitivity

If $p^{\ast }(u,v)$ is derivative at $(0,0)$, that is,
$$\begin{array}{rl}& {\lambda }_i^{\ast }=\frac{\partial p^{\ast }(0,0)}{\partial u_i}\\ & {\nu }_i^{\ast }=\frac{\partial p^{\ast }(0,0)}{\partial v_i}\end{array}$$