Повторением операции мы уменьшаем размеры исходного многогранника и потом отслеживаем шаги поиска и приближения (к пределу). В процессе уменьшения многогранник иногда может принимать настолько малые размеры, что невозможно будет найти решение. Для возобновления процесса поиска мы будем использовать
, которая выбирает новый многогранник и новый процесс многократного уменьшения многогранника начинается заново. Размер многогранника определяется как . Если будет меньше ранее определенного значения e1, то начнет выполняться новый цикл. Построение большего по размерам многогранника позволяет получить следующие преимущества:1) Увеличение размера многогранника увеличивает шаг поиска на столько, чтобы он был способен достичь наилучшей вершины.
2) Форма многогранника изменяется в соответствии с направлением поиска.
Результаты двух следствий сравниваются. Цикл будет повторяться до тех пор, пока не возникнет каких-либо существенных различий между результатами, т.е. разность решений двух циклов будет меньше ранее определенного значения e2. Ниже представлен подробный алгоритм вычисления. LВ алгоритме, при достижении 14 шага, цикл завершается. На 13 шаге завершается стадия повторения этого цикла. Таким образом, kk – номер цикла, который начинается с 0, а k – номер стадии для каждого цикла, который тоже начинается с 0.
(Инициализация)
Шаг 1) Пусть kk=0 и k=0. Выбираем
и в выражениях (15), (17) и (18). Также выбираем е1 и е2. Пусть OLDХs=[0,0,…,0].(Вычисление первой вершины многогранника)
Шаг 2) Вычисляем
по (20). Если подходит, тогда ; иначе, величине присваивается подходящая вершина, преобразованная процедурой (ПВР) из .(Вычисление остальных n-1 вершин многогранника)
Шаг 3) Для i=2,3,…,n вычисляем
по (21). Если подходит, тогда ; иначе, величине присваивается подходящая вершина, преобразованная процедурой (ПВР) из .Шаг 4) Из n вершин
а) определяем , которая принимает наименьшее значение функции и б) , которая принимает наибольшее значение функции. Из этого следует и .Шаг 5) Вычисляем центр многогранника
по (13).(Отображение)
Шаг 6) Проводим отображение для получения
с помощью (14) и (15). Полученную величину приводим к подходящему для нас виду процедурой (ПВР), если до этого она была не подходящей.(Растяжение, при
)Шаг 7) Если
, то выполняем а), б), и с) ………………………; иначе, переходим к шагу 8).а) Если
полагаем , потом увеличиваем k=k+1 и переходим на шаг 13),иначе продолжаем (Замечание:
показывает, что некоторые вершины многогранника в результате отображения имеют хоть и малые, но положительные значения. Растяжение нельзя проводить, т.к. они могут стать отрицательными, а это нарушает условие о положительных временных интервалов.б) Выполняем отображение для получения
по формулам (16) и (17). Приводим к подходящему для нас виду процедурой (ПВР), если до этого она была не подходящей.с) Выбираем
потом увеличиваем k=k+1 и переходим на шаг 13).
Шаг 8) Если
для некоторых полагаем , потом увеличиваем k=k+1 и переходим на шаг 13).Шаг 9) Если
, тогда полагаем .(Сжатие)
Шаг 10) Выполняем сжатие для получения величины
по формуле (18). Полученную величину приводим к подходящему для нас виду процедурой (ПВР), если до этого она была не подходящей.Шаг 11) Если
, тогда полагаем , потом увеличиваем k=k+1 и переходим на шаг 13), иначе продолжаем.(Уменьшение)
Шаг 12) Уменьшаем многогранник следующим образом:
, i=1,2,…,n.(Проверка размера многогранника)
Шаг 13) Если
, тогда переходим на шаг 14), иначе переход на шаг 4).(Проверка на близость результатов решений двух циклов)
Шаг 14) Если
,тогда выводим как результат и прекращаем поиск; иначе полагаем , . Потом увеличиваем kk=kk+1, обнуляем k=0, и переходим на шаг 3).Алгоритм оптимизации всегда приводит не удовлетворяющую величину к подходя-щему для нас виду процедурой (ПВР), которая выполняет преобразование не удовлетворяющих величин умножением на величину
.Процедура преобразования занимает очень мало времени.В начале каждого цикла n вершин первоначально определяются так, что любая из (n-1) вершин линейно независима. Новая вершина, которая замещает
, всегда представляет собой линейную комбинацию и остальных n-1 вершин. Следовательно, любая из (n-1) вершин из нового выбора вершин n все еще линейно независима. Расположение исключает возможность того, что поиск попадет в подпространство.Вычисление производной для
Условие непрерывности по скорости дает нам
, i=1,2,…,n-1,что при использовании уравнений (1) и (2) приводит нас к уравнению вида:Не оговоренные присоединенные переменные в двух особых точках могут быть выражены граничными величинами начальных и конечных узлов вместе с
и . Следовательно, , (23) (24)Подставляя (23) и (24) в (22) получаем
(25) (26) (27) (28)Из-за условия непрерывности по ускорению в уравнениях (25) и (29)
примем равным .Таким образом, (25) – (29) –система, состоящая из n-2 уравнений с n-2 неизвестными ,для i=2,3,…,n-1.