Методы погружения в нелинейном программировании

• Автор: Заботин, Игорь Ярославович
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Казань
• Количество страниц: 120 c. : ил

0 Г ДАВЛЕНИЕ

Глава I. МЕТОДЫ ПОГРУЖЕНИЯ ДО МИНИМИЗАЦИИ

ГЛАДКИХ ФУНКЦИЙ

§ I.I. Метод обобщенно опорных гиперплоскостей

для решения задачи математического программирования

§ 1.2. Метод типа условного градиента с частичным

погружением допустимого множества

§ 1.3. Итеративная регуляризация одного варианта

метода типа условного градиента с погружением допустимого множества

§ 1.4. Проекционный метод с погружением

допустимого множества
§ 1.5. Вариант метода Ньютона с частичным погружением допустимого множества
ГЛАВА II. РЕЛАКСАЦИОННЫЕ СУБГРАДИЕНТНЫЕ МЕТОДЫ
МИНИМИЗАЦИИ
§ 2.1. Две общие схемы отыскания точки выпуклого
множества, использующие его погружение
§ 2.2. Релаксационный субградиентный метод
минимизации строго выпуклых функций
§ 2.3. Конечный метод отыскания точки
выпуклого множества
§ 2.4. Метод условного £. - субградиента
Глава III. РЕШЕНИЕ ТЕСТОВЫХ И ПРИКЛАДНЫХ ЗАДАЧ
§ 3.1. Решение тестовых задач методом условного
£. - субградиента
§ 3.2. Применение метода типа условного
градиента с погружением допустимого множества для решения задачи синтеза инфор-мационно-управляющей системы (ИУС)

§ 3.3. Применение метода условного £ - субградиента для решения задачи выбора оптимальных времен функционирования подсистем ИУС
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЦДЕНИЕ
Построение методов решения задач нелинейного программирования и их численная реализация постоянно пользуются вниманием ма-тематиков-вычислителей. В тесной связи с разработкой методов находятся и вопросы оценки их эффективности (см.,напр., [ 15,47,49, 66,67,69,84,90] ). К настоящему времени накоплено значительное число методов минимизации нелинейных функций, складывается определенная их классификация. Различные подходы к построению методов решения нелинейных экстремальных задач предложены в [1-3,6,9,17, 18,23,44-46,48,50-52,55,63-65,68,75,79,81,83],и этот перечень работ далеко не полон. Среди упомянутых можно найти работы, посвященные методам минимизации выпуклых и невыпуклых, гладких и негладких функций. В последнее время большое внимание уделяется разработке методов минимизации недифференцируемых функций. Остановимся на некоторых из них подробнее.
Большую группу методов минимизации негладких функций образуют так называемые субградиентные методы. Одним из первых представителей этой группы является метод обобщенного градиентного спуска (ОГС), предложенный Н.З.Шором (см.,напр., [94]). В дальнейшем субградиентные методы разрабатывались в [20,21,28,29,59,62,72,76, 77,94,95]. Для ускорения скорости их сходимости были предложены варианты метода ОГС с растяжением пространства ([94 - 96]). В [41, 42] Я.И.Заботиным, А.И.Кораблевым, Р.Ф.Хабибуллиным метод ОГС был распространен на задачи минимизации квазивыпуклых функций. В [94, 96] установлена связь методов ОГС и фейеровских приближений ([25-27]), ОГС и методов отсечений ([69]).
Другую группу методов для минимизации недифференцируемых функций составляют £ - субградиентные методы и близкие к ним методы сопряженных субградиентов. Впервые £ - субградиенты исполь-

, (8)
С€ Кг . Поскольку ~ - <0 , то из (8) и (5) следует
неравенство (4). Лемма доказана.
Теорема. Пусть для функции Ф[х) и множества Т) выполняются условия леммы и для всех Хб2) , У е справедливо неравенство
<<рЪс)*,т>^м и-? и2 , С9)
где . Тогда последовательность {х^} , К&К , определяемая предложенным методом,существует И Xм ,к .
Доказательство. Покажем сначала вэзможность выбора шагов в методе из условий (2),(3), то есть,другими словами, существование последовательности ^хк } . Положим ^ “ хк + ^ » где
р - произвольное число, удовлетворяющее неравенству Тогда

сР(х?)-фГг1<)=(^,(х?)+ Х-<(ф"(Х^+0^к)- (Ю)
-Ф//Гхк))2к ,5К > , 0$е*П
а) Пусть сначала индекс К 6 , то есть хк6 О и
с, = 5с - ос .Из выпуклости функции Ф.(х) следует, что
УС К к К
^ Ч^(х^)+(і-^>) Схк) = °тсюда и из
равенства (10) с учетом (5),(9) получим неравенство

ф('х^)-ф('хк)^рц^(хк)+ и хк - х^ II ( (XX)
Для сильно выпуклой функции ФК(Х) известна ([9], с.186) оценка
»5к-хк|Ч • (к)