29-1 Linear-inequality feasibility

Given a set of $m$ linear inequalities on $n$ variables $x_1, x_2, \dots, x_n$, the linear-inequality feasibility problem asks whether there is a setting of the variables that simultaneously satisfies each of the inequalities.

a. Show that if we have an algorithm for linear programming, we can use it to solve a linear-inequality feasibility problem. The number of variables and constraints that you use in the linear-programming problem should be polynomial in $n$ and $m$.

b. Show that if we have an algorithm for the linear-inequality feasibility problem, we can use it to solve a linear-programming problem. The number of variables and linear inequalities that you use in the linear-inequality feasibility problem should be polynomial in $n$ and $m$, the number of variables and constraints in the linear program.

a. We just let the linear inequalities that we need to satisfy be our set of constraints in the linear program. We let our function to maximize just be a constant. The solver for linear programs would fail to detect any feasible solution if the linear constraints were not feasible. If the linear programming solver returns any solution at all, we know that the linear constraints are feasible.

b. Suppose that we are trying to solve the linear program in standard form with some particular $A$, $b$, $c$. That is, we want to maximize $\sum_{j = 1}^n c_jx_j$ subject to $Ax \le b$ and all entries of the $x$ vector are non-negative. Now, consider the dual program, that is, we want to minimize $\sum_{i = 1}^m b_iy_i$ subject to $A^{\text T} y \ge c$ and all the entries in the $y$ vector are nonzero. We know by Corollary 29.9, if $x$ and $y$ are feasible solutions to their respective problems, then, if we have that their objective functions are equal, then, they are both optimal solutions.

We can force their objective functions to be equal. To do this, let $c_k$ be some nonzero entry in the $c$ vector. If there are no nonzero entries, then the function we are trying to optimize is just the zero function, and it is exactly a feasibility question, so we we would be done. Then, we add two linear inequalities to require $x_k = \frac{1}{c_k} \Big(\sum_{i = 1}^m b_iy_i - \sum_{j = 1}^n c_jx_j \Big)$. This will require that whatever values the variables take, their objective functions will be equal. Lastly, we just throw these in with the inequalities we already had. So, the constraints will be:

$$ \begin{aligned} Ax & \le b \\ A^{\text T} y & \ge c \\ x_k & \le \frac{1}{c_k} \Bigg(\sum_{i = 1}^m b_iy_i - \sum_{j = 1}^n c_jx_j \Bigg) \\ x_k & \ge \frac{1}{c_k} \Bigg(\sum_{i = 1}^m b_iy_i - \sum_{j = 1}^n c_jx_j \Bigg) \\ x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m & \ge 0. \end{aligned} $$

We have a number of variables equal to $n + m$ and a number of constraints equal to $2 + 2n + 2m$, so both are polynomial in $n$ and $m$. Also, any assignment of variables which satisfy all of these constraints will be a feasible solution to both the problem and its dual that cause the respective objective functions to take the same value, and so, must be an optimal solution to both the original problem and its dual. This of course assumes that the linear inequality feasibility solver doesn't merely say that the inequalities are satisfiable, but actually returns a satisfying assignment.

Lastly, it is necessary to note that if there is some optimal solution $x$, then, we can obtain an optimal solution for the dual that makes the objective functions equal by theorem 29.10. This ensures that the two constraints we added to force the objectives of the primal and the dual to be equal don't cause us to change the optimal solution to the linear program.