Дискретная оптимизационная задача с матрицей

[B@R5uk]

Задача состоит в том, чтобы найти столбец $X$, доставляющий минимум ${\left\| Y-AX \right\|}^{2}$. Причём элементы столбца $X$ могут принимать значения только $0$ или $1$. Единственное, что приходит на ум, — перебор в лоб. Однако, это весьма медленная процедура и требует большого количества компьютерного времени. Хотелось бы что-то более продвинутое, наподобие вычисления величины ${{\left( {{A}^{T}}A \right)}^{-1}}{{A}^{T}}Y$, как если бы это была бы обычная минимизация. Подскажите, пожалуйста, есть ли какие-нибудь аналитические подходы к решению этой задачи.

Не уверен, что это поможет с решением (да и хотелось бы чего-нибудь общего), но про матрицу $A$ дополнительно известно, что каждая следующая её строка является предыдущей, сдвинутой вправо с дополнением нулём спереди. А столбец $Y$ в качестве своих элементов имеет числа из отрезка $\left[ 0,1 \right]$.

[iifat]

Не уверен как-то, что перебор будет сильно медленнее такой вот формулы. Если устроить перебор с изменением на каждом шаге одного разряда, то и вычислений на каждом шаге потребуется немного.

[mihaild]

Без уточнения структуры $A$ задача $NP$-трудная даже для $Y$ размером $1 \times 1$.

[Sphinx Pinastri]

А матрица какого размера? И много ли таких задач надо решить за секунду машинного времени? Задавать задачки без ограничений и без примера нехорошо.

[Евгений Машеров]

Первое, что приходит в голову - штрафные функции, скажем $\Sigma_i\alpha_ix_i^2(1-x_i)^2$, прибавляемые к целевой. Но теряется простота аналитического решения, получается серия нелинейных оптимизаций, в каждой из которых увеличиваются и увеличиваются альфы.
Второе - ветви и границы, ветвимся заданием данной переменной значений 0 и 1, а отсекаем, решая ${{\left( {{C}^{T}}C \right)}^{-1}}{{C}^{T}}V$ где C получено из матрицы A вычёркиванием строк, для которых задано 0 или 1, а V - вычитанием из Y соответствующих строк, и расчётом нормы разности, дающей оценку снизу лучшего для этой ветки решения.

[B@R5uk]

Евгений Машеров в сообщении #1215303 писал(а):

Второе - ветви и границы, ветвимся заданием данной переменной значений 0 и 1, а отсекаем, решая ${{\left( {{C}^{T}}C \right)}^{-1}}{{C}^{T}}V$

Спасибо. Вот это интересная идея.

mihaild в сообщении #1215161 писал(а):

Без уточнения структуры $A$

Я же написал:

B@R5uk в сообщении #1215137 писал(а):

про матрицу $A$ дополнительно известно, что каждая следующая её строка является предыдущей, сдвинутой вправо с дополнением нулём спереди.

Если быть ещё более конкретным, то каждая строка является импульсным откликом инерционной системы. Задача состоит в том, чтобы подобрать такой высокочастотный цифровой поток, чтобы на выходе этой системы был желаемый результат с как можно большей точностью. Поэтому:

Sphinx Pinastri в сообщении #1215171 писал(а):

А матрица какого размера? И много ли таких задач надо решить за секунду машинного времени?

Большого и очень много!