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
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
What did we just do ? Well instead of having strict equalities and inequalities. We “perturb” the zero boundary. If , we say that the inequality constraint is relaxed by an amount of . Likewise, when , the equality constraint is relaxed by an amount of . Also we can see that problem (2) “boils down” to problem (1) when perturbation parameters ‘s and ‘s are set to zero, which makes sense right ? Now if , you can see that we “tighten” the inequality constraint. Similarly, if , the 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 , the optimal value of problem (1). To this extent, let us define the optimal value of problem (2) as
The function tells us how the optimal value of problem (2) as a function of perturbation parameters
Note that for the particular case and , we have that . In the lecture, we prove an inequality that shows us how far is from which is the following
where 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 , i.e. differentiable at and strong duality, we can get a feel on what happens locally around . In the above lecture, we also prove that given the previous two conditions (strong duality and differentiability around ), we have that
The above allows us to quantify how active a constraint is at the optimal point .