Inferring inequalities

If \(x\) is at least \(2\) and \(y\) is at least \(3\), it is not hard to convince ourselves that \(x+y\) must be at least \(5\).

More generally, if \(a\), \(b\), \(c\), and \(d\) are real numbers such that \(a \geq b\) and \(c \geq d\), then \(a + c \geq b + d\). We say that \(a + c \geq b + d\) is inferred from \(a \geq b\) and \(c \geq d\). Casually, we also say that "adding" the two inequalities gives \(a + c \geq b + d\).

Note that adding inequalities require that the inequalities to have the same sense; in other words, adding a mixture of \(\leq\)-inequalities and \(\geq\)-inequalities is not allowed for obvious reasons. However, adding a mixture of equalities and inequalities with the same sense is valid. For example, if \(x\) and \(y\) are real numbers satisfying \begin{align*} x - 2y & \geq 5 \\ 3x + y & = 7, \end{align*} then \(x\) and \(y\) must also satisfy \(4x - y \geq 12\). Going one step further, we can add scalar multiples of inequalities to obtain new inequalities under appropriate conditions. For example, if we have \[a\geq b, c \leq d, \alpha \geq 0, \beta \leq 0,\] then \[\alpha a + \beta c \geq \alpha b + \beta d.\]

In general, suppose that \(\mathbf{x} \in \mathbb{R}^n\) satisfies the system \begin{align} \mathbf{P} \mathbf{x} & \geq \mathbf{p} \\ \mathbf{Q} \mathbf{x} & \leq \mathbf{q} \\ \mathbf{R} \mathbf{x} & = \mathbf{r} \end{align} where \(\mathbf{P} \in \mathbb{R}^{m \times n}\), \(\mathbf{p} \in \mathbb{R}^m\), \(\mathbf{Q} \in \mathbb{R}^{m' \times n}\), \(\mathbf{q} \in \mathbb{R}^{m'}\), \(\mathbf{R} \in \mathbb{R}^{\bar{m} \times n}\), \(\mathbf{r} \in \mathbb{R}^{\bar{m}}\) for some nonnegative integers \(m, m', \bar{m}\). If \(\mathbf{f} \in \mathbb{R}^m\) with \(\mathbf{f} \geq \mathbf{0}\), \(\mathbf{g} \in \mathbb{R}^{m'}\) with \(\mathbf{g} \leq \mathbf{0}\), and \(\mathbf{h} \in \mathbb{R}^{\bar{m}}\), then \(\mathbf{x}\) also satisfies \[\mathbf{c}^\mathsf{T} \mathbf{x} \geq \gamma\] where \(\mathbf{c} = \mathbf{f}^\mathsf{T}\mathbf{P}+ \mathbf{g}^\mathsf{T} \mathbf{Q} +\mathbf{h}^\mathsf{T} \mathbf{R}\) and \(\gamma = \mathbf{f}^\mathsf{T}\mathbf{p}+ \mathbf{g}^\mathsf{T} \mathbf{q} +\mathbf{h}^\mathsf{T} \mathbf{r}\). We say that the inequality \(\mathbf{c}^\mathsf{T} \mathbf{x} \geq \gamma\) is inferred from the system above. To simplify the language for describing linear constraint inference, we often assign labels to the constraints and write linear combinations of them. For example, say we have the system \begin{align*} x_1 + 2x_2 & \geq 2 && (\text{A}) \\ -x_1 + x_2 & \leq 1 && (\text{B}) \\ 3x_1 - x_2 & = -1. && (\text{C}) \end{align*} Then \(2\times (\text{A}) +(-1)\times (\text{B}) + (\text{C})\) refers to the inequality \(6x_1+2x_2 \geq 2\) since \(2(x_1+2x_2)+(-1)(-x_1+x_2)+(3x_1 - x_2)\) gives \(6x_1 + 2x_2\) and \(2(2) + (-1)(1) + (-1)\) is \(2\).

Worked examples

1. Determine the maximum value of \(\mu\) such that \(x + y \geq \mu\) can be inferred from the system \begin{align*} 2x + y & \geq 2 \\ x + 3y & \geq 1 \\ 3x + 2y & \geq 6 \end{align*}

   To infer \(x + y \geq \mu\) from the given system, we need \(\alpha \geq 0\), \(\beta \geq 0\), and \(\gamma \geq 0\) such that \begin{align*} 2\alpha + \beta + 3\gamma & = 1\\ \alpha + 3\beta + 2\gamma & = 1\\ 2\alpha + \beta + 6\gamma & = \mu. \end{align*} Solving gives \(\begin{bmatrix} \alpha \\ \beta \\ \gamma\end{bmatrix} = \begin{bmatrix} \frac{13}{15} - \frac{7}{15} \mu \\ \frac{4}{15}-\frac{1}{15} \mu \\ -\frac{1}{3} + \frac{1}{3}\mu\end{bmatrix}\). The maximum value \(\mu\) can take so that this tuple has only nonnegative entries is \(\frac{13}{7}\).

