Minimal set of inequalitiesI have a set of m linear inequalities in Rn, of the form A x ≤ bThese are automatically generated from the specification of my problem. Many of them could be removed because they are implied by the others.I would like to find the minimal set of inequalities, A ′ x ≤ b ′ such that a solution to the first problem is also a solution to the second, and vice versa.

Question

Minimal set of inequalitiesI have a set of m linear inequalities in Rn, of the form  A  x  ≤  bThese are automatically generated from the specification of my problem. Many of them could be removed because they are implied by the others.I would like to find the minimal set of inequalities,      A    ′    x  ≤      b    ′  such that a solution to the first problem is also a solution to the second, and vice versa.

Patricia Curry · Accepted Answer

Using Farkas&#039; lemma, an halfspace   {  x  ∣      a    ′    x  ≤      b    ′    } contains the polyhedron   P  =  {  x  |  A  x  ≤  b  } if and only if there exists   λ  ∈        R    m   with   λ  ≥  0 (understood component-wise) such that:                              a          ′                                    =                  λ          T                A                                      b          ′                                    ≥                  λ          T                b            The set                    N        =        {        (                  a          ′                ,                  b          ′                )              |        ∃        λ        ≥        0        ,                  a          ′                =                  λ          T                A        ,                  b          ′                ≥                  λ          T                b        }            is called the polar of the polyhedron   P. The facets of   P are given by the extreme rays of   N.An inequality       a    i    x  ≤      b    i   will be non-redundant (i.e is not implied by the other) if and only if it is an extreme ray of   N.So all you need to do is to compute the conic hull of the m points   (      a    1    ,      b    1    )  ,  .  .  .  ,  (      a    m    ,      b    m    ) which is more or less equivalent (some gap to fill here) to computing a convex hull.

Minimal set of inequalities I have a set of m linear inequalities in Rn, of the form A x

Answered question

Answer & Explanation

New Questions in Algebra I