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

Точки, удовлетворяющие этому условию, называются стационарными (критическими). Стационарные точки могут быть и точками локального минимума, и точками локального максимума, и точками перегиба. Например, на рисунке точка есть точка перегиба. Для определения характера стационарных точек используется достаточное условие локальной оптимальности.

Достаточное условие локальной оптимальности.

Пусть f(x) дифференцируема в точке k раз, k>1, причем Тогда, если k - четное число, то x* - точка локального минимума при и максимума при .Если k - нечетное число, то x* - точка перегиба.

Отметим, что при прохождении точки минимума знак первой производной меняется с «-» на «+», при прохождении точки максимума знак первой производной меняется с «+» на «-», а при прохождении точки перегиба знак первой производной не меняется.

Используя необходимое и достаточное условия оптимальности, находятся точки локальных экстремумов. Для определения абсолютного минимума есть только один способ: найти все локальные минимумы, сравнить их и выбрать наименьшее значения.

Классификация методов одномерной безусловной оптимизации.

Все численные методы одномерной безусловной оптимизации условно можно сгруппировать следующим образом:
1. Методы исключения интервалов (линейный поиск):

1.1. Метод половинного деления;

1.2. Метод «золотого сечения»;

1.3. Метод Фибоначчи;

2. Метод полиномиальной аппроксимации:

2.1. Метод Пауэлла;

3. Методы с использованием производных:

3.1. Метод секущих;

3.2. Метод качательных.

Первые две группы методов используют только значения функции и не требуют вычисления ее производных и называются методами минимизации нулевого порядка.

Методы исключения интервалов накладывают единственное требование на исследуемую функцию: она должна быть унимодальной. Следовательно, указанные методы можно использовать для анализа как непрерывных, так и разрывных функций, а также в случаях, когда переменные принимают значения из дискретного множества. Логическая структура поиска с помощью методов исключения интервалов основана на простом сравнении значений функции в двух пробных точках. Кроме того, при таком сравнении в расчет принимается только отношение порядка на множестве значений функции и не учитывается величина разности между значениями функции.Большим достоинством этих методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы методов нулевого порядка, это возможность определения значений f(x) в заданных точках, а также, что исследуемая целевая функция в допустимой облас-ти, по крайней мере, обладает свойством унимодальности.

Стр.: 1, ..., 3, 4