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

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

 

 

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

 

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

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

, (7.9)

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

Большое значение имеет также выбор начальной точки .

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

, (7.10)

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

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

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

. (7.11)

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

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

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

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

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

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

(7.12)

при условиях

(7.13)

(7.14)

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

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

(7.15)

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

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

, (7.16)

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

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

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

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

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

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

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

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

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

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

при условиях

,

где - выпуклые функции.

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

,

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

, (7.17)

где , (7.18)

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

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

(7.19)

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

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

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

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

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

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

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

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