Minimální relevantní proměnné v lineárním systému - Minimum relevant variables in linear system
MINIMÁLNÍ relevantní proměnné v lineárním systému (Min-RVLS) je problém v matematická optimalizace. Vzhledem k tomu, lineární program, je nutné najít proveditelné řešení, ve kterém je počet nenulových proměnných co nejmenší.
Je známo, že problém je NP-tvrdé a dokonce těžké se přiblížit.
Definice
Problém Min-RVLS je definován:[1]
- Binární relace R, což je jeden z {=, ≥,>, ≠};
- An m-podle-n matice A (kde m je počet omezení a n počet proměnných);
- An m-by-1 vektor b.
Lineární systém je dán vztahem: A x R b. Předpokládá se, že je to proveditelné (tj. Splněno alespoň jedním X). V závislosti na R existují čtyři různé varianty tohoto systému: A x = b, A x ≥ b, A x> b, A x ≠ b.
Cílem je najít n-by-1 vektor X který vyhovuje systému A x R b, a podle toho obsahuje co nejméně nenulových prvků.
Speciální případ
Problém Min-RVLS [=] představili Garey a Johnson,[2] kdo to nazval „řešením minimální hmotnosti lineárních rovnic“. Dokázali, že je to NP-tvrdé, ale neuvažovali o aproximacích.
Aplikace
Problém Min-RVLS je důležitý v strojové učení a lineární diskriminační analýza. Vzhledem k řadě pozitivních a negativních příkladů je nutné minimalizovat počet funkcí, které jsou nutné k jejich správné klasifikaci.[3] Problém je znám jako minimální problém se sadou funkcí. Algoritmus, který aproximuje Min-RVLS v rámci faktoru mohl podstatně snížit počet tréninkových vzorků potřebných k dosažení dané úrovně přesnosti.[4]
The nejkratší problém s kódovým slovem v teorie kódování je stejný problém jako Min-RVLS [=], když jsou koeficienty v GF (2).
Související problémy
v MINIMálně neuspokojené lineární vztahy (Min. ULR), dostaneme binární vztah R a lineární systém A x R b, o kterém se nyní předpokládá, že je nemožné. Cílem je najít vektor X která porušuje co nejméně vztahů a uspokojuje všechny ostatní.
Min-ULR [≠] je triviálně řešitelný, protože je možný jakýkoli systém se skutečnými proměnnými a konečným počtem omezení nerovnosti. Pokud jde o další tři varianty:
- Min-ULR [=,>, ≥] jsou NP tvrdé i při homogenních systémech a bipolárních koeficientech (koeficienty v {1, -1}). [5]
- NP-úplný problém Nastaven minimální oblouk zpětné vazby redukuje na Min-ULR [≥], přičemž v každém omezení je přesně jedna 1 a jedna -1 a všechny pravé strany se rovnají 1. [6]
- Min-ULR [=,>, ≥] jsou polynomy, pokud je počet proměnných n je konstantní: mohou být řešeny polynomiálně pomocí Greerova algoritmu[7] včas .
- Min-ULR [=,>, ≥] jsou lineární, pokud je počet omezení m je konstantní, protože všechny subsystémy lze zkontrolovat včas Ó(n).
- Min-ULR [≥] je v některých zvláštních případech polynomiální.[6]
- Min-ULR [=,>, ≥] lze přiblížit v rámci n +1 v polynomiálním čase.[1]
- Min-ULR [>, ≥] jsou minimální dominující sada -tvrdý, dokonce is homogenními systémy a ternárními koeficienty (v {−1,0,1}).
- Min-ULR [=] nelze přiblížit v rámci faktoru , pro všechny , pokud NP není obsažen v DTIME (). [8]
V doplňkovém problému MAXimální proveditelné lineární subystem (Max-FLS), cílem je najít maximální podmnožinu omezení, která lze splnit současně.[5]
- Max-FLS [≠] lze vyřešit v polynomiálním čase.
- Max-FLS [=] je NP tvrdý i při homogenních systémech a bipolárních koeficientech.
- . S celočíselnými koeficienty je těžké se přiblížit uvnitř . S koeficienty nad GF [q] to je q- přibližný.
- Max-FLS [>] a Max-FLS [≥] jsou NP-tvrdé i při homogenních systémech a bipolárních koeficientech. Jsou 2-aproximovatelné, ale nelze je aproximovat v žádném menším konstantním faktoru.
Tvrdost aproximace
Všechny čtyři varianty Min-RVLS se těžko přibližují. Zejména všechny čtyři varianty nelze aproximovat v rámci faktoru , pro všechny , pokud NP není obsažen v DTIME ().[1]:247–250 Tvrdost dokazují redukce:
- Dochází ke snížení z Min-ULR [=] na Min-RVLS [=]. Platí také pro Min-RVLS [≥] a Min-RVLS [>], protože každou rovnici lze nahradit dvěma doplňkovými nerovnostmi.
- K dispozici je snížení z minimální dominující sada na Min-RVLS [≠].
Na druhou stranu je zde redukce z Min-RVLS [=] na Min-ULR [=]. Platí také pro Min-ULR [≥] a Min-ULR [>], protože každou rovnici lze nahradit dvěma doplňkovými nerovnostmi.
Proto když je R v {=,>, ≥}, jsou Min-ULR a Min-RVLS ekvivalentní, pokud jde o přibližnou tvrdost.
Reference
- ^ A b C Amaldi, Edoardo; Kann, Viggo (06.12.1998). "O přibližnosti minimalizace nenulových proměnných nebo neuspokojených vztahů v lineárních systémech". Teoretická informatika. 209 (1–2): 237–260. doi:10.1016 / S0304-3975 (97) 00115-1. ISSN 0304-3975.
- ^ Johnson, David S .; Garey, M. R. (1979). „Počítače a neodolatelnost: Průvodce po teorii úplnosti NP“. www.semanticscholar.org. Citováno 2019-01-07.
- ^ Koehler, Gary J. (01.11.1991). "Lineární diskriminační funkce určené genetickým hledáním". ORSA Journal on Computing. 3 (4): 345–357. doi:10.1287 / ijoc.3.4.345. ISSN 0899-1499.
- ^ Van Horn, Kevin S .; Martinez, Tony R. (01.03.1994). "Minimální problém se sadou funkcí". Neural Netw. 7 (3): 491–494. doi:10.1016/0893-6080(94)90082-5. ISSN 0893-6080.
- ^ A b Amaldi, Edoardo; Kann, Viggo (07.08.1995). "Složitost a přibližnost nalezení maximálních proveditelných subsystémů lineárních vztahů". Teoretická informatika. 147 (1–2): 181–210. doi:10.1016 / 0304-3975 (94) 00254-G. ISSN 0304-3975.
- ^ A b Sankaran, Jayaram K. (01.02.1993). "Poznámka k řešení neproveditelnosti v lineárních programech omezením uvolnění". Dopisy o operačním výzkumu. 13 (1): 19–20. doi:10.1016 / 0167-6377 (93) 90079-V. ISSN 0167-6377.
- ^ Greer, R. (2011-08-18). Stromy a kopce: Metodika pro maximalizaci funkcí systémů lineárních vztahů. Elsevier. ISBN 9780080872070.
- ^ Arora, Sanjeev; Babai, László; Stern, Jacques; Sweedyk, Z. (01.04.1997). "Tvrdost přibližné Optimy v mřížkách, kódech a systémech lineárních rovnic". Journal of Computer and System Sciences. 54 (2): 317–331. doi:10.1006 / jcss.1997.1472. ISSN 0022-0000.