Минимальные соответствующие переменные в линейной системе

Минимальное количество соответствующих переменных в линейной системе ( Min-RVLS ) представляет собой проблему математической оптимизации . Учитывая линейную программу , требуется найти допустимое решение, в котором число ненулевых переменных будет как можно меньшим.

Известно, что задача NP-трудна и даже трудно аппроксимируется.

Определение

Проблема Min-RVLS определяется: ^[1]

Бинарное отношение R , которое является одним из {=, ≥, >, ≠};
Матрица mxn размером — — A (где m количество ограничений, а n количество переменных);
Вектор m -x1 b .

Линейная система имеет вид: A x R b. Предполагается, что оно осуществимо (т. е. удовлетворяется хотя бы одним x ). В зависимости от R существует четыре различных варианта этой системы: A x = b, A x ≥ b, A x > b, A x ≠ b .

Цель состоит в том, чтобы найти размером n -x1 вектор x , который удовлетворяет системе A x R b и при этом содержит как можно меньше ненулевых элементов.

Особый случай

Проблема Min-RVLS[=] была представлена Гари и Джонсоном, ^[2] который назвал это «решением линейных уравнений с минимальным весом». Они доказали, что это NP-трудно, но не рассматривали аппроксимации.

Приложения

Проблема Min-RVLS важна в машинном обучении и линейном дискриминантном анализе . Учитывая набор положительных и отрицательных примеров, требуется минимизировать количество признаков, необходимых для их правильной классификации. ^[3] Эта проблема известна как проблема минимального набора функций . Алгоритм, аппроксимирующий Min-RVLS с точностью до коэффициента $O(\log(m))$ может существенно сократить количество обучающих выборок, необходимых для достижения заданного уровня точности. ^[4]

Проблема кратчайшего кодового слова в теории кодирования — это та же проблема, что и Min-RVLS[=], когда коэффициенты находятся в GF(2).

Связанные проблемы

В минимальных неудовлетворенных линейных отношениях ( Min-ULR ) нам даны бинарное отношение R и линейная система A x R b , которая теперь считается недопустимой . Цель состоит в том, чтобы найти вектор x , который нарушает как можно меньше отношений, но при этом удовлетворяет всем остальным.

Min-ULR[≠] тривиально разрешима, поскольку возможна любая система с действительными переменными и конечным числом ограничений-неравенств. Что касается остальных трех вариантов:

Min-ULR[=,>,≥] NP-трудны даже для однородных систем и биполярных коэффициентов (коэффициентов в {1,-1}). ^[5]
NP-полная задача Минимальный набор дуг обратной связи сводится к Min-ULR[≥] ровно с одной 1 и одной -1 в каждом ограничении, а все правые части равны 1. ^[6]
Min-ULR[=,>,≥] являются полиномиальными, если число переменных n постоянно: их можно решить полиномиально с использованием алгоритма Грира. ^[7] вовремя $O(n\cdot m^{n}/2^{n-1})$ .
Min-ULR[=,>,≥] являются линейными, если количество ограничений m постоянно, поскольку все подсистемы можно проверить за время O ( n ).
Min-ULR[≥] в некотором особом случае является полиномиальным. ^[6]
Min-ULR[=,>,≥] может быть аппроксимирован в пределах n + 1 за полиномиальное время. ^[1]
Min-ULR[>,≥] являются -жесткими с минимальным доминирующим множеством , даже с однородными системами и тройными коэффициентами (в {−1,0,1}).
Min-ULR[=] не может быть аппроксимирован с точностью до коэффициента $2^{\log ^{1-\varepsilon }n}$ , для любого $\varepsilon >0$ , если только NP не содержится в DTIME ( $n^{\operatorname {polylog} (n)}$ ). ^[8]

В дополнительной задаче максимально допустимой линейной подсистемы ( Max-FLS ) цель состоит в том, чтобы найти максимальное подмножество ограничений, которые могут быть удовлетворены одновременно. ^[5]

Max-FLS[≠] можно решить за полиномиальное время.
Max-FLS[=] NP-труден даже для однородных систем и биполярных коэффициентов.

. С целыми коэффициентами трудно аппроксимировать с точностью до $m^{\varepsilon }$ . С коэффициентами над GF[q] он q -аппроксимируем.
Max-FLS[>] и Max-FLS[≥] NP-трудны даже для однородных систем и биполярных коэффициентов. Они 2-аппроксимируемы, но не могут быть аппроксимированы с точностью до меньшего постоянного множителя.

Твердость аппроксимации

Все четыре варианта Min-RVLS трудно аппроксимировать. В частности, все четыре варианта не могут быть аппроксимированы с точностью до коэффициента. $2^{\log ^{1-\varepsilon }n}$ , для любого $\varepsilon >0$ , если только NP не содержится в DTIME ( $n^{\operatorname {polylog} (n)}$ ). ^[1]^{: 247–250} Твердость подтверждается сокращениями:

