Основы теории оптимизации (стр. 73 )

Необходимые частные производные целевой функции по независимым переменным. Поскольку в основе метода лежит допущение об унимодальности целевой функции, в тех случаях, когда есть основания допускать, что она не является таковой, необходимо брать несколько входных точек. На рис. 6 представлена схема алгоритма метода Девидона - Флетчера - Пауэлла.

  Рис. 7. Схема алгоритма метода Девидона – Флетчера – Пауэлла

Вначале в пространстве проектирования выбирают пригодную начальную точку. После этого, вычисляя состав вектора градиента определяют направление поиска.

, i = 1, 2, ..., N,

Здесь k – номер итерации, а – элементы симметричной положительно определенной матрицы размерности NN. В процессе итераций эта матрица обращается в матрицу, обратную матрицы Гессе, элементами которой являются вторые частичные производные целевой функции. Поскольку обычно матрица заранее неизвестна, то в качестве начальной можно воспользоваться любой симметричной положительно определенной матрицей. Как правило, берут простейшую из них - единичную матрицу. В этом случае поиск начинается вдоль линии наискорейшего спуска. Одномерный поиск ведется вдоль входного направления в соответствии с соотношением

      (11)

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

    (12)

Элементы матриц и , которые имеют размерность NN и вычисляются по формулам

  (13)

  (14)

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

В соответствии с правилами матричного вычисления числительные выражений для и представляют собой матрицы размерности NN, а знаменатели являются скалярами. Определив новое направление поиска, проводят одномерный поиск и продолжают итерационный процесс. При выполнении алгоритма, который описывается, поиск после первой попытки ведется в тех направлениях, в которых целевая функция в ближайшей окрестности имеет значения, которые приближаются к оптимальному. Лишь в редких случаях эти направления совпадают с направлением градиента. Поэтому данный алгоритм часто называют методом «отклоненного» градиента. Указанное свойство метода Девидона – Флетчера – Пауэлла позволяет обходить трудности, которые связаны с разрывами производных в пространстве проектирования. Считается, что этот метод является наиболее эффективным из всех градиентных методов. В отличие от метода Флетчера – Ривса он дает полную информацию о кривизне поверхности целевой функции в точке минимума, однако при этом требуется больший объем памяти и большее время счета для обработки матрицы .

6.8.5. Метод конфигураций Хука – Дживса

Этот метод облегчает поиск и не требует вычисления производных. Поиск ведется вдоль линий разрыва производных в предположении, что смещения в пространстве проектирования, которые оказались удачными на ранней стадии поиска, могут привести к успеху и на его более поздних стадиях. Метод Хука - Дживса переопределен для поиска минимума унимодальной функции многих переменных

      (15)

при отсутствии ограничений. На рис. 8 представленная схема алгоритма этого метода.

Рис. 8. Схема алгоритма метода конфигураций Хука - Дживса

Выполняется он следующим образом. Вначале выбирается входная базовая точка пространства проектирования и величины шагов, которые будут использованы при исследовании функции. После этого в соответствии со схемой рис. 9 проводится исследование с заданным приростом в направлениях, соответствующих всем независимым переменным. Там, где получено уточненное значение функции, размещают новую временную базовую точку. Закончив этап исследования, выбирают новую базовую точку и выполняют «сдвиги схемы». Эта операция заключается в экстраполяции вдоль линии, которая соединяет новую и бывшую базовые точки. Расстояние сдвига новой базовой точки несколько превышает расстояние между двумя бывшими базовыми точками. Математически экстраполяция определяется формулой (16)

      (16)

где xi,0(k+1) – новая временная базовая точка, или «точка роста», I – переменный индекс, k – порядковый номер стадии поиска, а α – коэффициент усиления, значение которого больше или равно единице. После этого исследуют окрестность новой временной базовой точки, чтобы выяснить, не содержит ли она точку, приняв которую за следующую базовую можно приблизиться к оптимальному решению. Этот поиск также ведется по схеме, которая показана на рис. 9.

  Рис. 9. Алгоритм исследования целевой функции на основе метода Хука-Дживса

Если найденная временная точка роста или одна из соседних с ней точек имеет преимущество перед другими, то вся процедура повторяется с использованием ее в качестве базовой. Благодаря введению коэффициента усиления, каждое следующее исследование окрестности точки осуществляется на все большем и большем отдалении от входной точки до тех пор, пока в процессе поиска не окажется пройденным пик или линия разрыва производной. В этом случае возвращаются к предыдущей «лучшей базовой точке», суживают область исследования и повторяют весь процесс снова. Если шаг, который уменьшается, последовательно оказывается меньшим за некоторую заранее заданную величину и при этом отсутствует заметное изменение значения целевой функции, поиск прекращается. После нескольких изменений направления поиска метод Хука - Дживса обеспечивает совпадение распределения расчетных точек с линией разрыва производных. Обычно после завершения выбора схемы поиска сдвига на каждом следующем шаге увеличивается, пока не превысит величину входного шага в 10 или даже в 100 раз. Поэтому в случае, когда сдвиг оказывается неудачным, единственное средство продолжить поиск - возвратиться к наиболее удачной из базовых точек и начать все сначала. Тот факт, что данный алгоритм обладает свойством «ускоряться», оказывает содействие повышению его общей эффективности. Второе преимущество метода Хука - Дживса - возможность получения с его помощью приближенного решения, качество которого непрерывно повышается на всех стадиях численного решения. Особенно явным образом преимущества подобных средств оказываются при отыскании екстремумов на гиперповерхностях, которые содержат глубокие узкие впадины, т. е. тогда, когда градиентние методы неэффективны.

6.8.6. Метод конфигураций Розенброка

Метод конфигураций Розенброка основан на поиске минимума вдоль линий разрыва производных и часто оказывается эффективным, когда другие методы не позволяют получить решения. Его нередко называют «методом вращения осей координат», поскольку исследование в окрестности выбранной точки ведется именно таким методом. В отличие от предыдущих методов, в которых входным переменным предоставляют независимые приросты, в методе Розенброка система координат поворачивается так, чтобы одна из осей была направлена вдоль линии разрыва производных, положение которой определяется в результате предыдущего исследования. Остальные оси образуют с ней ортогональную систему координат. Метод Розенброка основан на предположении об унимодальности целевой функции и переопределен для отыскания минимума функции многих переменных вида

      (17)

при отсутствии ограничений. На рис. 10 показанная схема алгоритма, который используется в этом методе.

  Рис. 10. Блок-схема алгоритма метода конфигураций Розенброка

Выполняется он следующим образом. Вначале выбирают начальную точку, задают начальные величины шагов и вычисляют целевую функцию. После этого каждой переменной хі дают прирост Si в направлении, параллельном к соответствующей оси координат в пространстве проектирования, и снова вычисляют целевую функцию F . Если ее новое значение оказывается меньшим за предыдущее, то сдвиг считается удачным и следующий шаг увеличивается в соответствии с формулой