Теория оптимизаций. ТЕОРИЯ ОПТИМИЗАЦИИ общий конспект лекций. Общие сведения о теории оптимизации

• Название: Общие сведения о теории оптимизации
• Анкор: Теория оптимизаций
• Дата: 25.01.2022
• Размер: 2.93 Mb.
• Имя файла: ТЕОРИЯ ОПТИМИЗАЦИИ общий конспект лекций.doc
• Тип: Лекция; #342116
• страница: 9 из 10

Тема 4 Градиентные методы оптимизации
За основу материалов лекций по данной теме взяты рукописные тексты лекций заведующей кафедры математики Ростовского военного института ракетных войск Абаниной Т.И.
Лекция 7 Сущность градиентных методов
7.1 Теоретические основы градиентных методов
Градиентные методы представляют собой одну из наиболее распространённых групп методов поиска экстремального значения (то есть минимума или максимума) нелинейной функции нескольких переменных и относятся к численным итерационным методам.

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

В этом случае функцию можно изобразить, как это показано на рис. 1, в трёхмерной системе координат в виде поверхности типа котловины.

Рис.1. Геометрическая интерпретация
На каждом шаге процедуры поиска минимума движение

к точке рассматриваемого экстремума осуществляется в направлении антиградиента функции .

С геометрической точки зрения каждый такой шаг происходит в направлении, перпендикулярном линиям уровня

Как известно, градиентом функции f(X) = f(x₁,…, x_n) называется вектор, проекциями которого служат значения частных производных этой функции.

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



элементы вектора-столбца называют

координатами градиента.

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

.
Вектор-антиградиент – f(X) (с отрицательным знаком)указывает направление наибольшего убывания функции f(X).

В силу необходимого условия экстремума в точке

экстремума все частные производные первого порядка равны нулю:

, ,…, ,

иначе говоря, .

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

Для рассмотрения сущности градиентных методов поиска экстремума найдём путём разложения в ряд Тейлора с удержанием первых членов ряда до второго порядка включительно квадратичную аппроксимацию функции f(x) в окрестности точки предполагаемого экстремума.

Так как в точке в силу необходимого условия экстремума все частные производные первого порядка равны нулю, в получаемом соотношении члены первого порядка будут отсутствовать, то есть остаются лишь члены второго порядка:

где .
Вычислим производные функции f(X) по .

С учётом того, что



а также того, что в записанном таким образом соотношении содержатся при ( ) по n – 1 пар производных вида

и ,

в сумме равных , и одна производная (при ) вида , также равная , находим координаты градиента в рассматриваемой точке:



а сам градиент при его записи в матричной форме имеет вид

где А – квадратная симметричная матрица размерности с элементами .

Решая записанное в матричной форме уравнение относительно находим

,

где – матрица, обратная матрице А.

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

Поэтому матрицу , обратную матрице А, заменяют матрицей Г, получаемой более простым способом.

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

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

где .

Здесь – приращение k-го шага, – градиент в точке начала k-го шага.

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

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

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


это означает, что в этом случае матрица является диагональной с элементами на главной диагонали:

,

где диагональная матрица с элементами главной диагонали, равными 1.

При методе градиентного спуска на k-м шаге поправка (являющаяся величиной шага) имеет вид


а процедура определения новой точки при поиске экстремума записывается как


Алгоритм метода градиентного спуска описывается схемой, приведенной на рис. 1.



Рис.2. Алгоритм процедуры поиска минимума функции методом градиентного спуска

На рис.1 указана соответствующая ГОСТу [2] нумерация блочных символов, обычно используемая для ссылок на те или иные элементы при пояснении схемы алгоритмов.

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

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

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

8.2.2 Метод градиентного спуска

с постоянным шагом
При таком методе величину шага стремятся сделать независимой от значения градиента. Поправка в этом случае определяется формулой



где – единичный вектор направления градиента, длина которого является независимой от k. Итерационный процесс завершается, когда нарушается движение к оптимуму, проверяемое по вычисляемому после каждого шага изменению значения функции.

Оба рассмотренных простейших метода градиентного спуска имеют следующие недостатки:

может быть слишком много шагов;

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

на каждом шаге необходимо заново определять направление градиента, что требует значительного времени.

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

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

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

ВОПРОСЫ ДЛЯ САМОКОТРОЛЯ