Материал: Основы проектирования Р Э С. Комплект учебно-методической документации по дисциплине. Учебное пособие. Самойленко Н.Э., Скоробогатов В.С

В общем виде (3.25) можно записать:

градиентных методах используется, как правило, комбинация двух условий: Ф(Xk+1 ) - Ф(X k) или

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

3.9. 3. Градиентный метод с дроблением шага

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

Исходными данными являются требуемая точность ,

108

начальная точка поиска Х0 и начальная величина шага поиска h (обычно h=1). Получение новых точек производится по формуле:

где hk – величина шага на k-ой итерации поиска, при hk должно выполняться условие:

107

Ф( Хk – hk grad Ф(Хk) ) Ф(Хk) - hk grad Ф(Хk) 2. (3.27)

Если величина hk такова, что неравенство (3.6) не выполнено, то производится дробление шага до тех пор, пока данное условие не будет выполнено. Дробление шага выполняется по формуле hk = hk , где 0 1.Такой подход позволяет сократить число итераций, но затраты на проведение одной итерации при этом несколько возрастают.

3.9.4. Метод наискорейшего спуска

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

где hk = arg min Ф(Хk – hk grad Ф(Хk)), 0<h<

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

109

наискорейшего убывания целевой функции, то есть в направлении вектора-антиградиента функции Ф(Х) в точке Хk

При выборе оптимальной величины шага необходимо из множества ХМ={ Х Х= Хk–h grad Ф(Хk), h [0, ) } точек, лежащих на векторе градиенте функции Ф(Х), построенном в точке Хk выбрать ту, где функция

Ф( h ) = Ф(Хk – h grad Ф(Хk)) принимает минимальное значение.

Таким образом, метод наискорейшего спуска нашел точку минимума целевой функции за одну итерацию ( из-за того, что линии уровня функции Ф(x1, x2)=(x1 – 1)2 + ( x2 – 2)2 окружности(x1 – 1)2 + (x2–2)2 const, и вектор антиградиент из любой точки точно направлен в точку минимума – центр окружности). На практике целевые функции гораздо более сложные, линии также имеют сложную конфигурацию, но в любом случае справедливо следующее: из всех градиентных методов в методе наискорейшего спуска наименьшее число итераций, но некоторую проблему представляет поиск оптимального шага численными методами, так как в реальных задачах, возникающих при проектировании РЭС применение классических методов нахождения экстремума практически невозможно. Численные методы однопараметрической (одномерной) оптимизации содержатся в разделе 3.5 данного пособия.

З. 9. 5. Двухуровневый адаптивный метод

Для задач оптимизации в условиях неопределенности

110

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

Исходными данными являются требуемая точность , начальная точка поиска Х0 и начальная величина шага поиска h (обычно h=1 ). Получение новых точек производится по формуле:

где шаг hk+1 может быть рассчитан по одной из двух формул: hk+1 = hk+ k+1 k, или hk+1 = hkexp(k+1 k). В качестве понижающего коэффициента выбирают обычно k=1/k, где k- номер итерации поискового метода.

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

k=sign{(grad Ф(Хk),grad Ф(Х))},

то есть k – это знак скалярного произведения векторов

градиентов целевой функции в точках Хk и Х, где

Х=Хk – hkgrad Ф(Хk) пробная точка, а hk- это шаг , который был использован для получения точки Хk на предыдущей итерации метода

(рис. 3.6).

111

Знак скалярного произведения двух векторов позволяет оценить величину угла между данными векторами ( обозначим этот угол ). Если 9, то скалярное произведение должно быть положительным, в противном случае – отрицательным. С учетом вышеизложенного нетрудно понять принцип корректировки величины шага в двухуровневом адаптивном методе: Если угол между антиградиентами (острый угол), то направление поиска из точки Хk выбрано правильно, и величину шага

Если же угол между антиградиентами (тупой угол), то направление поиска из точки Хk удаляет нас от точки минимума Х*, и шаг нужно уменьшить Метод носит название двухуровневого, так как на каждой

итерации поиска анализируются не одна, а две точки (Xk и

Х) и строятся два вектора антиградиента. Это, конечно, увеличивает затраты на проведение одной итерации, но позволяет проводить адаптацию (настройку) величины шага hk+1 на поведение случайных факторов.

З. 10. Методы поиска второго порядка

Несмотря на простоту реализации метод наискорейшего спуска не рекомендуется в качестве ―серьезной‖ оптимизационной процедуры для решения задачи безусловной оптимизации функции многих переменных, так как для практического применения он работает слишком медленно. Причиной этого является тот факт, что свойство наискорейшего спуска является локальным свойством, поэтому необходимо частое изменение направления поиска, что может привести к

112

неэффективной вычислительной процедуре.

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

Формула (3.30) представляет собой первые три члена разложения функции Ф(Х) в ряд Тейлора в окрестности точки Х0, поэтому при

аппроксимации функции Ф(Х) функцией (Х) возникает ошибка не более чем Х-Х0 3.

С учетом (3.30) в методе Ньютона исходными данными

где G-1(Хk) – матрица, обратная к матрице Гессе, вычисленная в точке

113