Произошло сокращение с Min-ULR[=] до Min-RVLS[=]. Это также применимо к Min-RVLS[≥] и Min-RVLS[>], поскольку каждое уравнение можно заменить двумя дополнительными неравенствами.
Происходит сокращение от минимального доминирующего набора до Min-RVLS[≠].

С другой стороны, происходит сокращение Min-RVLS[=] до Min-ULR[=]. Это также применимо к Min-ULR[≥] и Min-ULR[>], поскольку каждое уравнение можно заменить двумя дополнительными неравенствами.

Следовательно, когда R находится в {=,>,≥}, Min-ULR и Min-RVLS эквивалентны с точки зрения жесткости аппроксимации.

Ссылки

^ Перейти обратно: ^а ^б ^с Амальди, Эдоардо; Канн, Вигго (декабрь 1998 г.). «Об аппроксимации минимизации ненулевых переменных или неудовлетворенных отношений в линейных системах» . Теоретическая информатика . 209 (1–2): 237–260. дои : 10.1016/S0304-3975(97)00115-1 .
^ Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимость: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 978-0-7167-1044-8 .
^ Келер, Гэри Дж. (ноябрь 1991 г.). «Линейные дискриминантные функции, определяемые генетическим поиском». Журнал ORSA по вычислительной технике . 3 (4): 345–357. дои : 10.1287/ijoc.3.4.345 .
^ Ван Хорн, Кевин С.; Мартинес, Тони Р. (январь 1994 г.). «Проблема минимального набора функций». Нейронные сети . 7 (3): 491–494. дои : 10.1016/0893-6080(94)90082-5 .
^ Перейти обратно: ^а ^б Амальди, Эдоардо; Канн, Вигго (август 1995 г.). «Сложность и аппроксимируемость нахождения максимально возможных подсистем линейных отношений» . Теоретическая информатика . 147 (1–2): 181–210. дои : 10.1016/0304-3975(94)00254-G .
^ Перейти обратно: ^а ^б Шанкаран, Джаярам К. (февраль 1993 г.). «Заметка о разрешении недопустимости в линейных программах путем ослабления ограничений». Письма об исследованиях операций . 13 (1): 19–20. дои : 10.1016/0167-6377(93)90079-В .
^ Грир, Р. (2011). Деревья и холмы: методология максимизации функций систем линейных отношений . Эльзевир. ISBN 978-0-08-087207-0 . ^{[ нужна страница ]}
^ Арора, Санджив; Бабай, Ласло; Стерн, Жак; Сведик, З. (апрель 1997 г.). «Твердость приближенных оптимумов в решетках, кодах и системах линейных уравнений» . Журнал компьютерных и системных наук . 54 (2): 317–331. дои : 10.1006/jcss.1997.1472 .

[:1-1] Перейти обратно: ^а ^б ^с Амальди, Эдоардо; Канн, Вигго (декабрь 1998 г.). «Об аппроксимации минимизации ненулевых переменных или неудовлетворенных отношений в линейных системах» . Теоретическая информатика . 209 (1–2): 237–260. дои : 10.1016/S0304-3975(97)00115-1 .

[2] Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимость: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 978-0-7167-1044-8 .

[3] Келер, Гэри Дж. (ноябрь 1991 г.). «Линейные дискриминантные функции, определяемые генетическим поиском». Журнал ORSA по вычислительной технике . 3 (4): 345–357. дои : 10.1287/ijoc.3.4.345 .

[4] Ван Хорн, Кевин С.; Мартинес, Тони Р. (январь 1994 г.). «Проблема минимального набора функций». Нейронные сети . 7 (3): 491–494. дои : 10.1016/0893-6080(94)90082-5 .

[:0-5] Перейти обратно: ^а ^б Амальди, Эдоардо; Канн, Вигго (август 1995 г.). «Сложность и аппроксимируемость нахождения максимально возможных подсистем линейных отношений» . Теоретическая информатика . 147 (1–2): 181–210. дои : 10.1016/0304-3975(94)00254-G .

[:2-6] Перейти обратно: ^а ^б Шанкаран, Джаярам К. (февраль 1993 г.). «Заметка о разрешении недопустимости в линейных программах путем ослабления ограничений». Письма об исследованиях операций . 13 (1): 19–20. дои : 10.1016/0167-6377(93)90079-В .

[7] Грир, Р. (2011). Деревья и холмы: методология максимизации функций систем линейных отношений . Эльзевир. ISBN 978-0-08-087207-0 . ^{[ нужна страница ]}

[8] Арора, Санджив; Бабай, Ласло; Стерн, Жак; Сведик, З. (апрель 1997 г.). «Твердость приближенных оптимумов в решетках, кодах и системах линейных уравнений» . Журнал компьютерных и системных наук . 54 (2): 317–331. дои : 10.1006/jcss.1997.1472 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]