Assume that we have solved a (standard) linear program $$ \text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0, $$ and would like to know how sensitive is the optimal objective value to the fluctuations in $c_0$, $A_0$, $b_0$. For this, we introduce parameterised linear program $$ V(t) = \text{minimize}_{x\in {\mathbb R^n}}\,\, c(t)^Tx, \,\,\,\,\, \text{s.t. } A(t)x \leq b(t), $$ where $c(t)=c_0+tc_1$, $A(t)=A_0+tA_1$, $b(t)=b_0+tb_1$, $t\in[0,1]$ is a parameter, and would like to estimate the right derivative $V(0+)$. A naive approach would be to solve the problem for $t=0$, then for some small $t=\epsilon>0$, and approximate $V(0+)\approx \frac{V(\epsilon)-V(0)}{\epsilon}$. This would require solving the problem twice, and the choice of $\epsilon$ is unclear.

There is a Theorem providing (under some compactness conditions) a direct formula for $V(0+)$ $$ V(0+) = \inf\limits_{x\in X^*(0)} \sup\limits_{\lambda \in \Lambda^*(0)} L_t(x,\lambda,0), $$ where $L_t(x,\lambda,0)$ is the partial derivative in $t$ of the Lagrangian $L(x,\lambda,t)$ at $t=0$, $X^*(0)$ and $\Lambda^*(0)$ are the sets of optimal solutions to the primal and dual problems with $t=0$, respectively. The results of this type are known as Envelope theorems in economic literature, and sensitivity analysis (or perturbation analysis) in mathematics.

If primal and dual problems have unique solutions $x^*$ and $\lambda^*$ respectively, this simplifies to $$ V(0+) = L_t(x^*,\lambda^*,0), $$ and can be used to actually compute $V(0+)$. However, in general $X^*(0)$ is not a singleton, and standard methods like simplex return some $x\in X^*(0)$, but not describe the whole solution set.

So, the question is: can this formula, or any other theoretical result, be used to actually compute $V(0+)$ for practical problems (with hundreds or thousands variables and constraints), with performance better than (or at least comparable to) the naive approach?

  • There is the parametric simplex method which is able to solve linearly perturbed linear programs - this may be helpful here. – Dirk Jun 15 '16 at 13:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.