Метод множителей

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

, где - векторы множителей; - параметр штрафа; k - номер итерации.

Задается начальная точка поиска . На каждой -й итерации ищется точка минимума модифицированной функции Лагранжа при заданных с помощью одного из методов безусловной минимизации. Полученная точка используется в качестве начальной на следующей итерации, выполняемой при возрастающем значении параметра штрафа и пересчитанных определённым образом векторах множителей . Для достижения сходимости в отличие от метода внешних штрафов не требуется устремлять к бесконечности.

Алгоритм:

Шаг 1. Задать начальную точку ; начальное значение параметра штрафа ; число для увеличения параметра; Начальные значения векторов множителей ; малое число для остановки алгоритма. Положить .

Шаг 2. Составить модифицированную функцию Лагранжа:

.

Шаг 3. Найти точку безусловного минимума функции по x с помощью какого-либо метода (нулевого, первого или второго порядка):

.

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

Шаг 4. Вычислить ,

где и проверить выполнение условия окончания:

a) если , процесс поиска закончить:

;

b) если , положить:

(пересчёт параметра штрафа);

(пересчёт множителей для ограничений-равенств);

(пересчёт множителей для ограничений-неравенств);

, и перейти к шагу 2.

Утверждение 3 (о сходимости метода множителей в задаче с ограничениями типа равенств) Пусть функции непрерывны, последовательность ограничена, при всех k, причем , - компактное изолированное множество точек локального минимума в исходной задаче. Тогда найдется подпоследовательность , сходящаяся к некоторой точке и такая, что ее произвольный элемент является точкой локального минимума функции . Если при этом состоит из единственной точки , то можно указать последовательность и номер такие, что и является точкой локального минимума функции при .

Замечания:

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

б) Если , то через конечное число итераций те множители, которые соответствуют ограничениям, не являющимся активными в точке , обратятся в нуль.

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

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

д) Метод множителей был предложен Пауэллом и Хестенсом и имеет многочисленные модификации.

Пример: Найти минимум в задаче

Решение:

1. В поставленной задаче . Решим ее аналитически. Положим . Выберем для сравнения последовательность , используемую в примере в методе штрафов.

2. Составим модифицированную функцию Лагранжа:

3. Найдем безусловный минимум при фиксированных :

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

В первом случае имеем .

Кроме того, , т.е. достаточные условия минимума выполняются. Проведем расчеты при различных k.

При получаем .

Имеем , поэтому .

При получаем .

Имеем , поэтому .

При получаем .

Имеем , поэтому

.

При получаем .

Имеем , поэтому

.

При получаем .

Имеем , поэтому процесс завершается:

.

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

k
				-3,66		0,222
			1,333	-3,2218	0,333	0,333
		1,333	1,0555	-3,100	0,0555	0,0075
		1,888	1,00109	-3,00006	0,00109	0,0021
		1,997	1,0000029	-3,00000	0,0000029	0,0000058

Дата добавления: 2015-07-20