Minimum relevant variables in linear system: Difference between revisions

Revision as of 10:59, 7 January 2019

Revision as of 11:11, 7 January 2019

Line 1:

The '''Min-RVLS''' problem (MINimum Relevant Variables in Linear System''' ('''Min-RVLS''') is a problem in [[mathematical optimization]]. Given a [[linear program]], it is required to find a feasible solution in which the number of non-zero variables is as small as possible.

The problem is known to be [[NP-hardness|NP-hard]] and even hard to approximate.

Line 10:

* An ''m''-by-1 vector ''b''.

The linear system is given by: ''A x'' ''R'' ''b.'' It is assumed to be feasible (i.e., satisfied by at least one ''x''). Depending on R, there are four different variants of this system: ''A x = b, A x ≥ b, A x > b, A x ≠ b''.

The goal is to find an ''n''-by-1 vector ''x'' that satisfies the system ''A x'' ''R'' ''b'', and subject to that, contains as few as possible nonzero elements.

Line 18:

== Applications ==

The Min-RVLS problem is important in [[machine learning]] and [[linear discriminant analysis]]. Given a set of positive and negative examples, it is required to minimize the number of features that are required to correctly classify them.<ref>{{Cite journal|last=Koehler|first=Gary J.|date=1991-11-01|title=Linear Discriminant Functions Determined by Genetic Search|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.4.345|journal=ORSA Journal on Computing|volume=3|issue=4|pages=345–357|doi=10.1287/ijoc.3.4.345|issn=0899-1499}}</ref> The problem is known as the [[minimum feature set problem]].<ref>{{Cite journal|last=Van Horn|first=Kevin S.|last2=Martinez|first2=Tony R.|date=1994-03-01|title=The Minimum Feature Set Problem|url=http://dx.doi.org/10.1016/0893-6080(94)90082-5|journal=Neural Netw.|volume=7|issue=3|pages=491–494|doi=10.1016/0893-6080(94)90082-5|issn=0893-6080|via=}}</ref>

== Related problems ==

In '''MINimum Unsatisfied Linear Relations''' ('''Min-ULR'''), we are given a binary relation ''R'' and a linear system ''A x'' ''R'' ''b'', which is now assumed to be ''infeasible''. The goal is to find a vector ''x'' that violates as few relations as possible, while satisfying all the others.

In the complementary problem '''MAXimum Feasible Linear Subystem''' ('''Max-FLS'''), the goal is to find a maximum subset of the constraints that can be satisfied simultaneously.<ref>{{Cite journal|date=1995-08-07|title=The complexity and approximability of finding maximum feasible subsystems of linear relations|url=https://www.sciencedirect.com/science/article/pii/030439759400254G|journal=Theoretical Computer Science|language=en|volume=147|issue=1-2|pages=181–210|doi=10.1016/0304-3975(94)00254-G|issn=0304-3975}}</ref> Max-FLS[≠] is polynomial, but Max-FLS[=] , Max-FLS[>] and Max-FLS[≥] are NP-hard even with homogeneous systems and bipolar coefficients.

== References ==