# LPs having a 'stable' objective value wrt changes in the constraint right-hand sides

I have a problem as:

\begin{align} \begin{array}{cl} \underset{x \in \mathbb{R}^n_+}{\min} & c^\top x \\ \mathrm{s.t.} & Ax \leq \mathbf{1} \cdot b , \end{array} \end{align} where $$A \in \mathbb{R}^{m \times n}$$ is an arbitrary data matrix and all the constraints have $$b > 0$$ on the right-hand side.

I am looking for the terminology (and in a broader sense, the relevant literature) studying "if we increase $$b$$ arbitrarily small, we can also bound the change in the optimal objective value with an arbitrarily small change." Or more formally maybe:

Take $$b_1 > 0$$, and denote $$OPT_1$$ as the optimal objective value when the above problem has $$b_1$$ on the right-hand side of the constraint. For any $$\epsilon > 0$$, there exists some $$b_2 < b_1$$, such that $$OPT_2 - OPT_1 < \epsilon$$, where $$b_2$$ is a function of $$\epsilon$$ and $$OPT_2$$ denotes the optimal objective value of the above LP when the right-hand side is $$b_2$$.

My main goal is to analyze this for a continuous LP where the variable becomes a Borel measure, the objective becomes $$\int_{\mathbb z \in R} c(z) \mathrm{d}x(z)$$ and the $$i$$-th constraint becomes $$\int_{\mathbb R} a_i(z)\mathrm{d}x(z) \leq b$$ where $$a_i$$ are also Borel functions. I am hoping the answer for the simpler LP example above will let me generalize to this case.

• Sensitivity analysis Jul 29, 2021 at 18:12
• The bound you want comes from LP duality theory.
– prubin
Jul 29, 2021 at 18:17
• @user3680510 I don’t think this is sensitivity analysis. Sensitivity analysis tells us the change in the objective with a unit change in each right hand side. What if we cannot “bound” this by changing the right hand side of every constraint at once? Jul 29, 2021 at 23:32

"if we increase $$b$$ arbitrarily small, we can also bound the change in the optimal objective value with an arbitrarily small change."
This property is called "the objective being lipschitz continuous with regard to $$b$$". In my intuition this should hold all LPs that have a non empty simplex. If you push $$b$$ so that the simplex becomes empty you can't reason about the meaning of the objective.
Take $$b_1 > 0$$, and denote $$OPT_1$$ as the optimal objective value when the above problem has $$b_1$$ on the right-hand side of the constraint. For any $$\epsilon > 0$$, there exists some $$b_2 < b_1$$, such that $$OPT_2 - OPT_1 < \epsilon$$, where $$b_2$$ is a function of $$\epsilon$$ and $$OPT_2$$ denotes the optimal objective value of the above LP when the right-hand side is $$b_2$$.
This property is called "the objective being continuous with regard to $$b$$" and is implied by the former under the same concerns of the simplex being non empty.