Оптимизатор

Алгоритм Поиск-2

Реализуется алгоритм деления шага пополам при одном оптимизируемом параметре (n = 1) и алгоритм преобразований матрицы направлений при n > 1.

Далее рассматривается алгоритм многомерного поиска.

Направления поиска на k-том этапе задаются матрицей S_k. На очередном этапе производится серия спусков в направлениях векторов s₁, …, s_n, представляющих собой столбцы матрицы S_k . Векторы перемещений на каждом из спусков равны соответственно g₁s₁, …, g_ns_n. После выполнения спусков матрица направлений преобразуется по формуле:

где Λ_k - диагональная матрица, элементы которой равны λ_k = γ_i, если γ_i ≠ 0, и λ_k = 0.5, если γ_i = 0; P_k - ортогональная матрица.

Умножение на ортогональную матрицу необходимо для изменения набора направлений поиска. Если на всех этапах P_k = i , то направления поиска не изменяются от этапа к этапу и алгоритм представляет собой алгоритм покоординатного спуска. Очевидно, что выбор матриц P_k существенно влияет на эффективность поиска.

Было испытано несколько различных способов выбора ортогональных матриц P_k, в том числе и случайный выбор. Лучшим оказался способ, при котором все матрицы P_k равны между собой и определяются в виде:

Алгоритм Поиск-4

Реализуется алгоритм квадратичной интерполяции при одном оптимизируемом параметре (n = 1) и алгоритм преобразований вращения и растяжения-сжатия (n > 1).

Алгоритм при n > 1. Алгоритм основан на выполнении преобразований растяжения - сжатия и преобразований вращения для такого преобразования системы координат, при котором матрица вторых производных (матрица Гессе) приближается к единичной, а направления поиска становятся сопряженными. Этот алгоритм использует квадратичную интерполяцию.

Пусть H - симметричная положительно-определенная матрица. Формируется последовательность матриц:

где Λ_k - диагональная матрица с элементами λ_i = h_ii−1/2 (h_ii - диагональные элементы H_k-1); P_k - ортогональная матрица.

После умножения матрицы H_k−1 слева и справа на Λ_k получается матрица с единичными диагональными элементами. При подходящем выборе ортогональных матриц P_k матрица H_k будет стремиться к единичной. На этом, в частности, основан метод вращений для расчета собственных значений симметричных матриц.

В задаче поиска минимума функции нескольких переменных на k-м этапе поиска поочередно минимизируется функция в направлениях векторов s₁ ,…, s_n, представляющих собой столбцы матрицы S_k. Для нахождения точки минимума в направлении s_i используется квадратичная интерполяция по трем равноотстоящим точкам z = x − as_i , x , y = x + as_i .

Одновременно для каждого направления вычисляется

После выполнения серии спусков матрица S преобразуется по формуле:

где Λ_k - диагональная матрица, элементы которой определяются по выражению; P_k - некоторая ортогональная матрица.

Для квадратичной целевой функции матрица S_kT H S_k , где H - матрица Гессе, совпадает с матрицей H_k . Таким образом, при надлежащем выборе матриц P_k для квадратичной функции S_kT H S_k → i и направления поиска приближаются к сопряженным. В рассматриваемом алгоритме матрицы P_k одинаковы на всех этапах и определяются по формуле формуле.

Этапы работы алгоритма Поиск-4 аналогичны рассмотренным выше этапам алгоритма Поиск-2.

Алгоритм Симплекс

Используется метод «деформируемого многогранника» Нелдера и Мида.

В методе Нелдера-Мида минимизируется функция n независимых переменных с использованием n+1 вершин деформируемого многогранника. Каждая вершина может быть идентифицирована вектором x . Вершина (точка), в которой значение f(x) максимально, проектируется через центр тяжести (центроид) оставшихся вершин. Улучшенные (меньшие) значения целевой функции находятся последовательной заменой точки с максимальным значением f(x) на более “хорошие” точки, пока не будет найден минимум f(x).

Далее кратко излагается суть алгоритма.

Пусть x_i(k) = [x_i1(k), …, x_ij(k), …, x_in(k)]T, i = 1, …, n+1, является i-й вершиной (точкой) на k-том этапе поиска, k = 0, 1, …, и пусть значение целевой функции в x_i(k) равно f(x_i(k)). Также отмечаются векторы многогранника, которые дают максимальное и минимальное значения.

Пусть f(x_h(k)) = max{f(x₁(k)), …, f(x_n+1(k))},

где x_h(k) = x_i(k) , и

