Диссертация (1150844), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

. . , — разница междумаксимальным среди всех и текущим весом, при этом max ≥ 0, ^ ≥ 0. Меж­̂︀ = (^ду векторами = (1 , . . . , )T и 1 , . . . , ^ , max )T существует простое̂︀ где H ∈ R×(+1) — матрица следующеголинейное соответствие: = H,вида:⎛⎜⎜H=⎜⎝−100...1...−1 1⎞⎟⎟⎟.⎠(4.18)Условие cond(diag R) ≤ 1/, устанавливающее границу снизу для весов, в но­вых обозначениях записывается как (1 − )max − ^ ≥ 0, = 1, .

. . , .Получаем следующую задачу квадратичного программирования с линей­ными ограничениями, но с нестрого выпуклой целевой функцией:Задача 4.3.3.̂︀^⋆ = min ^(),̂︀ ℛ^∈̂︀ = (H)̂︀ = 1 ̂︀T HT SĤ︀ − 1T̂︀где ^() H,2(4.19)89{︁ ⃒^̂︀ ⃒⃒ ^ ≥ 0,ℛ= (1 − )max − ^ ≥ 0,}︁ = 1, . . . , .(4.20)Теорема 4.3.1. Задачи 4.3.1, 4.3.2 и 4.3.3 эквивалентны.Доказательство. Требуется доказать, что ⋆ ≥ ⋆⋆ ≥ ^⋆ ≥ ⋆ , и что по реше­нию одной из задач можно построить решение любой другой.1. ( ⋆ ≥ ⋆⋆ ). Пусть ⋆ — решение задачи 4.3.1, то есть ⋆ = arg min∈ℛ ().Положим ⋆ = arg max .

⋆ ∈ ℛ и ⋆ — палиндром, следовательно,⋆ ∈ ℛ ⋆ . Цепочка неравенств ⋆ = (⋆ ) ≥ ⋆ = min∈ℛ⋆ () ≥min=1,...,⌈/2⌉ min∈ℛ () = ⋆⋆ завершает доказательство пункта.2. ( ⋆⋆ ≥ ^⋆ ). Пусть ⋆ = arg min=1,...,⌈/2⌉ ⋆ , ⋆⋆ = arg min∈ℛ⋆ () —решение задачи 4.3.2. Положим max = ⋆ , ⋆ , ^ = max − ⋆ , , = 1, . . . , ,̂︀ ∈ ℛ,^ из чего полу­где ⋆⋆ = ( ⋆ ,1 , . . . , ⋆ , )T . Нетрудно заметить, что ̂︀ = (⋆⋆ ) = ⋆⋆ .чим, что ^⋆ ≤ ^()̂︀⋆ = arg min ̂︀ ^ ^()̂︀ — решение задачи 4.3.3. Положим3. (^⋆ ≥ ⋆ ).

Пусть ∈ℛ = max − ^ и заметим, что ∈ ℛ, из чего получим, что ⋆ ≤ () =̂︀ = ^⋆ .^()4.3.2. Общий алгоритм решенияИспользуя эквивалентность, доказанную в теореме 4.3.1, можем сформу­лировать следующий алгоритм решения Задачи 4.3.1:Алгоритм 4.3.1. Вход: Параметры , , .1:Положить = 1.2:Решить подзадачу КП (4.14) ⋆ = (,1 , . . . , , )T = arg min∈ℛ ().3:̂︀ из (4.19), взяв max = , , ^ = max − , .Задать эквивалентный вектор 904:5:6:7:8:̂︀ — решение задачи 4.3.3 thenif Вектор return ⋆ = ⋆ — вектор оптимальных весовelseПоложить = + 1 и перейти к пункту 2.end ifТаким образом, если встретился нужный индекс , то алгоритму не по­надобится перебирать оставшиеся индексы и решать подзадачу (4.14) лишнийраз.

Практические эксперименты показывают, что максимальный вес всегданаходится на краях: алгоритм 4.3.1 останавливается уже при = 1, то естьфактически сводится к задаче КП с положительно определённой квадратичнойформой в целевой функции.Для реализации алгоритма 4.3.1 необходимо разработать алгоритмы реше­ния задач из пунктов 2 и 4, что и будет сделано в следующих разделах. Сначалав разделе 4.3.3 рассмотрим пункт 4, а в разделе 4.3.4 — пункт 2.4.3.3.

Проверка вектора на решение задачи 4.3.3Предложим быстрый алгоритм, проверяющий, является ли заданный век­̂︀ точкой, в которой достигается глобальный минимум в задаче 4.3.3, тотор есть реализующий пункт 4 из алгоритма 4.3.1. Для этого применим теоремуо необходимом и достаточном условии минимума в задаче квадратичного про­граммирования для задачи 4.3.3.Теорема 4.3.2.̂︀ −1. Рассмотрим вектор = (1 , . . .

, +1 )T = HT SĤ︀ является решением задачи 4.3.3 в том и только в томHT 1 . Тогда случае, если:̂︀ = 0,а. T б. Существует вектор = (1 , . . . , )T ∈ R такой, что имеют91место неравенства ≥ 0, = 1, . . . , , ≥ − , = 1, . . . , и∑︀(1 − ) =1 ≤ +1 .̂︀ является решением2.

Положим = max(0, − ), = 1, . . . , . Тогда задачи 4.3.3 в том и только в том случае, если:̂︀ = 0,а. T ∑︀б. (1 − ) =1 ≤ +1 .Доказательство. Первый пункт данной теоремы является переформулировкойтеоремы [54, теорема 9.2] для задачи 4.3.3, поэтому перейдём сразу к доказа­тельству второго пункта.Условие (а) в обоих пунктах одинаковое.

