0
$\begingroup$

Given a feasibility problem with both inequality and equality constraints, I'm interested in the sensitivity of the bounds of the region to changes in the constraints. To help with answering the rather general question, I'm interested in particular for linear equality constraints with perturbations for

  • Linear
  • Non-linear

inequality constraints. As a sample problem, consider

$$ \begin{align} min \qquad 1 \\ \text{subject to} \hspace{1ex} b-\epsilon \leq \hspace{1ex}&a^{T}x \leq b + \epsilon \\ \mathbf{1}^{T}x &= 1 \end{align} $$

How do the limits of each co-ordinate in the feasible region $x_{i}$ vary as a function of $\epsilon$? Is there a common name for this problem?

$\endgroup$
2
$\begingroup$

I assume that you're interested in

$b-\epsilon \leq a^{T}x \leq b +\epsilon$

rather than

$b+\epsilon \leq a^{T}x \leq b +\epsilon$

right?

If you're interested in more complicated parameterizations of the constraints, what would those look like?

In this linear case, for any fixed $\epsilon$ (including 0), you can minimize (or maximize) $x_{i}$ subject to the constraints.

$a^{T}x \geq b-\epsilon$

$a^{T}x \leq b+\epsilon$

$1^{T}x=1$

This is a linear programming problem. Once you have an optimal solution, you can find the sensitivity of the optimal value to changes in the right-hand sides of the constraints from the dual solution. This is called "sensitivity analysis" in linear programming. You can also use "parametric linear programming" techniques to find the optimal value as a function of $\epsilon$.

Parametric linear programming techniques are discussed in many textbooks on linear programming. I believe for example that you'll find it in Vanderbei's text (I'm not in the office at the moment so I can't immediately verify this.)

For convex nonlinear problems you can also use the Lagrangian dual to perform sensitivity analysis. There are also parametric nonlinear programming techniques that have been discussed in a few papers, but this isn't very well developed.

$\endgroup$
  • $\begingroup$ Thanks. I'm wondering if the bounds can be expressed analytically atleast for the linear problem. In this case, the extreme $x_{i}$ occur only on the hyperplane intersections. $\endgroup$ – gpavanb Jan 21 '17 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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