Регулярные методы поиска экстремума

Сканирование.

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

о наличии свойства экстремальности и о необходимости соблюдения условия

где х — допустимая область изменения управляемого параметра.

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

Если обозначить допустимый интервал изменения параметра х через А, а заданную точность в достижении экстремума — через то в результате сканирования определяют значений функционала качества в точках

где

После перебора всех значений выбирают максимальное или минимальное значение:

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

При заданной точности количество замеров существенно увеличивается:

Регулярность метода сканирования определяется заранее задаваемым порядком перебора значений. Чаще всего используют два способа при обходе точек: строчная развертка и спиральная развертка (соответственно рис. 11.3 и 11.4). Оба правила обхода обеспечивают просмотр всех допустимых точек без пропусков.

Метод Гаусса—Зайделя. В методе Гаусса—Зайделя используют дополнительную информацию о виде функционала качества в частности предполагают, что является унимодальной функцией, т. е. функцией, имеющей один экстремум.

Рис. 11.3

Рис. 11.4

Условие унимодальности можно записать следующим образом (для поиска минимума):

где — положение минимума; — произвольные положения относительно точки минимума.

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

В основу метода поиска положено исследование полной производной экстремизируемого функционала

где коэффициенты, характеризующие отклонение от экстремума.

Отсюда

В точке экстремума имеем поэтому во всех точках, кроме функция (11.11) должна удовлетворять условию монотонного приближения к экстремуму:

Пример 11.1. Пусть функция качества имеет вид, представленный на рис. 11.5:

где и поиск начинается из точки . Изменяем координату оставив постоянной.

Тогда функция качества

Минимум находим, приравнивая нулю частную производную т.е.

Отсюда первый экстремум по равен

и ему соответствует на рис. 11.5 точка с координатами

Теперь оставим координату х, на уровне — 2,25 и будем изменять

Находим минимум функции по

Данному экстремуму соответствует точка А3 на рис. 11.5 с координатами Повторяем цикл вычислений для координаты закрепляя найденное значение т. е.

В результате поисковых движений получаем ломаную линию, состоящую из взаимно перпендикулярных прямых, точки излома которой находятся в местах касания этих прямых с кривыми:

В методе Гаусса—Зайделя производится поочередное изменение координат и определяются частные экстремумы по каждой из координат, при этом все координаты, кроме выбранной, закрепляются.

Взяв координату при

Рис. 11.5

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

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