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

1) с помощью условия 1 находим все точки возможного экстремума функции f(x) на интервале (а; b), т. е. корни уравнения

f'(x)=0 (5)

(стационарные точки), принадлежащие интервалу (а; b);

2) найденные стационарные точки исследуем в соответствии с условием 2, выделяя из них только точки локальных минимумов f(x);

3) значения f(x) в точках локальных минимумов и на концах отрезка (а; b) сравниваем между собой. Наименьшему из этих значений соответствует точка глобального минимума f(x) на (f(x); b).

Замечание. Применение условия 2 требует вычисления высших производных функций f(x), поэтому в большинстве случаев бывает проще сравнить значения f(x) во всех стационарных точках, не интересуясь их характером. С учетом этого можно предложить следующий алгоритм минимизации f(x) на отрезке (а; b) (классический метод).

Шаг 1. Решить уравнение (5) на интервале х (а; b), т. е. найти все стационарные точки Положить x0=a, xk =b.

Шаг 2. Вычислить значения f(xi) функции f(x) в точках xi, i = 0,...,k.

Шаг 3. НайтиПоложить х* = хт.

Пример 1. Классический метод минимизации.

Решить задачу

Шаг 1. Находим корни уравнения из интервала (-2; 2): х1 =-1, х2=1. Полагаем х0=-2, х3=2.

Шаг 2. Вычисляем значения f(х) в точках хi, i = 0,...,3 :

Шаг 3. Находим Поэтому х* =х0=-2, f* =-17.

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

Изучение методов одномерной минимизации имеет самостоятельное значение. Эти методы являются существенной составной частью методов многомерной оптимизации при помощи которых находят наименьшее значение действительных функций многих переменных.

Для существования минимума f(х) в D(f) необходимо и достаточно, чтобы f(х) была непрерывна, a D(f) - конечным отрезком. Однако при нарушении этих условий (f(х) имеет в D(f) точки разрыва или D(f) -интервал или полуинтервал), наименьшее значение может и не достигаться в D(f). В этом случае отыскиваетсят. е. под решением задачи минимизации такой функции на D(f) следует понимать построение последовательности {хп} точек из D(f), для которых существует

Пример. Найти минимум Функция не достигает наименьшего значения на D(f), хотя и ограничена снизу

В качестве последовательности {хп} точек из полуинтервала [1;2) выберемТогда

Функция может достигать наименьшего значения, как в единственной точке, так и на некотором множестве точек, конечном, счётном или несчётном. Фактически, количество значений точек минимума зависит от того, является ли f(x) сильно выпуклой, строго выпуклой или просто выпуклой.

Аналогом выпуклых функций в одномерном случае является унимодальная функция. Функция f(x) называется унимодальной на отрезке [a;b], если она непрерывна на [a;b]и существуют числа α и β, а ≤α≤β≤ b, такие, что:

1) если а < α, то f(x) монотонно убывает при

2) если

3) если β < b то f(x) монотонно возрастает при

Множество унимодальных на отрезке [a;b] функций мы будем обозначать через Q[a;b].

Отметим, что возможно вырождение в точку одного или двух отрезков из Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на рис. 2.

Рис. 2. Графики унимодальных функций

Известны следующие основные свойства унимодальных функций.

1. Любая из точек локального минимума унимодальной функции является и точкой её глобального минимума на отрезке [a;b].

2. Функция унимодальная на отрезке [a;b] является унимодальной на любом меньшем отрезке [c;d] [a;b].

где х* - одна из точек минимума f(x) на отрезке [a;b].

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

При решении практических задач оптимизации классический метод имеет ограниченное применение. Это объясняется тем, что, во-первых, во многих случаях значения целевой функции f(x) находятся из измерений или экспериментов, а измерение производной f'(x) затруднительно или невозможно и, во-вторых, даже когда производная f'(x) задана аналитически или поддается измерению, решение уравнения (5) зачастую вызывает затруднения.

2.2.2. Постановка задачи одномерной минимизации

Рассмотрим задачу безусловной минимизации функции одного переменного:

Требуется найти т. х* R такую, что

Ф(х*) =min Ф(х) х* Ф(х) loc Ф(х). (6)

Если функция Ф(х) С2(R) дважды непрерывно дифференцируема, то известны необходимое и достаточное условия минимума

необходимое достаточное

условия условия

экстремума экстремума (7)

Ф′(х*)=0 Ф′= (х*)

Ф′′ (х*)≥0 Ф′′ (х*)>0

(Взятые по отдельности – это соответствующие условия оптимальности точки х* первого и второго порядков как необходимые, так и достаточные)

В таком стучае, при нахождении в достаточно малой окрестности точки х*, разложение целевой функции в ряд Тейлора с центром в точке х* имеет вид

Ф(х*+h)= Ф(х*)+ Ф′(х*)h+ Ф′′ (х*) h2+o(h2).

В этом выражении Ф′(х*)h≡0 в силу (7)

Мы говорим о невырожденности минимума в точке х*, если Ф′′ (х*) ≠0, тем самым, согласно (7), Ф′′ (х*)>0. В дальнейшем будем предполагать это условие выполненным.

Подчеркнем еше раз, что мы пытаемся рассмотреть способы минимизации задачи (6), а не решение задачи (7) из необходимого условия экстремума. Хотя, конечно, это тесно связанные проблемы.

3. Методы одномерной минимизации нулевого порядка (прямые методы)

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

Предположим что точки а и b определяют возможно и достаточно грубо, интервал, где расположено значение точки минимума х* задачи

Ф(х*) =min Ф(х) х* Ф(х) loc Ф(х).