Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. A. Методы измерения мертвого времени
  2. HR– менеджмент: технологии, функции и методы работы
  3. I метод.
  4. I. 2. 1. Марксистско-ленинская философия - методологическая основа научной психологии
  5. I. 2.4. Принципы и методы исследования современной психологии
  6. I. Анализ методической структуры и содержания урока
  7. I. Методические указания к изучению курса

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

, где - векторы множителей; - параметр штрафа; 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; просмотров: 115 | Нарушение авторских прав


Читайте в этой же книге: Общие принципы методов поиска условного экстремума | Метод штрафов | Метод барьерных функций | Применение обратной штрафной функции | Применение метода в задаче с ограничениями типа равенств. | Применение метода в задаче с ограничениями типа неравенств. | Метод Зойтендейка | Пример отчета по лабораторной работе |
<== предыдущая страница | следующая страница ==>
Комбинированный метод штрафных функций| Метод точных штрафных функций

mybiblioteka.su - 2015-2024 год. (0.01 сек.)