Пускай имеем задачу НП: минимизировать
, |
(1) |
при ограничениях
. |
(2) |
Розенброком было предложено преобразование задачи НП (1)¸(2) к присоединённой функции без ограничений вида:
, |
(3) |
где
при
и
при
.
Следовательно, (3) вне допустимой области обращается в нуль. Предполагается, что в каждой точке допустимой области целевая функция принимает отрицательное значение, т.е.
. В случае если в некоторых либо кроме того во всех точках допустимой области
была хорошей, то вычитанием из
солидного постоянного числа
, будем иметь:
. Ясно, что
в этом случае не изменится.
Численный оптимизационный поиск задачи (3) может начинаться не только с внутренней точки
, вместе с тем и с точки, выходящей (неподалеку) за пределы допустимой области.
Чтобы продемонстрировать на связь между функцией (3) и присоединённой функцией ((4) в прошлом заголовке), прологарифмируем левую и правую части (3), предварительно поменяв их символы и перейдя от минимизации к максимизации, возьмём:
, |
(3′) |
(Умножить
и
нужно для того, чтобы получить положительные значения). Т.к.
на любой стадии вычислительного процесса есть константой, то возможно положить
и вычислять, что
, следовательно соответствие между (3) и (4 в прошлом заголовке) установлена.
Розенброком создана процедура абсолютной минимизации для задач без ограничений, она реализуется следующим образом:
Пускай
– единичные векторы,
– индекс, обозначающий этапы поиска. Ортонормированные векторы
строятся на основании информации, взятой на
-м этапе (будет продемонстрировано ниже).
, направления
в большинстве случаев берутся параллельными осям
. В общем случае ортогональные направления поиска смогут быть выражены как комбинация координат свободных переменных следующим образом:
, |
(4) |
где
– единичный вектор в направлении
;
– единичный вектор в направлении
.
Совокупность (4) в матричной форме:
. |
(5) |
Разглядим
-й этап:
Поиск начинается из начальной точки
, для чего вводится возмущение, равное
, в первом координатном направлении (
– протяженность шага, которая связана с направлением
). В случае если значение
, то ход считается успешным и полученная пробная точка заменяет
.
умножается на множитель
и вводится возмущение по направлению
. В случае если
, то ход считается неудачным и
не заменяется,
умножается на
и опять задаётся возмущение по направлению
. Розенброком предложено в общем случае брать значения параметров
.
По окончании того как пройдены все направления
,
, опять возвращаются к первому направлению
и вводится возмущение с длиной шага, равной
либо
, в зависимости от результата прошлого возмущения по направлению
. Возмущения по выбранным направлениям поиска задаются , пока по каждому из направлений за успехом не последует неудача. Наряду с этим
-й этап поиска заканчивается. Потому, что получение однообразных значений функции рассматривается как успех, успех в итоге достигается по каждому направлению, т.к. множители
уменьшают последовательно длины шагов. Причём, последняя полученная точка делается начальной точкой следующего этапа
.
Нормированное направление
берётся параллельым
, а остальные направления выбираются ортонормированными друг к другу и к
посредством одного из способов:
К примеру: Пускай
– имеется алгебраическая сумма всех успешных шагов (суммарное перемещение) в направлении
на
м этапе. Определим
векторов по формулам:
. |
(6) |
Так
– имеется вектор перехода из
в
,
– имеется вектор перехода из
в
и т.д.
Следовательно
представляет собой полное перемещение с
-го этапа на
-й этап,
– полное перемещение, но без учёта продвижения, сделанного на протяжении поиска в направлении
и т.д.
В случае если в (6) каждые
из
обращаются в нуль, то новые направления отыскивают лишь для тех
направлений, для которых
; остальные
направлений остаются неизменными:
, |
(7) |
Так, векторам с нулевыми
приписываются первые
номеров.
Так как первые
векторов взаимно ортогональны и для
;
, то они не будут иметь составляющих в направлениях
,
. А так как последние направления взаимно ортогональны, то из этого направляться, что все направления являются взаимно ортогональными.
Итак, направления на
-м этапе вычислений определяются следующим образом. Вектор
выбирается так, дабы он совпадал с направлением результирующего перемещения на прошлом этапе
. Остальные направления поиска строятся как взаимно ортогональные к
единичные векторы (ортонормированные). [Описание для того чтобы построения дано в работах по теории матриц и линейной алгебре].
Коротко, без доказательств, комплект ортонормированных векторов
на
-м этапе вычисляется по следующим соотношениям:
, |
(8) |
где
– норма
;
– норма
.
Та же процедура поиска, которая проводилась на
-м этапе повторяется после этого на
-м этапе с точки
.
направляться подчернуть, что способ Розенброка не снабжает автоматического окончания поиска по окончании того, как отыскан экстремум
. Поиск или проводится на определённое число этапов, или заканчивается, когда величина
делается меньше определённого значения на нескольких последовательных этапах. Также, возможно по окончании каждого этапа расстояние
сравнивать с размером шага
.
В случае если
, то
дробят на 10, и предстоящий поиск осуществляется в
прошлых направлениях с новым
.
В случае если
, то поиск длится на
-м этапе, как было поведано выше.
Разглядим числовой пример для иллюстрации способа Розенбока:
Минимизировать
, |
(1п) |
Выбираем начальную точку, к примеру
, вычислим
.
Этап 1: Выбираем направления начального поиска, совпадающими с координатными осями
и
, т.е.
, |
Задаёмся длиной шага
и
. Вводим возмущение в направлении
, вычислим:
, |
т.е. имеем
, т.е. имеет место неудача. Следовательно, умножаем
на
. Вводим возмущение в направлении
, вычислим:
, |
т.е.
, т.е. опять имеет место неудача. Следовательно, на следующем цикле кроме этого
.
Вводим возмущение
в направлении
из последнего успешного значения
, т.е.
.
, |
т.е.
, т.е. имеет место успех. Следовательно:
, где
, т.е.
Вводим возмущение
в направлении
из точки
:
, |
Следовательно, на следующем цикле
.
Потом производятся подобные расчёты на 1-м этапе поиска. Числовые эти по предстоящим циклам 1-го этапа продемонстрируем в следующей таблице (таб.39):
функция и Условный экстремум Лагранжа