Безусловная оптимизация

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО

ДИСЦИПЛИНЕ «ЭКОНОМИКО-МАТЕМАТИЧЕСКИМ МЕТОДАМ И МОДЕЛИРОВАНИЮ В ЗЕМЛЕУСТРОЙСТВЕ»

МЕТОДЫ ПОИСКА ЭКСТРЕМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ.

БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ

ЗАДАНИЕ 1. Дана функция: .

В области определения найти ее минимум.

1. Находя производную и решая уравнение

а). методом половинного деления;

б). методом хорд;

в). методом касательных (Ньютона).

Точность вычислений .

2. Не производя дифференцирования функции , организовать процедуры:

а). методом половинного деления;

б). методом золотого сечения.

Точность вычислений .

Коэффициенты по вариантам заданий приведены в в таблице:

№ Варианта
			-1
		-2
		-1
			-1
		-3
			-3
		-5

МЕТОД ГРАДИЕНТНОГО СПУСКА ПОИСКА МИНИМУМА ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ

ЗАДАНИЕ 2. Пусть требуется найти локальный минимум функции

.

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

. (1)

Выбор вектора определяет различные варианты метода "спуска" к минимуму .

Величина шага управляется выбором . Обычно выбирается так, чтобы функция

(2)

принимала наименьшее значение.

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

(3)

или

. (3.1)

Процесс приближений прекращается, если (абсолютная оценка приближения) или (относительная оценка приближения), где заданная точность.

"Скорейший" спуск получается, если шаг делать в направлении быстрейшего убывания , то есть вдоль вектора

. (4)

Так как градиент в любой точке ортогонален к поверхности уровня , то в точке следует двигаться в направлении вектора до такой точки , в которой ортогонален вектору (в этой точке касается поверхности уровня, то есть будет достигнут минимум функции ).

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

где

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

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

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

В общем случае для этого можно решить уравнение

,

(необходимое условие экстремума), каким-либо из приближенных методов.

В случае, если квадратичная функция, представляет собой квадратный трехчлен относительно с положительным старшим коэффициентом и его минимум можно найти, если известны значения при каких-либо трех значениях . Выберем, например для значения –1, 0, 1 и вычислим (обратившись к процедуре ) соответствующие значения . Обозначим их через , и . Здесь на самом деле можно не вычислять, так как оно известно с предыдущего шага. Тогда находится по формуле

.

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

1. убывает;

2. ;

3. (или ) .

ЗАДАНИЕ 2. Найти экстремум функции

.

Числовые параметры функции даны в таблице для каждого варианта.

№ Варианта							Начальные данные	Точность
I	-1		-3				(-1; -1)	0,02
II	-2		-1				(0; 0)	0,01
III	-3		-3				(-2; 1)	0,03
IV	-1		-1				(2; 1)	0,015
V	-2		-5				(0; 0)	0,01
VI	-3		-2				(1; 1)	0,01
VII	-1		-3				(2; -1)	0,02
VIII	-4		-2				(0; 0)	0,02
IX	-2		-2				(-1; -1)	0,015
X	-1		-1				(1; 1)	0,02

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