Главным недостатком метода Ньютона являются затраты на вычисление обратного гессиана G-1(Хk) на каждой итерации метода.

В методе Давидона – Флетчера - Пауэлла (ДФП) преодолены недостатки как метода наискорейшего спуска, так и метода Ньютона / 6 /.

Достоинством данного метода является то, что он не требует вычисления обратного гессиана, а в качестве направления поиска в методе ДФП выбирается

направление -НkgradФ(Хk), где Нk - положительно определенная симметричная матрица, которая заново рассчитывается на каждой итерации (шаге метода поиска) и приближает обратный гессиан G-1(Хk)

(Нk G-1(Хk) с увеличением k). Кроме того, метод ДФП при его применении для поиска экстремума функции n переменных сходится (то есть дает решение) не более чем за n итераций.

Вычислительная процедура метода ДФП включает следующие шаги. Исходными данными являются требуемая точность , начальная точка поиска Х0 и начальная матрица

Н0 (обычно единичная матрица, Н0 = I ).

1.На k-ой итерации метода известны точка поиска Хk

иматрица Нk (k=0,1,…).

2.Обозначим направление поиска dk = -Нk gradФ(Хk).

направлении dk с помощью методов одномерной оптимизации (так же, как в методе наискорейшего спуска выбиралась величина в направлении ветора антиградиента)

З. Обозначим vk= k dk и получим новую точку поиска

Хk+1=Xk + vk.

114

4.Проверяем выполнение условия прекращения поиска . Если

vk или gradФ (Хk+1) , то решение найдено Х*= Хk+1. В

противном случае продолжаем вычисления.

5. Обозначим uk = gradФ(Хk+1)- gradФ(Хk) и матрицу Нk+1

является скалярная величина (число), а умножение столбца на строку дает матрицу размера nxn).

6. Увеличиваем номер итерации на единицу и переходим к пункту 2 данного алгоритма.

Метод ДФП – это мощная оптимизационная процедура, эффективная при оптимизации большинства функций. Для одномерной оптимизации величины шага в методе ДВП используют методы интерполяции / 6 /.

3.10 Методы оптимизации функции одной переменной

3.10.1. Метод квадратичной интерполяции

Метод квадратичной интерполяции (метод Пауэлла) заключается в приближенной замене целевой функции одной переменной f() квадратичной функцией 2 С. Для вычисления коэффициентов А, В, С квадратичной функции необходимо знать значения аппроксимируемой функции f() в трех точках 1, 2, 3:

В точке минимума * квадратичной функции/ *=0 и // *>0, поэтому *= -В/ (2А) при А>0. Решив систему уравнений (3.12) и подставив выражения величин А, В,

и С в формулу для *, получим

Рассмотрим основные шаги метода Пауэлла.

1. Исходными данными являются требуемая точность и величина h.

2.Точку 1 задаем произвольно и, по возможности, ближе

кточке минимума * , 2= 1+h , а чтобы выбрать

третью точку 3 сравним f(1) и f(2) (рис.3.8). Если f(1)< f(2), то 3=1-h, в противном случае 3=1+2 h, вычисляем f(3),

3.По формуле (3.13) находим *1.

4.Проверим, можно ли точку * считать точкой минимума

с точностью , то есть f(*k+1)-f(*k) ,

k=0,1, ... На первой итерации считаем, что *0 = 1. Если условие прекращения поиска выполнено, то задача решена и*= *k+1. В противном случае продолжаем вычисления.

4.Из имеющихся четырех точек 1, 2, 3, * выбираем три наиболее близких к точке минимума целевой функции f() точки , , . Чтобы получить точки ,

, из точек 1, 2, 3, *, достаточно исключить точку с наибольшим значением функции f(1), f(2),

116

f(3), f(*), а затем проверить для трех оставшихся точек выполнение условия < < , f( )>f( ), f( )<f( ).

6. В полученных точках 1= , 2= , 3= вычисляем f(1), f(2), f(3) и переходим к пункту 3.

3.10.2. Метод кубической интерполяции

Метод кубической интерполяции (метод Давидона) обеспечивает большую точность при выборе оптимальной величины шага в методах наискорейшего спуска и ДФП по сравнению с методом квадратичной интерполяции. Целевая функция одной переменной f() аппроксимируется функцией С 2D3. Для вычисления коэффициентов А, В, С, D кубического полинома необходимо знать значения аппроксимируемой функции f() и ее производной в двух точках p и q (fp=f(p), fq=f(q), Gp=f / (p), Gq=f /(q))

и решить систему уравнений: p fp

q fq/q Gq .

Рассмотрим основные шаги метода кубической интерполяции.

1. Исходными данными является требуемая точность метода . 2.Точки p и q задаем так, чтобы интервал (p,q)содержал точку минимума функции f( ). Выбираем p=0 и проверяем, справа или слева от точки p находится точка минимума * (если f / (p)<0, то функция убывает и минимум находится справа от p, в противном случае – возрастает, и минимум – слева от p). Точку q выбираем в направлении убывания функции. Теперь нужно подобрать расстояние от q до p (p=0) так, чтобы p,q . Для этого задают произвольно

величину q и проверяют, выполнено ли хотя бы одно из условий f