Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Методы последовательной безусловной минимизации

Численные методы поиска условного экстремума

Преобразование задачи условной оптимизации в последовательность задач безусловной оптимизации

· Метод штрафов (внешних штрафов) – к целевой функции добавляется функция-штраф за нарушение каждого из ограничений. Метод генерирует последовательность точек, которые сходятся к решению исходной задачи.

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

где штрафная функция, параметр штрафа.

Штрафные функции конструируются, исходя из условий:

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

Начальная точка задается вне множества допустимых решений.

Утверждение. Пусть − локально единственное решение задачи поиска условного минимума, а функции и непрерывно дифференцируемы в окрестности точки . Тогда для достаточно больших найдется точка локального минимума функции в окрестности и при .

Замечания:

1. С ростом функция приобретает ярко выраженную овражную структуру, скорость сходимости падает. Поэтому обычно выбирают , а иногда начинают и с .

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

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

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

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

где штрафная функция, параметр штрафа.

Как правило, используются:

а) обратная штрафная функция

б) логарифмическая штрафная функция

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

Начальная точка задается внутри множества X. При последовательность точек стремится к точке условного минимума .

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

Замечания:

1. Обычно .

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

3. Обязательна проверка при решении задачи безусловной минимизации, что точка не покинула множество допустимых решений.

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

– для обратной штрафной функции

– для логарифмической штрафной функции

 

· Методы множителей – добавление штрафной функции к функции Лагранжа.

· Точные штрафные функции – решение лишь одной задачи безусловной минимизации.

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


Дата добавления: 2014-01-05; Просмотров: 2464; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.