Метод розенброка

  • 13 окт. 2013 г.
  • 2214 Слова
Методы безусловной оптимизации


Постановка задачи
Требуется найти вектор [pic]= [pic], доставляющий минимум функции [pic] с заданной точностью ε, используя численный метод решения. Здесь [pic]. Отсутствие ограничений позволяет соотнести задачу с методами безусловной оптимизации.


Особенности поиска экстремума функции многих переменных


Задачи отыскания экстремумов вмногомерном случае существенно осложняются. Возникают следующие качественно новые стороны рассматриваемой задачи:
1. Функция F(X) может иметь сложную форму. Для графической интерпретации поверхности принято изображать ее с помощью линий уровня. Линия уровня – это кривая в 2-х мерном сечении пространства параметров, значение функции, на которой константа. Поверхность, соответствующая зависимостиF(X) может иметь: «овраги» или «гребни» (поверхности уровня имеют структуру, сильно отличающуюся от сферической); «плато» (плоские горизонтальные участки); особые точки типа «седло». Это не имеет себе аналогий в классе одномерных функций. («Седло» – точка гладкой поверхности, вблизи которой поверхность лежит по разные стороны от своей касательной плоскости. В окрестности седла имеются 4 интегральныекривые, которые входят в особую точку. Между ними располагаются интегральные кривые типа гипербол).
2. Если в одномерном случае имеется только два возможных направления поиска, то в многомерном – таких направлений (. В связи с этим центральной проблемой поиска экстремума многомерной функции является проблема выбора направления поиска.
3. Переменные х1, х2, . . . , хn могут быть взаимосвязаны.4. В многомерном случае область допустимых значений имеет бесчисленное множество форм.

Стратегия методов безусловной оптимизации


Все методы решения задач математического программирования можно разбить на прямые и непрямые. Непрямые методы основаны на использовании необходимых и достаточных условий экстремумов и сводятся к решению системы нелинейных уравнений
Методы, несвязанные с использованием необходимых и достаточных условий экстремумов относят к прямым.
Большинство применяемых на практике прямых методов решения задач математического программирования являются итеративными.
В основу этих методов положен механизм порождения последовательности точек [pic] по правилам, которые определены в соответствии с выбранным методом решения и обладают следующими свойствами:▪ [pic]
▪ [pic]


Общее правило построения последовательности [pic] численными методами безусловной оптимизации записывается в виде:
[pic]




Такие методы, как это принято говорить, используют алгоритмы спуска. Здесь [pic] - начальная точка поиска, [pic] - принятое направление перехода из точки [pic] в точку [pic], которое называется направлением спуска, [pic]- числовой множитель, определяющий величину шага.


Стратегия предполагает на очередной итерации следующие шаги:
1. Задание начальной точки поиска, из которой производится спуск к минимуму.
2. Выбор направления поиска очередной точки (на основании исследования локальных свойств целевой ф-ии).
3. Выбор величины шага до новой точки вдоль выбранного направления.4. Переход в очередную точку итерационного процесса.
5. Проверка критерия окончания итерационного процесса.
Выбор начальной точки [pic] производится, исходя из физического содержания решаемой задачи и наличия априорной информации о положении точек экстремума.
Выбор направления и величины шага определяется выбранным методом решения. Проверка критерия окончания итерационногопроцесса дает информацию о том, что либо решение задачи надо продолжить, либо найдена точка, претендующая на роль экстремума и процедуру поиска следует завешить.


Критерии для завершения поиска
На основании сравнения результатов расчетов двух или нескольких последовательных итераций. Наиболее распространены:
1. [pic] (норма разности 2 последовательных итераций)
2. [pic]...
tracking img