Докажем эквивалентность усло­вия (б).Достаточность. Коэффициенты выбраны так, чтобы условия ≥ 0 и ≥ − выполнялись. Если удовлетворено и условие (б), то выполняются всетребования первого пункта.Необходимость. Очевидно, что выбраны наименьшими из всех тех, ко­∑︀торые удовлетворяют условиям ≥ 0 и ≥ − . Пусть (1 − ) =1 >̃︀ = (˜+1 .

Рассмотрим любой вектор 1 , . . . , ˜ )T , удовлетворяющий условию∑︀(1 − ) ˜ ≤ +1 . Тогда существует индекс такой, что ˜ < . Следова­=1 тельно, либо ˜ < 0, либо ˜ < − , из чего следует, что не существует такого̃︀ , который бы удовлетворял условиям первого пункта.вектора Рассмотрим следующий алгоритм, базирующийся на теореме 4.3.2.̂︀ параметр .Алгоритм 4.3.2. Вход: предполагаемое решение ,̂︀ решением задачи 4.3.3.Результат: Булево значение: является ли 1:2:̂︀ − HT 1 .Вычислить = HT SĤ︀ ̸= 0 thenif T 923:4:5:return FALSEelseПерейти к пункту 7.6:end if7:Выбрать в качестве вектора = (1 , . .

. , )T следующие значения: =8:9:10:11:12:max(0, − ), = 1, . . . , .∑︀if (1 − ) =1 ≤ +1 thenreturn TRUEelsereturn FALSEend if4.3.4. Задача квадратичного программирования специального видаТеперь переходим к пункту 2 алгоритма 4.3.1. Для решения подзадачи(4.14) при зафиксированном индексе воспользуемся алгоритмом 1.5.1. Специ­фика задачи позволяет эффективно реализовать алгоритм.Подзадача (4.14) при фиксированном переписывается в терминах задачи1.5.1 следующим образом: ⋆ = ⋆ , = , G = S, = 1 , (1.10) состоит из(4.15), (1.11) состоит из (4.16) и (4.17).Таким образом, необходимо объяснить, как находить начальную точку (п.1 алгоритма 1.5.1), решение подзадачи квадратичного программирования и мно­жители Лагранжа (п.

4 алгоритма 1.5.1) применительно к частному случаюзадачи (4.14).Обозначим вкратце те особенности, которые помогают получить быстроерешение:∙ Для выполнения пункта 4 алгоритма 1.5.1 требуется уметь решать задачу(1.12) с ограничениями (1.13). Положив A = [ : ∈ ], A ∈ R× ,93ограничения (1.13) можно записать как AT = 0 , где — количествоактивных ограничений.Для решения поставленной вспомогательной задачи (1.12) есть явная фор­мула обобщённого метода наименьших квадратов:⋆ = A⊥ ((A⊥ )T GA⊥ )−1 (A⊥ )T ,где матрица A⊥ ∈ R×(−) состоит из столбцов, составляющих базисортогонального дополнения к базису столбцов матрицы A.

Обычно ве­лико, поэтому − мало, что позволяет быстро искать решение подза­дачи.В случае задачи 4.3.2 матрица G имеет простой вид, и её можно умножатьна вектор за время (). Матрица A — разрежённая, в ней содержитсямаксимум 2 ненулевых коэффициента в каждом столбце. За счёт этогоматрицу A⊥ можно также найти быстро и хранить, используя () па­мяти. Из-за быстрого умножения матрицы A для вычисления формулыобобщённого МНК удобно и эффективно использовать метод сопряжён­ных градиентов, вычислительная сложность которого (( − )).Аналогично, за счёт разрежённости матрицы A можно быстро находитьмножители Лагранжа за время ().

Таким образом, вычислительнаясложность одного шага алгоритма 1.5.1 при решении подзадачи (4.14) рав­на (( − )).∙ Есть две стратегии выбора начальной точки: первая применяется при ма­лом размере задачи и заключается в том, чтобы назначить первым точ­кам, где перебирается по целочисленной сетке до ⌊/2⌋, максимальныйвес (то есть (4.17)), а оставшимся — минимальный (то есть (4.16)), послечего выбрать то , где достигается наименьшее значение целевой функции ().94Вторая стратегия используется при = 1 и основана на следующем на­блюдении: решения задач при примерно одинаковом отношении к иодинаковом схожи. Например, на рисунке 4.2 изображены два отнорми­рованных (умноженных на ) решения задачи 4.3.1 при = 200, = 60, = 0.1 и = 1000, = 300, = 0.1 соответственно.N = 1000, L = 300, alpha = 0.1551010rr15152020N = 200, L = 60, alpha = 0.10204060801001201400Index100200300400500600700IndexРис.

4.2. Два решения задачи 4.3.1 при одинаковом отношении к .Схема эвристики следующая: зафиксируем параметр масштаба 0 < < 1(на практике хорошими значениями являются 0.5 – 0.7), найдём решениезадачи при ≈ , ≈ , = , после чего используем решениезадачи меньшего порядка для выбора начального рабочего множества иначальной точки. Формально, алгоритм выглядит так:Алгоритм 4.3.3. Вход: параметр .Результат: Начальное рабочее множество ограничений 0 и старто­вая точка 0 .1:Положить = [], = [], = + − 1.2:Определить функцию () = [размерности.(−1)( −1)−1+ 1] перехода к уменьшенной953:Найти масштабированное решение = (,1 , . . . , , )T задачи (4.14)при = , = , = , = = 1.4:Добавить к рабочему множеству индексы всех ограничений вида(4.15).5:for all = 2, 3, .

Характеристики

Список файлов диссертации