Нахождение безусловного экстремума функции нескольких переменных градиентными методами (стр. 1 )

работа №1.

“Нахождение безусловного экстремума функции нескольких переменных градиентными методами”.

Цель работы: знакомство с градиентными методами нахождения безусловного экстремума.

Работа выполняется с использованием алгоритмических языков высокого уровня.

Одной из важнейших задач анализа является задача отыскания экстремума (наибольшего или наименьшего значения) скалярной функции f (x), n - мерного векторного аргумента x при некоторых ограничениях. Эту задачу будем записывать следующим образом:

(1)

(2)

Здесь X - некоторое подмножество евклидового пространства En. Будем называть X допустимым множеством задачи , а точки, принадлежащие X, - ее допустимыми точками [1].

Задачу максимизации функции f (x) также можно записать в виде , заменив f (x) на .

Точка x*ÎX доставляет глобальный минимум функции f (x) на множестве X, если при некотором достаточно малом e>0 для всех X не равных x*, x Î X и удовлетворяющих условию.

выполнено неравенство

Если допустимое множество X составляет n - мерное пространство (X = En), то имеет место задача безусловной минимизации функции нескольких переменных.

Будем предполагать, что f (x) имеет в окрестности исследуемой точки непрерывные первую и вторую производные. Тогда имеет место теорема 1:

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

(3)

Вес точки , удовлетворяющее условию называются стационарными .

Условие стационарности (3) записывают также в виде

(4)

n - мерный вектор с константами - градиент функции f (x) в точке .

Так как предполагается, что функция f (x) дважды непрерывно дифференцируема по всем переменным, то существует матрица ее вторых производных - матрица Гессе.

Выражение вида:

(6)

называется квадратичной формой.

Имеет место следующая теорема [1] (теорема 2):

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

Если X - вектор размерности n, а A - квадратная симметричная матрица порядка n x n, то квадратичная форма имеет вид .

Если все главные миноры матрицы A положительны,

т. е. то матрица A и соответствующая ей квадратичная форма называется положительно определенными.

Алгоритмы численных методов отыскания безусловного экстремума функции n переменных основаны на использовании приведенных выше теорем. При этом находится последовательность векторов {Xk}, при которых

Такая последовательность называется релаксационной, а методы ее построения - методами спуска.

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

*  методы нулевого порядка (методы поиска) - используют значение самой функции;

*  методы первого порядка требуют кроме того вычисления первых производных минимизируемой функции и т. д.

Градиентные методы являются методами первого порядка.

Градиент скалярной функции f (x) в некоторой точке xk направлен в сторону наискорейшего возрастания функции.

Антиградиент - вектор, противоположный градиенту , направлен в сторону наискорейшего убывания функции.

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

(6)

Итерационные процессы, в которых направление движения на каждом шаге совпадает с градиентом (антиградиентом), называются градиентными методами.

Градиентные методы отличаются выбором шага a:

*  методы с постоянным шагом;

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

Удобнее при поиске экстремума использовать не антиградиент - а нормированный антиградиент[2]

где

В этом случае формула (5) примет вид

(7),

где

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

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

(8)

где 0<e<1

Если на какой - то итерации условие (8) выполняется, переходим к следующей итерации. В противном случае дробим шаг ak (делим пополам) до тех пор, пока условие (8) не будет выполнено.

Итерационный процесс (7) заканчивается, при выполнении условия где e1 - заданная точность вычислений (в точке экстремума градиент равен нулю).

Задание на работу №1.

Найти безусловный экстремум функции двух переменных с заданной точностью e1:

*  градиентным методом с постоянным шагом для двух различных значений ak;

*  градиентным методом с дроблением шага при заданном e.

Начальные значения: X1=10; X2= - 10.

Результаты вычислений свести в таблицы вида:

а) Таблица 1,1: Итерационный процесс нахождения безусловного экстремума градиентным методом с постоянным шагом a=a1, a2.

Итерация
0 1	10	10

б) Таблица 1,2. Итерационный процесс нахождения безусловного экстремума градиентным методом с дроблением шага.

N ите-рации	N ша-га
0	0	10	10

Итерационный процесс поиска экстремума с постоянным шагом прекратить, если число итераций превышает 100.

Варианты заданий.

N
1		1	0,8	1	0,5	0,001
2		1	0,7	1	0,6	0,001
3		1	0,6	1	0,7	0,001
N
4		1	0,5	1	0,8	0,001
5		1	0,4	1	0,9	0,001
6		1	0,3	1	0,5	0,001
7		1	0,2	1	0,6	0,001
8		1	0,1	1	0,7	0,001
9		1	0,8	1	0,8	0,001
10		1	0,7	1	0,9	0,001
11		2	0,6	2	0,5	0,005
12		2	0,5	2	0,6	0,005
13		2	0,4	2	0,7	0,005
14		2	0,3	2	0,8	0,005
15		2	0,2	2	0,9	0,005
16		2	0,1	2	0,5	0,005
17		2	0,8	2	0,6	0,005
18		2	0,7	2	0,7	0,005
19		2	0,6	2	0,8	0,005
20		2	0,5	2	0,9	0,005
21		1	0,8	1	0,5	0,001
22		1	0,7	1	0,6	0,001
23		1	0,6	1	0,7	0,001
24		1	0,5	1	0,8	0,001
25		1	0,8	1	0,8	0,001

Методика выполнения работы.