Алгоритмы заданной точности в методе штрафов с аппроксимацией допустимого множества

• Автор: Фукин, Игорь Анатольевич
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Казань
• Количество страниц: 123 с.

1 Аппроксимация допустимого множества

1.1 Постановка задачи и основные понятия

1.2 Аппроксимация допустимого множества. Условие р - аппроксимируемости функции

1.3 Оценки параметров аппроксимации

2 Алгоритмы заданной точности в методе штрафов

2.1 Алгоритмы с использованием множества, погруженного в допустимое

2.2 Алгоритмы с аппроксимацией допустимого множества

2.3 Алгоритмы, осуществляющие двустороннее приближение к решению

2.4 Алгоритмы с неполной минимизацией вспомогательных функций,

3 Реализация алгоритмов и анализ вычислительных экспериментов

3.1 Процедуры реализации принципиальных алгоритмов. Вычислительные аспекты

3.2 Тестовые задачи
3.3 Результаты вычислений
Заключение
Список литературы

В связи с повсеместным использованием вычислительной техники не вызывает сомнение необходимость перехода во всех сферах человеческой деятельности с интуитивных методов принятия решений на новые, более эффективные методы. В их основе, как известно, лежит количественное обоснование выбора того или иного варианта действий при определенных условиях. Эта проблема решается, в частности, методами математического программирования, разработке и описанию которых к настоящему моменту посвящено очень большое число работ (см., например, [8, 9, 17, 43, 40, 41, 55, 59, 84, 89, 94, 95, 123] и библиографию в них).
Одним из наиболее исследованных на сегодняшний день разделов математического программирования можно считать теорию линейной оптимизации [18, 52, 50, 125]. Основными направлениями развития этой области в настоящее время являются теория двойственности [53], параметризация задачи линейного программирования [27], проблемы некорректности ее постановки и нестационарного моделирования [52, 54].
Для более сложных задач квадратичного программирования, также как и для линейных, имеются конечные методы их решения [23, 74, 99, 100, 109, 121].
Сложнее обстоит дело с решением нелинейных задач, где, по-видимому, не приходится рассчитывать на создание сколько-нибудь универсальных эффективных методов. В этом случае, обычно, для решения исходной задачи на каждой итерации приходится решать более простые вспомогательные экстремальные задачи.

Большой интерес представляют методы последовательной безусловной минимизации [33, 114], сводящие исходную задачу с ограничениями к последовательности безусловных задач, для которых аппарат минимизации разработан достаточно хорошо, создано много методов. Здесь искомое решение определяется как предел последовательности безусловных минимумов вспомогательных задач. В зависимости от способа сведения задачи с ограничениями к семейству вспомогательных задач различают методы центров, штрафных функций, модифицированных функций Лагранжа и другие. Свое развитие этот раздел оптимизации получил благодаря работам И.И. Еремина [46], Ю.Г. Евтушенко [41, 43], В.Г. Жадана [58], Ф.П. Васильева [16], В.В. Федорова [112], Д. Бертсекаса [12]. Обзор иностранных работ по этой тематике дан в [114] и [126].
Одним из первых методов последовательной безусловной минимизации был метод штрафных функций, общая идея которого заключается в следующем. Для нахождения минимума функции f(x) на множестве Л строится семейство вспомогательных функций
где {<рк(х), к = 0,1...} - последовательность определенных и неотрицательных в Нп функций, удовлетворяющих условию
Алгоритм состоит в минимизации вспомогательной функции (1) при различных к £ {0,1... }, где к —» оо.
Очевидно, с ростом номера к приходится "платить" большой штраф за нарушение ограничений.
Принято считать ([114],с.20), что впервые подобный подход был преме-нен еще в 1943 году Р. Курантом [129], но получил свое развитие лишь в конце 50 - начале 60 годов. В этот период была доказана его сходимость
Рк{х) = f(x) + щ(х)
(1)
х е £>, х 0 И.

В методе штрафных функций расположение итерационной точки г (С*) не зависит от х(Ск- 1). Поэтому для каждой вспомогательной функции П(ж,СУ можно выбирать свой метод безусловной минимизации.
В принципе, если на подготовительном шаге схемы выбрать достаточно большое Со, то можно надеяться, что номер А, при котором т(Слг) £ -0(0), будет небольшим или, вообще, равен 1. Однако, как неоднократно отмечалось в литературе (см., например, [16], [108], [109]) при большом значении штрафного коэффициента С матрица вторых производных функции А(ж, С) в некоторых точках, близких к границе множества Х)(р) будет плохо обусловленной, что негативно отразится на. скорости сходимости градиентных методов нахождения безусловного минимума функции Р(х, С), которая при больших С становится овражной.
На подготовительном шаге схемы не конкретизируется способ выбора такого числа р > 0, что попадание итерационной точки ж(СУ в допустимое множество гарантировало бы ее е - оптимальность. Теоремы 1.5 и 1.6 дают правила подбора подобного параметра р в зависимости от тех или иных требований к функциям, участвующим в задаче.
При выполнении условий Ъ) и с) можно решать с заданной точностью задачу выпулого программирования с помощью следующего принципиального алгоритма.
Алгоритм 1. Задается требуемая точность решения е. Выбираются числар е (0,тт{^,р'ф}) и натуральное число N. Задается точка жо 6 Яп. и возрастающая функция р(-) такая, что <р(А) > Щ, 1) > 0. Полагается к = 1.
1. Вычисляется С к = <р (к).
2. Выбирается метод обеспечивающий нахождение безусловного минимума функции Я{х, Ск).
3. Методом Ак находим точку ж к = ж (Ск).
4.Если х к 6 И(0), то процесс окончен и ж к является е- решением задачи (1.1). Иначе переходим к пункту 1 при к, замененном на к + 1.