Алгоритм градиентного метода

Идея градиентного метода: если заранее известно, что функция Алгоритм градиентного метода - student2.ru имеет в допустимой области единственный экстремум, то поиск точки, в которой он достигается, целесообразнее проводить следующим образом. В допустимой области взять производную функции в точке Алгоритм градиентного метода - student2.ru и с помощью градиента (антиградиента) определить направление, в котором целевая функция Алгоритм градиентного метода - student2.ru возрастает (убывает) с наибольшей скоростью.

Алгоритм градиентного метода - student2.ru

Рис.7.3. Поиск экстремума градиентным методом

Сделав наибольший шаг в найденном направлении, перейти в новую точку Алгоритм градиентного метода - student2.ru . Потом снова определить наилучшее направление для перехода в очередную точку Алгоритм градиентного метода - student2.ru и т. д., иначе говоря, надо построить последовательность точек Алгоритм градиентного метода - student2.ru так, чтобы она сходилась в точке экстремума Алгоритм градиентного метода - student2.ru , т.е. для точек последовательности выполнялись условия

Алгоритм градиентного метода - student2.ru Алгоритм градиентного метода - student2.ru Алгоритм градиентного метода - student2.ru

Величина шага из точки Алгоритм градиентного метода - student2.ruпо направлению градиента Алгоритм градиентного метода - student2.ru (антиградиента - Алгоритм градиентного метода - student2.ru ) определяется значением параметра Алгоритм градиентного метода - student2.ru в уравнении прямой

Алгоритм градиентного метода - student2.ru , Алгоритм градиентного метода - student2.ru(7.9)

Методы поиска экстремума, основанные на построении последовательности точек Алгоритм градиентного метода - student2.ru , называют шаговыми или итерационными. Эти методы различаются способом выбора направления движения Алгоритм градиентного метода - student2.ru и способом выбора шага Алгоритм градиентного метода - student2.ru , от этого зависит сходимость методов.

Большое значение имеет также выбор начальной точки Алгоритм градиентного метода - student2.ru .

В качестве критериев прекращения итерационного процесса, свидетельствующих о достижении достаточной близости последней точки последовательности Алгоритм градиентного метода - student2.ru к точке экстремума Алгоритм градиентного метода - student2.ru , могут использоваться или модуль градиента

Алгоритм градиентного метода - student2.ru , (7.10)

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

Значения критериев сравниваются с достаточно малыми положительными числами Алгоритм градиентного метода - student2.ru , соответствующими требуемой точности решения.

Признаком прекращения итерационного процесса служит выполнение неравенства

Алгоритм градиентного метода - student2.ru . (7.11)

Используя градиентные методы, можно найти решение любой задачи нелинейного программирования. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач выпуклого программирования, в которых всякий экстремум является одновременно и глобальным. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что, начиная с некоторой точки Алгоритм градиентного метода - student2.ru , осуществляется последовательный переход к некоторым другим точкам до тех пор, пока не выявляется приемлемое решение исходной задачи. При этом градиентные методы могут быть подразделены на две группы.

К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. Наиболее распространенным из таких методов является метод Франка-Вулфа.

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

Остановимся более подробно на методах Франка-Вулфа, штрафных функций и Эрроу-Гурвица.

Метод Франка-Вулфа

Пусть требуется найти максимальное значение вогнутой функции

Алгоритм градиентного метода - student2.ru (7.12)

при условиях

Алгоритм градиентного метода - student2.ru (7.13)

Алгоритм градиентного метода - student2.ru (7.14)

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

Процесс нахождения решения задачи начинают с определения точки, принадлежащей области допустимых решений задачи. Пусть это точка Алгоритм градиентного метода - student2.ru , тогда в этой точке вычисляют градиент функции (7.12)

Алгоритм градиентного метода - student2.ru

Алгоритм градиентного метода - student2.ru (7.15)

и строят линейную функцию

Затем находят максимальное значение этой функции при ограничениях (7.13) и (7.14). Пусть решение данной задачи определяется точкой Алгоритм градиентного метода - student2.ru . Тогда за новое допустимое решение исходной задачи принимают координаты точки Алгоритм градиентного метода - student2.ru :

Алгоритм градиентного метода - student2.ru , (7.16)

где λk – некоторое число, называемое шагом вычислений и заключенное между нулем и единицей Алгоритм градиентного метода - student2.ru . Это число λk берут произвольно или определяют таким образом, чтобы значение функции в точке Алгоритм градиентного метода - student2.ru Алгоритм градиентного метода - student2.ru зависящее от λk, было максимальным. Для этого необходимо найти решение уравнения Алгоритм градиентного метода - student2.ru и выбрать его наименьший корень. Если его значение больше единицы, то следует положить λk=1. после определения числа λk находят координаты точки Алгоритм градиентного метода - student2.ru , вычисляют значение целевой функции в ней и выясняют необходимость перехода к новой точке Алгоритм градиентного метода - student2.ru . Если такая необходимость имеется, то вычисляют в точке Алгоритм градиентного метода - student2.ru градиент целевой функции, переходят к соответствующей задаче линейного программирования и находят ее решение. определяют координаты точки Алгоритм градиентного метода - student2.ru и исследуют необходимость проведения дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.

Итак, процесс нахождения задачи (7.12)-(7.13) методом Франка-Вулфа включает следующие этапы:

1. Определяют исходное допустимое решение задачи.

2. Находят градиент функции (7.12) в точке допустимого решения.

3. Строят функцию (7.15) и находят ее максимальное значение при условиях (7.13) и (7.14).

4. Определяют шаг вычислений.

5. По формулам (7.16) находят компоненты нового допустимого решения.

6. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи (7.5).

Метод штрафных функций

Рассмотрим задачу определения максимального значения вогнутой функции Алгоритм градиентного метода - student2.ru

при условиях Алгоритм градиентного метода - student2.ru

Алгоритм градиентного метода - student2.ru ,

где Алгоритм градиентного метода - student2.ru - выпуклые функции.

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

Алгоритм градиентного метода - student2.ru ,

которая равна сумме целевой функции задачи, и некоторой функции Алгоритм градиентного метода - student2.ru . Функция Алгоритм градиентного метода - student2.ru , определяемая системой ограничений, называется штрафной функцией. Штрафную функцию можно построить различными способами. Однако наиболее часто она имеет вид

Алгоритм градиентного метода - student2.ru , (7.17)

где Алгоритм градиентного метода - student2.ru , (7.18)

а аi>0 – некоторые постоянные числа, представляющие собой весовые коэффициенты.

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

Алгоритм градиентного метода - student2.ru (7.19)

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

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

1. Определяют исходное допустимое решение.

2. Выбирают шаг вычислений.

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

4. По формуле (7.19) находят координаты точки, определяющей возможное новое решение задачи.

5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу. Если координаты найденной точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему допустимому решению. В случае такой необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.

6. Устанавливают значения весовых коэффициентов и переходят к этапу 4.

Наши рекомендации