Лабораторная работа #2

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА МО ЭВМ

Дисциплина: Методы оптимизации

ОТЧЕТ

по лабораторной работе №2

«Исследование методов условной минимизации»

Выполнили студенты гр. 3352

Воронин С.Ю.

Сергеев М.В.

Проверил: Балтрашевич В.Э.

Санкт – Петербург

2005

1. Формулировка задания

Для функции f(x1, x2) = (x1 – b)⁴ + a*(x2 + 3 -b)⁴ провести исследования следующих методов условной минимизации:

1. Метод проекции градиента

2. Метод условного градиента

3. Метод функции Лагранжа

для следующих значений параметра a: 0.1; 1;

для следующих значений параметра b: 0; 3;

для следующих начальных точек: (3; 8); (3; 10); (10; 20)

2. Математическая постановка задачи

2.1 Метод проекции градиента

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

x^k+1= p_x (x^k- f(x^k)), где p_x проектор на X.

2.2 Метод условного градиента

В очередной точке x^k линеаризуют функцию f(x) (в этом «условность» метода, то есть линеаризация и есть «условие» в названии). Затем решают задачу min линейной функции на X и найденную точку используют для выбора направления движения.

При этом предполагается:

1. Задача минимизации линейной функции на X имеет решение.

2. Это решение может быть найдено достаточно просто, лучше всего в явной форме.

3. Нужно указать правило выбора _k. Можно _k определить из условия наискорейшего спуска :

В этом случае последовательность x^k сходится к специальной точке. В частности для гладких функций f верно: f(x*)- f* = o(1/k), где f* = min f(x) на множестве X.

2.3 Метод функции Лагранжа

Функцией Лагранжа в ЗВП называется функция

(x ,) = f(x)+ f(x) + (,g(x)), где _i0.

Выше была доказана теорема о седловой точке:

Если выполняется соотношение

(x* , ) (x* ,*) (x ,*) xRⁿ,   0,

то точка x* является оптимальной точкой задачи выпуклого программирования.

Это соотношение можно записать иначе:

(*) (x* ,*) = (x ,) = (x ,) = f(x*)

Если назвать x прямыми переменными, а  двойственными, то видно, что прямые и двойственные переменные равноправны.

Теорема Куна- Таккера позволяет исходную задачу заменить задачей отыскания седловой точки функции Лагранжа, то есть задачи вида (x ,).

Метод модифицированной функции Лагранжа.

Метод сходится к (x* ,*) со скоростью геометрической прогрессии.

4. Испытания методов оптимизации

Метод условной оптимизации	Метод безусловной оптимизации	Количество шагов	Точка минимума	Начальная точка	Значение параметра а	Значение параметра b
Метод проекции градиента	Градиентный с дроблением шага	2	(0; 0)	(3; 8)	0.1	0
	Наискорейшего спуска	9
	Ньютона с одномерной минимизацией	Не удалось найти минимум
	Полака Ривьера	19
Метод условного градиента	---	3	(0; 0)	(3; 8)	0.1	0
Метод функции Лагранжа	---		(0; 0)	(3; 8)	0.1	0
Метод проекции градиента	Градиентный с дроблением шага	9	(0; 0)	(3; 10)	0.1	0
	Наискорейшего спуска	3
	Ньютона с одномерной минимизацией	Не удалось найти минимум
	Полака Ривьера	181
Метод условного градиента	---	2	(0; 0)	(3; 10)	0.1	0
Метод функции Лагранжа	---		(0; 0)	(3; 10)	0.1	0

Метод условной оптимизации	Метод безусловной оптимизации	Количество шагов	Точка минимума	Начальная точка	Значение параметра а	Значение параметра b
Метод проекции градиента	Градиентный с дроблением шага	9	(0; 0)	(10; 20)	0.1	0
	Наискорейшего спуска	3
	Ньютона с одномерной минимизацией
	Полака Ривьера	175
Метод условного градиента	---	2	(0; 0)	(10; 20)	0.1	0
Метод функции Лагранжа	---		(0; 0)	(10; 20)	0.1	0
Метод проекции градиента	Градиентный с дроблением шага	48	(2.56; 0.60)	(10; 20)	1	3
	Наискорейшего спуска	301
	Ньютона с одномерной минимизацией	1
	Полака Ривьера	Не удалось найти минимум
Метод условного градиента	---	91	(2.56; 0.60)	(10; 20)	1	3
Метод функции Лагранжа	---	~400	(2.56; 0.60)	(10; 20)	1	3

4. Сравнительный анализ методов оптимизации

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

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

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

6