4

Suppose $\theta$ is the uncertain vector of parameters and it varies within the interval $\Theta$. We have the following uncertain constraint. $$ \sum_{i} f_i(x,\theta) \ge \sum_{j} g_j(x,\theta) \quad \theta \in \Theta $$

To find the robust counterpart, we should consider the following constraint.

$$ \min_{\theta \in \Theta} \left( \sum_{i} f_i(x,\theta) \right) \ge \max_{\theta \in \Theta} \left( \sum_{j} g_j(x,\theta) \right) $$

I am wondering if it is possible to approximate the above constraint with the following constraint?

$$ \sum_{i} \min_{\theta \in \Theta} \left( f_i(x,\theta) \right) \ge \sum_{j} \max_{\theta \in \Theta} \left( g_j(x,\theta) \right) $$

I think the last constraint is tighter than the former constraint and if it is valid, the former constraint would be valid. I am wondering what this approach is called. Is it called "Safe conservative inner approximation"?

Nike Dattani
  • 1,278
  • 6
  • 32
Amin
  • 2,150
  • 7
  • 20

2 Answers2

3

Yes, it is always mathematically guaranteed that $$\sum_i \min_\theta a_{i, \theta} ≤ \min_\theta \sum_i a_{i, \theta} \tag{1}$$ and that $$\sum_i \max_\theta a_{i, \theta} ≥ \max_\theta \sum_i a_{i, \theta} \tag{2}$$ for any values $a_{i,\theta}$ (including $a_{i, \theta} = f_i(x, \theta)$ or $a_{i, \theta} = g_i(x, \theta)$), least as long as the minima and maxima are all well defined.

Proof of $(1)$: Let $m_i = \min_\theta a_{i,\theta}$. By definition, we have $m_i ≤ a_{i,\theta}$ for all $\theta$. Thus $\sum_i m_i ≤ \sum_i a_{i,\theta}$ for all $\theta$, and thus $\sum_i \min_\theta a_{i, \theta} = \sum_i m_i ≤ \min_\theta \sum_i a_{i,\theta}$, QED. (Inequality $(2)$ can be proven the same way, just by swapping $\max$ for $\min$ and changing the direction of the inequality signs.)

Of course, it could happen that this tighter constraint might not be satisfiable even if if the original robust constraint was (and of course the robust constraint itself might not be satisfiable even if there existed an $x$ that satisfies the original uncertain constraint for all $\theta$) and optimizing with the tighter constraint might yield a less optimal result than using either of the looser constraints. That's the price you pay for simplifying the constraints.

(As for whether there's an established name for the tightened robust constraint, with the minimum / maximum taken componentwise inside the sum, I cannot say — I'm a mathematician, and mostly unfamiliar with OR specific terminology. Sorry.)

Ps. In fact, the inequalities $(1)$ and $(2)$ still hold, and can be proven the same way, even if we generalize them by replacing $\min$ and $\max$ with $\inf$ and $\sup$. While in this general case it's no longer guaranteed that the infimum or supremum is actually attained for any $\theta$, and thus the inequality $m_i ≤ a_{i,\theta}$ might always be strict, the proof still works.

Ilmari Karonen
  • 168
  • 4
  • Thanks for your response. So, although it is possible that there is no solution to the last case, it is possible that there might be a solution to the initial and the second constraint. However, if there is any solution to the last case, there should be definitely a solution for the first two ones although it might not be optimal. If we neglect the optimality of solutions, can we say that the last constraint is an approximation of the formers, and I can solve the problem with the last one? – Amin Jan 29 '23 at 18:58
  • 1
    Yes, any $x$ satisfying the last constraint must necessarily satisfy both of the previous ones. – Ilmari Karonen Jan 29 '23 at 19:08
2

My simple logic says your constraint states that the lowest of the lhs should always be greater than/equal to the highest values possible in the rhs within the given interval. If you take sum then you may have something like this:
$1+2+3 \ge 3+1+1$, one of the constraints being violated

Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11