1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thank you so much! A follow-up question: is it possible to do the same thing but instead of changing the right-hand side of the constraint, we change some parameters in the objective function? (we still look at the effect on the optimal decision vector. $\endgroup$
    – Krypt
    Apr 6, 2023 at 23:02
  • 1
    $\begingroup$ Consider how those changes in the objective function change $\nabla f(x)$ in the KKT conditions. $\endgroup$ Apr 7, 2023 at 3:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.