1
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Sensitivity analysis $\endgroup$ Jul 29, 2021 at 18:12
  • 1
    $\begingroup$ The bound you want comes from LP duality theory. $\endgroup$
    – prubin
    Jul 29, 2021 at 18:17
  • $\begingroup$ @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? $\endgroup$ Jul 29, 2021 at 23:32

1 Answer 1

2
$\begingroup$

The property that some infinitesimal change in one of the constraints impacts the objective is called "a constraint being active" or "a constraint being in conflict with the objective".

"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.

$\endgroup$

Your Answer

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

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