f(x_l(k)) = min{f(x₁(k)), …, f(x_n+1(k)),

где x_l(k) = x_i(k).

Поскольку многогранник в E_n состоит из (n+1) вершин x₁, …, x_n+1, пусть x_n+2 будет центром тяжести всех вершин, исключая x_h.

Тогда координаты этого центра определяются формулой:

где индекс j обозначает координатное направление.

Критерий окончания поиска - проверка условия:

где e - произвольное малое число, а f(x_n+2(k)) - значение целевой функции в центре тяжести x_n+2(k).

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

После того, как деформируемый многогранник подходящим образом масштабируется, его размеры должны поддерживаться неизменными, пока изменения в топологии задачи не потребуют применения многогранника другой формы. Анализ, проведенный Нелдером и Мидом, показал, что компромиссное значение a = 1. Ими также рекомендованы значения b = 0.5, g = 2. Более поздние исследования показали, что рекомендуются диапазоны 0.4 ≤ b ≤ 0.6, 2.8 ≤g ≤ 3.0, причем при 0 < b < 0.4 существует вероятность того, что из-за уплощения многогранника будет иметь место преждевременное окончание процесса, а при b›0.6 может потребоваться большее число шагов для достижения окончательного решения.

Алгоритм наискорейшего спуска

Градиент функции в любой точке показывает направление наибольшего локального увеличения f(x̅). Поэтому при поиске минимума f(x̅), следует двигаться в направлении противоположном направлению градиента ∇f(x̅) в данной точке, то есть в направлении наискорейшего спуска. Итерационная формула процесса наискорейшего спуска имеет вид:

или

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

решая одномерную задачу минимизации с использованием некоторого метода. В этом случае алгоритм представляет собой алгоритм наискорейшего спуска. Если λ определяется в результате одномерной минимизации, то градиент в точке очередного приближения будет ортогонален направлению предыдущего спуска ∇f(x̅)⟂S̅^k.

Метод сопряженных градиентов

В алгоритме наискорейшего спуска на каждом этапе поиска используется только текущая информация о функции f(x̅^k) и градиенте ∇f(x̅^k). В алгоритмах сопряженных градиентов используется информация о поиске на предыдущих этапах спуска.

Направление поиска S̅^k на текущем шаге k строится как линейная комбинация наискорейшего спуска −∇f(x̅^k) на данном шаге и направлений спуска S̅⁰, S̅¹, …, S̅^k−1 на предыдущих шагах. Веса в линейной комбинации выбираются таким образом, чтобы сделать эти направления сопряженными. В этом случае квадратичная функция будет минимизироваться за n шагов алгоритма.

При выборе весов используется только текущий градиент и градиент в предыдущей точке.

В начальной точке x̅⁰ направление спуска S̅⁰ = −∇f(x̅⁰) :

где λ⁰ выбирается из соображений минимальности целевой функции в данном направлении:

Новое направление поиска:

где ω₁ выбирается так, чтобы сделать направления S̅¹ и S̅⁰ сопряженными по отношению к матрице H :

Для квадратичной функции справедливы соотношения:

где Δx̅ = x̅ − x̅⁰,

Если положить x̅= x̅¹, тогда x̅¹ − x̅⁰ = λ⁰ S̅⁰ и

Используя выражение выше, можно исключить (S̅⁰)^T из уравнения. Для квадратичной функции H = H^T , поэтому после транспонирования выражения и умножения справа на H⁻¹, получается следующее выражение:

и далее

Следовательно, для сопряженности S̅⁰ и S̅¹:

Вследствие изложенных ранее свойств сопряженности все перекрестные члены исчезают. С учетом, что S̅⁰ = −∇f(x̅⁰) и, следовательно,

получено для ω₁ следующее соотношение:

Направление поиска S̅² строится в виде линейной комбинации векторов −∇f(x̅²), S̅⁰, S̅¹, причем так, чтобы оно было сопряженным с S̅¹.

Если распространить сделанные выкладки на S̅², S̅³, …, опуская их содержание и учитывая, что (S̅^k)^T∇f(x̅^k+1) = 0 приводит к ∇^Tf(x̅^k)∇f(x̅^k+1) = 0, можно получить общее выражение для ω_k:

Все весовые коэффициенты, предшествующие ω_k, что особенно интересно, оказываются нулевыми.

После n+1 итераций ( k = n), если не произошел останов алгоритма, процедура циклически повторяется с заменой x̅⁰ на x̅ⁿ⁺¹ и возвратом на первый пункт алгоритма. Если исходная функция является квадратичной, то (n+1)-е приближение даст точку экстремума данной функции. Описанный алгоритм с построением ω_k по формулам соответствует методу сопряженных градиентов Флетчера-Ривса.

В модификации Полака-Рибьера (Пшеничного) метод сопряженных градиентов отличается только вычислением:

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

Работа с блоком «Оптимизатор»

На вход блока «Оптимизатор» должен подаваться вектор критериев оптимизации. На основании этих значений, используя численные методы оптимизации, происходит подбор значения выходного вектора параметров оптимизации так, чтобы значения критериев лежали в необходимом диапазоне.

Входные порты

Выходные порты

Свойства

Параметры

Блок не имеет параметров.

Примеры