Локальный и глобальный экстремумы функций. Нахождение экстремумов методом общего поиска

Рассмотрим две задачи, возникающие при проектировании сетей связи.

Задача 1. Проектируется канал передачи данных с решающей обратной связью. Узел А отправляет информационные пакеты узлу В. Узел В проверяет правильность каждого полученного пакета и при правильном или неправильном приеме отправляет узлу А, соответственно, положительные или отрицательные квитанции. При получении положительной квитанции узел А отправляет следующий пакет, при получении отрицательной - повторяет передачу предыдущего пакета. Каждый пакет состоит из информационной части длиной k символов и проверочной части длиной r символов. Эффективность работы канала передачи данных (КПД) оценивается по относительной скорости передачи R - эквиваленту коэффициента полезного использования пропускной способности канала передачи данных, R = f (k). В самом деле, если k = 0, т.е. информации в пакете нет и он содержит только проверочную часть, то R = 0. При увеличении k будет расти и R. Однако, если k чрезмерно велико, то пакеты имеют большую длину и, при вероятности искажения сообщений в КПД отличной от нуля, будут чаще поражаться ошибками, а, следовательно, и чаще повторяться. Таким образом, при изменении k от 0 до ¥ зависимость R = f (k) будет иметь вид показанный на рисунке 1.

Естественным является желание найти такое значение k, при котором R (k) достигает максимума.

 

Рис. 4.1

Задача 2. Задача о максимальной достоверности передаваемой информации при заданной длине пакета.

Пусть длина пакета составляет n = k + r = const. Очевидно, что k и r могут изменяться от 0 до n. При этом общая длина пакета не должна быть отличной от n. Достоверность определяется вероятностью необнаружения ошибки P _ош. Зависимость P _ош от отношения r/k имеет вид

Рис. 4.2

Требуется найти такое соотношение между r и k, при котором вероятность искажения пакета в канале передачи данных минимальна P^* _ош = min P (r/k).

Видно, что задачи 1 и 2 - задачи поиска экстремума некоторой функции в заданной области изменения ее аргумента (области исследования).

Разрабатывая методы поиска, стремятся найти экстремум как можно быстрее, сделав как можно меньше попыток. В дальнейшем рассмотрим методы поиска экстремума целевой функции - функции одного аргумента (одномерной функции).

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

Рис.4.3

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

Задачу одномерной оптимизации можно поставить следующим образом. Пусть значения переменной x заключены в интервале [ a; b ]. Интервал значений переменной x, в котором производится поиск оптимума целевой функции, будем называть интервалом неопределенности. В начале процесса оптимизации этот интервал имеет длину b-a. Необходимо определить значения оптимума функции с погрешностью e, то есть найти в интервале [ a; b ] точку x, такую что

f (x -e) < f (x) > f (x +e) - при поиске максимума, или

f (x -e) > f (x) < f (x +e) - при поиске минимума.

 

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

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

 

Рис. 4.5

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

Проводя N измерений получим (N +1) частей интервала неопределенности и тогда:

где 2 – осталось частей интервала неопределенности; N +1 – было частей интервала неопределенности.

Чтобы получить значение f _д = 0,01 потребуется вычислить целевую функцию в 199 точках, а при f _д = 0,001 - N =1999. Видно, что эффективность этого метода при уменьшении интервала неопределенности быстро падает. Сам собой напрашивается другой путь: чтобы получить f _д=0,01, вычислим сначала функцию в 19 точках и получим f _д=0,1, а затем, вычислив еще 19 значений на сокращенном интервале получим f _д=0,01, сделав при этом всего 38, а не 199 вычислений. Таким образом, при некоторой изобретательности эффективность поиска можно резко повысить.

Фактически мы перешли от одношагового алгоритма к многошаговому алгоритму.