When does a given system of linear inequalities form a bounded convex polytope?We know that a Closed Convex Polytope may be regarded as the set of solutions to the system of linear inequalities: a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n ≤ b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n ≤ b 2 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n ≤ b m This can be concisely written as the matrix inequality A x ≤ b, where A is an m × n matrix, x is an n × 1 column vector of variables, and b is an m × 1 column vector of constants.

Question

When does a given system of linear inequalities form a bounded convex polytope?We know that a Closed Convex Polytope may be regarded as the set of solutions to the system of linear inequalities:                                          a                      11                                x                      1                    +                      a                      12                                x                      2                    +          ⋯          +                      a                          1              n                                            x                      n                          ≤                  b                  1                                                          a                      21                                x                      1                    +                      a                      22                                x                      2                    +          ⋯          +                                      a                          2              n                                            x                      n                    ≤                      b                      2                                                    ⋮                                                  a                          m              1                                            x                      1                    +                      a                          m              2                                            x                      2                    +          ⋯          +                      a                          m              n                                            x                      n                          ≤                  b                  m                    This can be concisely written as the matrix inequality   A  x  ≤  b, where   A is an   m  ×  n matrix,   x is an   n  ×  1 column vector of variables, and   b is an   m  ×  1 column vector of constants.

scipionhi · Accepted Answer

You can consider maximizing and minimizing each xi over your feasible set. These are 2n linear programs, each of which can run in polynomial time. If one of these is unbounded, then the polyhedron is unbounded. If all of them are bounded, then the polyhedron lives inside of the product of intervals given by the bounds you found, so it is bounded.Note that linear program solvers can figure out if the max is   ∞, they don&#039;t just run forever; for instance, being unbounded is equivalent to dual being infeasible but the primal being feasible. Both of these can be checked again by a linear program solver, using the reduction in the answer here: how to check whether feasible solutions exist for linear programming.Also, polytope is the standard terminology for a bounded polyhedron, at least in the CS and combinatorics literature.

When does a given system of linear inequalities form a bounded convex polytope? We know that a Clos

Answered question

Answer & Explanation

New Questions in Algebra I