Методы поисковой оптимизации (стр. 2 из 2)

Каждая из формул (2.6), (2.7) является векторным соотношением, включающим n уравнений. Например, с учетом Х^k+1 = ( x1^k+1, x2. ^k+1,…,xn^k+1), Х^k = ( x1^k, x2. ^k,…,xn^k) формула (2.6) примет вид:

или в скалярном виде

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

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

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

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

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

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

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

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

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

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

Исходными данными являются требуемая точность e, начальная точка поиска Х⁰.

Получение новых точек производится по формуле:

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

Основная идея метода наискорейшего спуска заключается в том, что на каждой итерации метода выбирается максимально возможная величина шага в направлении наискорейшего убывания целевой функции, то есть в направлении вектора-антиградиента функции Ф(Х) в точке Х^k ( рис. 2. 4).

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

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

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

Несмотря на простоту реализации, метод наискорейшего спуска не рекомендуется в качестве “серьезной” оптимизационной процедуры для решения задачи безусловной оптимизации функции многих переменных, так как для практического применения он работает слишком медленно. Причиной этого является тот факт, что свойство наискорейшего спуска является локальным свойством, поэтому необходимо частое изменение направления поиска, что может привести к неэффективной вычислительной процедуре. Более точный и эффективный метод решения задачи параметрической оптимизации (1.5) можно получить, используя вторые производные целевой функции (методы второго порядка). Они базируются на аппроксимации (то есть приближенной замене) функции Ф(Х) функцией j(Х),