2. Show that the inequality \(x + 2y \geq 3\) can be inferred from the system \begin{align*} 2x + y & \geq 2 \\ x + 5y & \geq 7 \\ -x + y & = 1 \\ \end{align*} in infinitely many ways.

   We first label the constraints: \begin{align*} 2x + y & \geq 2 & (\text{A}) \\ x + 5y & \geq 7 & (\text{B}) \\ -x + y & = 1. & (\text{C}) \end{align*} We want to find multipliers \(\alpha, \beta\ \geq 0\) and \(\gamma\) such that \(\alpha\times (\text{A})+\beta\times (\text{A})+\gamma \times (\text{C})\) is \(x + 2y \geq 3\). Simplifying \(\alpha\times (\text{A})+\beta\times (\text{A})+\gamma \times (\text{C})\) gives \[ (2\alpha+\beta-\gamma)x + (\alpha+5\beta+\gamma)y \geq 2\alpha + 7\beta + \gamma.\] Comparing this with \(x + 2y \geq 3\) coefficient by coefficient, we obtain the system \begin{align*} 2\alpha+\beta-\gamma & = 1 \\ \alpha+5\beta+\gamma & = 2 \\ 2\alpha + 7\beta + \gamma & = 3 \end{align*} Solving this system gives \(\begin{bmatrix} \alpha \\ \beta \\ \gamma \end{bmatrix} = \begin{bmatrix} \frac{1}{3}+\frac{2}{3}t \\ \frac{1}{3} - \frac{1}{3} t\\ t \end{bmatrix}\) where \(t \in \mathbb{R}\). Since we need \(\alpha, \beta \geq 0\), we must have \(-\frac{1}{2} \leq t \leq 1\). For every \(t\) in this range, which contains infinitely values, we obain a way to infer \(x+2y \geq 3\) from the given system.

   For example, when \(t = \frac{1}{2}\), we obtain \(\begin{bmatrix} \alpha \\ \beta \\ \gamma \end{bmatrix} = \begin{bmatrix} \frac{2}{3} \\ \frac{1}{6} \\ \frac{1}{2}\end{bmatrix}\).

3. Determine the optimal value of \[ \begin{array}{rl} \text{Minimize} & x + y \\ \text{Subject to} & 2x + y \geq 4 \\ & x + 3y \geq 1. \end{array} \]

   This problem can certainly be solved using graphical method. Instead, we solve it by determining the minimum value \(z\) so that \(x+y=z\) defines a line that has a nonempty intersection with the feasible region. Setting \(x=z-y\) and substituting for \(x\) in the inequalities, we obtain: \begin{eqnarray*} 2(z-y) + y \geq 4 \\ (z-y) + 3y \geq 1, \end{eqnarray*} or equivalently, \begin{eqnarray*} z \geq 2+\frac{1}{2}y \\ z \geq 1-2y, \end{eqnarray*} Thus, the minimum value for \(z\) is \(\min \{ 2+\frac{1}{2}y, 1-2y\}\), which occurs at \(y = -\frac{2}{5}\). Hence, the optimal value is \(\frac{9}{5}\).

   We can verify our work by doing the following. If our calculations above are correct, then an optimal solution is given by \(x = \frac{11}{5}\), \(y = -\frac{2}{5}\) since \(x = z - y\). It is easy to check that this satisfies both inequalities and therefore is a feasible solution.

   Now, taking \(\frac{2}{5}\) times the first inequality and \(\frac{1}{5}\) times the second inequality, we can infer the inequality \(x+y \geq \frac{9}{5}\). The left-hand side of this inequality is precisely the objective function. Hence, no feasible solution can have objective function value less than \(\frac{9}{5}\). But \(x = \frac{11}{5}\), \(y = -\frac{2}{5}\) is a feasible solution with objective function value equal to \(\frac{9}{5}\). As a result, it must be an optimal solution.

   Remark. We have not yet discussed how to obtain the multipliers \(\frac{2}{5}\) and \(\frac{1}{5}\) for inferring the inequality \(x+y \geq \frac{9}{5}\). This is an issue that will be taken up later. In the meantime, think about how one could have obtained these multipliers for this particular problem.