Sensitivity analysis for decision vectors in convex programming

Question

Can we perform sensitivity analysis on the decision variables for the perturbed right-hand side of the constraints in a convex/nonlinear program? I know a basic result regarding the sensitivity of the optimal solution but are there any techniques/references to do the same for the decision variables?

Answer 1

Suppose that $F: R^{n} \rightarrow R^{n}$, $F(x)=b$, and $F$ is differentiable at $x$ with non-singular Jacobian $J(x)$. Then to first order, we can use the Jacobian to find a change $\Delta x$ due to a small change $\Delta b$.

$F(x+\Delta x)=b+\Delta b$.

$F(x)+J(x)\Delta x=b+\Delta b$.

$\Delta x=J(x)^{-1} \Delta b$.

This is exact only in the limit as $\Delta b$ goes to 0, but it tells you that the partial derivatives of $x_{i}$ with respect to $b_{j}$ are given by

$\frac{\partial x_{i} }{\partial b_{j}}=(J(x)^{-1})_{i,j}$.

Now suppose that you've got a smooth optimization problem

$\min f(x)$

subject to

$h_{i}(x)=b_{i}$, $i=1, 2, \ldots, m$

and that you have found an optimal solution $x^{*}$ and also solved the KKT conditions. The KKT conditions are of the form

$K(x^{*},\lambda^{*})=0$

including the specific constraint equations

$h_{i}(x^{*})-b_{i}=0$, $i=1, 2, \ldots, m$

and the Lagrange multiplier constraints

$\nabla f(x^{*}) + \sum_{i=1}^{m} \lambda_{i}^{*} \nabla h_{i}(x^{*})=0$.

You can now find the Jacobian of $K(x^{*},\lambda^{*})$ and invert it to get the sensitivity of $x^{*}$ with respect to changes in $b_{i}$.

Note that in order to do this you'll have to look at the second derivatives of $f(x)$ and the $h_{i}(x)$ since $K$ already involves the first derivatives.

You can easily extend this to problems with inequality constraints.

A good book that discusses this is:

Bonnans, J. Frédéric, and Alexander Shapiro. Perturbation Analysis of Optimization Problems. Springer, 2013.