Методы Оптимизации Систем Автоматизированного Проектирования

Главная

Классификация задач

Безусловная оптимизация

Условная оптимизация

Глоссарий

Карта сайта

Классификация методов.

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

Общая характеристика методов нулевого порядка.

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

, вдоль которой целевая функция убывает:

Общая характеристика методов первого порядка.

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

разумно перейти в точку

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

в точке

, получаем итерационный процесс вида

В координатной форме этот процесс записывается следующим образом:

i = 1, ..., n; k= 0, 1, 2,...
В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента

, либо выполнение условия малости градиента

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

Градиентные методы отличаются друг от друга способами выбора ве-личины шага

Методы одномерной оптимизации:

-Основные определения
-Метод половинного деления
-Метод "Золотого сечения"
-Метод Фибоначчи
-Метод Пауэлла
-Метод секущих
-Метод касательной

Методы многомерной оптимизации:

Основные понятия и определения
-Основные определения
-Условия экстремума задачи безусловной оптимизации
-Принципы построения численных методов
-Классы функций
-Классификация методов

Методы нулевого порядка

-Метод конфигурации Хука-Дживса
-Метод деформированного многогранника

Методы первого порядка

-Метод градиентного спуска
-Метод наискорейшего спуска
-Метод наискорейшего покоординатного спуска
-Метод сопряженных градиентов

Методы второго порядка

-Метод Ньютона
-Метод Ньютона-Рафсона
-Метод Левенберга-Марквардта