Методы одномерного поиска

Общая одномерная задача оптимизации формулируется так: найти наименьшее (больше всего) значение целевой функции

в = f(x) (2.3)

определенной на множественном числе допустимых решений задачи :

, и = 1, 2., m, (2.4)

и определить значение управляемого переменного x , при котором целевая функция приобретает искомое экстремальное значение.

Существование решения этой задачи вытекает из следующей теоремы Вейерштрасса:

Всякая функция f(x), непрерывная на отрезке [ а, b ], приобретает на этом отрезке больше всего M и менее всего m значение, то есть существуют такие точки на отрезке [ а, b ] x1 и x2, что для любого [ а, b ] имеет место неравенство:

m = f(x2) - f(x) - f(x1)= M.

Из|с| теоремы не вытекает единственность|единый| решения задачи оптимизации. Не исключается|выключает| возможность, что равные экстремальные значения функции f(x) достигаются сразу в нескольких точках данного отрезка. С этим связаны|повязал| понятия локального и глобального экстремумов (оптимумів|).

Локальным оптимумом называется значение целевой функции, которое есть больше всего (менее всего) в сравнении со значениями во всех других точках ближайшей окружности точки достижения экстремума. У целевой функции может быть несколько локальных экстремумов. Глобальный оптимум лишь один. Глобальным оптимумом называется значение целевой функции, которое есть больше всего (менее всего) в сравнении со значениями во всех других точках области допустимых решений. Да, если температура воздуха измеряется каждый час каждого дня месяца, то для каждого дня будет своя наименьшая и наибольшая температуры – это локальные экстремумы, а наименьшая и наибольшая из них, то есть наименьшая и наибольшая температуры всего месяца – это глобальные экстремумы.

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

Допустимо, что целевая функция является унимодальной, то есть имеет лишь один экстремум в интервале, который рассматривается. Тогда задача одномерного поиска формулируется так: нужно найти такое значение переменной x, которое принадлежит интервалу (а, b), при котором целевая функция f(x) достигает экстремума. Интервал (а, b) называется интервалом неопределенности. Численные методы решения этой задачи направлены на сужение интервала неопределенности к допустимому значению е, где е – это достаточно малое положительное число ().

Интервал неопределенности можно сузить, определив значение целевой функции в двух или в нескольких точках интервала. Существует несколько способов сужения интервала (а, b). При этом процесс распадается на повторение последовательности определенных действий, которая приводит к последовательности интервалов неопределенности (ai, bi), и = 1, 2., n. Количество итераций n определяется достижением такой длины интервала неопределенности (an, bn), которая удовлетворяет неравенства

bn – an < е (2.5)

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

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

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

Интервал неопределенности разделяется на две неравных части таким образом, чтобы отношение длины большего отрезка z1 к длине всего интервала Z равнялось отношению длины меньшего отрезка z2 к длине большего отрезка z1:

Учитывая, что Z = z1 + z2, имеем , откуда 0, 618.

Таким образом z1 = 0, 618 Z, z2 = 0, 382 Z.

В этих точках вычисляются значения целевой функции и избирается одна из двух частей. Интервал неопределенности сужается в 1/0, 618 = 1, 618 разы. Наибольшее сокращение интервала неопределенности достигается при вычислении целевой функции в точках, равноудаленных от центра интервала. Координаты точек определяются так:

x1 = b – 0, 618(b – а) x2 = а + 0, 618(b – а) (2.6)

Вычисляем соответствующие значения функции y1 = f(x1) и y2 = f(x2). Рассматриваем интервалы (а, x2) и (x1, b). Длина каждого из них равняется 0, 618 длины интервала (а, b). Лишь один из них содержит искомый экстремум. Если отыскивается минимум функции, для последующего рассмотрения избирается тот, который содержит меньше из значений y1 и y2. С этим интервалом поступаем так же: разделяем двумя точками, но одна из точек придется на точку предыдущего интервала. То есть нужно будет найти лишь одну точку и значение функции в этой точке. Алгоритм метода «золотого» перерезу приведено выше.

Процесс уточнения следует продолжать, пока длина интервала неопределенности не станет меньше допустимой погрешности ε.

Метод золотого сечения всегда сходится, потому что длина интервалов неопределенности создает геометрическую прогрессию со знаменателем более малым 1: q = 0, 618. Метод золотого сечения есть наиболее экономичним. Он может применяться даже к недиференцируемым функциям и всегда сходится и при том линейно. Если на [ а, b ] функция имеет несколько локальных экстремумов, процесс сходится лишь к одному из них. При отыскании максимума функции в алгоритме в блоке сравнения значений y1 и y2 нужно изменить знак, то есть записать: y1 > y2.

Пример. Найти экстремум функции в = (x – 2)² + 1 на интервале (0; 4).

Во-первых, нужно установить вид экстремума и удостовериться, что на данном интервале лишь один экстремум. Для этого строим график функции:

Таким образом, функция имеет на этом интервале лишь|только| один минимум и можно сократить интервал неопределенности, хотя бы до|до| (1; 4). Расчеты удобно выполнять|исполнять| в среде Excel|. Размещение на листе|листе| Excel начальных|первоначальных| границ|границы| интервала и формул, которые соответствуют алгоритму метода «золотого сечения», может быть таким:

Последняя строка копируется, пока в столбце I не появится число, то есть пока длина интервала неопределенности не станет меньше заданной точности ε.

Будем иметь:

Таким образом, функция достигает своего минимума f(2)= 1 при x = 2. Корень определен с точностью, которая|какая| не превышает половину длины интервала неопределенности, то есть заданной величины ε = 0, 005. Начиная с 14–й| итерации это условие выполняется|исполняет|, а начиная с|с| 17–йй| погрешность становится|стает| меньше, чем 0, 0005. Значение минимума функции почти не изменяется уже начиная с 14–й| итерации.