Глава 6 Прикладной регрессионный анализ (стр. 9 )

(6.34)

(6.35)

где – действительные переменные, – булевы переменные, – константа, выбираемая исследователем, – машинный ноль.

Эта задача является труднорешаемой задачей комбинаторной оптимизации. Для обоснования эффективного метода ее решения сведем задачу (6.32)–(6.35) к следующей задаче линейного целочисленного программирования (ЛЦП):

(6.36)

(6.37)

(6.38)

(6.39)

где – целочисленные переменные, – булевы переменные, – константа, выбираемая исследователем, – машинный ноль, – натуральное число, задаваемое исследователем.

Формально задача ЛЦП (6.36)–(6.39) сложнее, чем задача (6.32)–(6.35), так как в задаче (6.32)–(6.35) находится L целочисленных переменных, а в задаче (6.36)–(6.39) – 2L целочисленных переменных. Тем не менее структура задачи ЛЦП (6.36)–(6.39) позволяет применить метод решения задачи ЛЦП, который статистически значимо не использует экспоненциальный перебор вариантов с отсечениями.

Действительно, в [40] разработан и теоретически обоснован метод для задачи линейного целочисленного программирования с произвольной ограниченной областью допустимых решений. Предложена оригинальная схема приведения исходной задачи к задаче с одним ограничением и неотрицательными переменными со специфическими теоретическими свойствами. Принципиальная новизна метода состоит в том, что предложенный точный алгоритм поиска целочисленного решения разработан для исходной задачи с использованием теоретических свойств приведенной задачи (определены постоянные приоритеты каждой переменной исходной задачи, т. е. приоритеты переменных не зависят от каких-либо промежуточных значений переменных, что позволяет получить первое допустимое целочисленное решение, которое статистически значимо является оптимальным).

Принципиальным недостатком метода является невозможность определить без перебора с отсечениями всех допустимых решений, является ли первое допустимое целочисленное решение оптимальным. Однако в силу специфики задачи ЛЦП (6.36)–(6.39) первому (либо первому текущему) допустимому целочисленному решению задачи ЛЦП (6.36)–(6.39), полученному универсальным методом направленного перебора [40], соответствует решение задачи восстановления закономерности по критерию 1, если число ненулевых переменных , , окажется меньше – числа пассивных экспериментов. Метод изложен в пятой главе.

Метод 2 (вероятностный). Решение задачи по критерию 1. Пусть P – число экспериментов – ненамного меньше L – числа базовых функций в множестве I. Тогда в предположении, что K (число базовых функций в множестве I) существенно меньше P, с большой вероятностью (легко определяемой как функция от K) следующий метод дает точное решение по первому критерию.

Этап 1. Случайным образом конструируется последовательность базовых функций:

. (6.40)

Функции исключаются из последовательности (6.40). Получаем последовательность

. (6.41)

В предположении, что базовые функции из множества находятся в последовательности (6.41), переходим к этапу 2.

Этап 2. Из последовательности (6.41) исключается базовая функция , и для оставшихся базовых функций решается задача линейного программирования (ЛП):

(6.42)

(6.43)

Переменными задачи (6.42)–(6.43) являются , и , .

Если значение показателя качества (6.42) задачи ЛП (6.42)–(6.43) равно 0 (с точностью до погрешности решения задачи ЛП), то базовая функция окончательно исключается из последовательности (6.41), в противном случае . При этом предполагается, что гипотеза, которая легла в основу критерия 1, выполняется.

Описанная процедура повторяется для функции и так далее до функции включительно. Все базовые функции, попавшие в множество на предыдущих итерациях, участвуют в построении соответствующей текущей итерации задачи ЛП (аналог задачи ЛП (6.42)–(6.43)). Искомая закономерность восстанавливается по решению последней задачи ЛП с нулевым показателем качества (6.42).

Примечание. Если , то метод 2 перестает быть вероятностным и гарантированно находит решение по критерию 1.

Метод 2а (вероятностный). Решение задачи по критерию 1. Рассматривается обобщение представления (6.28) на случай, когда базовые функции разбиваются на простые и составные; – обозначение простой базовой функции; – обозначение составной базовой функции, которая является линейной сверткой вспомогательных базовых функций , , т. е. , – неизвестные коэффициенты. Таким образом, (6.28) задается в виде

(6.28а)

Принципиальная разница между описаниями (6.28) и (6.28а) заключается в следующем:

–  в отличие от простой базовой функции, которая в описании (6.28) входит с одним неизвестным коэффициентом ai, составная базовая функция входит в описание (6.28а) с Ki неизвестными коэффициентами;

–  содержательный смысл введения составной базовой функции заключается в том, что исследователь в избыточное описание неизвестной закономерности может вводить блоки, в котором появление одной базовой функции по предположению исследователя обязательно повлечет появление (в качестве линейной свертки) других базовых функций.

Модификация этапов 1 и 2 является очевидной.

Этап 1а. Подпоследовательность (6.41) не может включать в себя часть составной базовой функции.

Этап 2а. При реализации второго этапа составная базовая функция исключается, либо остается со всеми своими составляющими компонентами.

Метод 3 (вероятностный). Решение задачи по критерию 1. Вероятность решения исходной задачи с помощью метода 2 определяется как вероятность построения такой последовательности (6.41), в которую входят все истинные компоненты неизвестной закономерности (обозначим как событие ), т. е.

. (6.44)

Если задать верхнюю оценку для числа истинных базовых функций (), то можно посчитать количество повторов применения метода 2 (количество построений последовательности (6.40)), необходимых для того, чтобы с заданной вероятностью восстановить неизвестную закономерность. А в случае, когда верхняя граница числа истинных базовых функций восстанавливаемой закономерности равна (P – 1) (так как в (6.29) по исходному предположению должно выполняться P > K ), то нижняя оценка вероятности попадания неизвестных истинных компонент в последовательность (6.41) определяется как