Perturbation & Sensitivity Analysis

In this lecture, we talk about Perturbation and Sensitivity Analysis. But what does that mean ? Well, consider our good old looking optimization problem that looks like this

(1) $\begin{equation*}\begin{aligned}& \underset{x}{\text{minimize}}& & f_0(x) \\& \text{subject to}& & f_i(x) \leq 0, \; i = 1, \ldots, m \\& & & h_i(x) = 0, \; i = 1, \ldots, p\end{aligned}\end{equation*}$

One way to tell how the above problem reacts to perturbation is to actually perturb it and check how its optimal value behaves with perturbation parameters. To this end, consider the following perturbed problem

(2) $\begin{equation*}\begin{aligned}& \underset{x}{\text{minimize}}& & f_0(x) \\& \text{subject to}& & f_i(x) \leq u_i, \; i = 1, \ldots, m \\& & & h_i(x) = v_i, \; i = 1, \ldots, p\end{aligned}\end{equation*}$

What did we just do ? Well instead of having strict equalities and inequalities. We “perturb” the zero boundary. If $u_i > 0$ , we say that the $i^{th}$ inequality constraint is relaxed by an amount of $u_i$ . Likewise, when $v_i > 0$ , the $i^{th}$ equality constraint is relaxed by an amount of $v_i$ . Also we can see that problem (2) “boils down” to problem (1) when perturbation parameters $u_i$ ‘s and $v_i$ ‘s are set to zero, which makes sense right ? Now if $u_i < 0$ , you can see that we “tighten” the $i^{th}$ inequality constraint. Similarly, if $v_i < 0$ , the $i^{th}$ equality constraint is said to be “tightened”. Going back to our main concern that is “check how its optimal value behaves with perturbation parameters”, we have to quantify that perturbation on $p^*$ , the optimal value of problem (1). To this extent, let us define the optimal value of problem (2) as

(3) $\begin{equation*} \begin{split} p^*(u,v)=\inf\lbracef_0(x) \vert\exists x \in \mathcal{D}, f_i(x) &\leq u_i, i = 1 \ldots m; \\h_i(x) &= v_i , i = 1 \ldots p \rbrace\end{split}\end{equation*}$

The function $p^*(u,v)$ tells us how the optimal value of problem (2) as a function of perturbation parameters

(4) $\begin{align*} u &= \begin{bmatrix} u_1 & \ldots & u_m \end{bmatrix} \\ v &= \begin{bmatrix} v_1 & \ldots & v_p \end{bmatrix} \end{align*}$

Note that for the particular case $u = 0$ and $v = 0$ , we have that $p^*(0,0) = p^$ . In the lecture, we prove an inequality that shows us how far $p^*(u,v)$ is from $p^*$ which is the following

(5) $\begin{equation*} p^*(u,v) \geq p^* - u^T \lambda^* - v^T \nu^*\end{equation*}$

where $(\lambda^*,\nu^*)$ are the optimal dual Lagrangian multipliers. The above also provides a global view on how far we are from the optimal unperturbed problem in terms of the optimal dual Lagrangian multipliers. Now, if we impose extra properties on $p^*(u,v)$ , i.e. differentiable at $(u,v) = (0,0)$ and strong duality, we can get a feel on what happens locally around $(u,v) = (0,0)$ . In the above lecture, we also prove that given the previous two conditions (strong duality and differentiability around $(u,v) = (0,0)$ ), we have that

(6) $\begin{align*} \lambda_i^* &= - \frac{\partial p^*(0,0)}{\partial u_i} \\\nu_i^* &= - \frac{\partial p^*(0,0)}{\partial v_i} \end{align*}$