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

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

Содержание
Введение
1 Общие процедуры решения задачи математического программирования и отыскания точки выпуклого множества. Их реализации
1.1 Общие процедуры аппроксимации с частичным погружением допустимого множества для задачи математического программирования
1.2 Общая процедура аппроксимации с полным погружением допустимого множества для задачи математического программирования

1.3 Две общие схемы отыскания точки выпуклого множества и их реализации

2 Методы условной минимизации гладких псевдовыпуклых функций с

реализациями на основе процедур аппроксимации

2.1 Метод условной минимизациии гладких псевдовыпуклых функций

2.2 Некоторые реализации метода из § 2.

2.3 Метод типа условного градиента для задачи псевдовыпуклого программирования
2.4 Реализации метода из § 2.3 на основе частичного погружения допустимого множества
2.5 Метод проекционного типа в псевдовыпуклом программировании и его реализации на основе процедур аппроксимации множеств
2.6 Метод второго порядка
3 Алгоритмы с параметризованными направлениями для условной минимизации гладких псевдовыпуклых функций
3.1 Вспомогательные результаты
3.2 Метод типа условного градиента с параметрическим заданием подходящих направлений
3.3 Реализация метода типа условного градиента с параметрическим заданием подходящих направлений на основе процедур аппроксимации
3.4 Проекционные алгоритмы с параметризованными направлениями спуска
3.5 Проекционные алгоритмы с параметризованными направлениями, использующие аппроксимацию допустимого множества

3.6 Алгоритм второго порядка с параметризованными направлениями
3.7 Алгоритм второго порядка с параметризованными направлениями, использующий частичное погружение допустимого множества
3.8 Вариант метода возможных направлений Зойтендейка с параметризованными направлениями для задачи псевдовыпуклого программирования
3.9 Вариант метода линеаризации с параметризованными направлениями итерационного перехода
4 Методы условной минимизации негладких псевдовыпуклых функций
4.1 Релаксационные алгоритмы условной минимизации негладких строго псевдовыпуклых функций
4.2 Алгоритмы отыскания условного дискретного минимакса
4.3 Вариант параметризованного метода центров
5 Алгоритмы безусловной минимизации псевдовыпуклых функций и исследование их устойчивости
5.1 Общий метод безусловной минимизации гладких псевдовыпуклых функций
5.2 Одношаговые и многошаговые алгоритмы, как реализации общего метода безусловной минимизации
5.3 Методы спуска по группам переменных
5.4 Общая схема исследования устойчивости алгоритмов безусловной минимизации гладких псевдовыпуклых функций
5.5 Исследование устойчивости некоторых одношаговых алгоритмов
5.6 Исследование устойчивости некоторых многошаговых алгоритмов
6 Методы решения специальных и прикладных задач псевдовыпуклого
программирования
6.1 Методы спуска по группам переменных для одного класса задач условной минимизации
6.2 Метод условной минимизации функции максимума специального вида
6.3 Субградиентный метод отыскания седловых точек
6.4 Использование предложенных методов при решении некоторых прикладных задач
Заключение
Список литературы

Введение
В связи с постоянно возникающими на практике оптимизационными задачами нелинейное программирование остается актуальным направлением исследований специалистов, работающих в области математической кибернетики и вычислительной математики. Большинство работ по нелинейному программированию относится к наиболее изученному его разделу выпуклого программирования. Различные подходы к построению методов выпуклого программирования и исследованию их сходимости предложены в [2, 8, 11, 16, 17, 21, 22, 23, 24, 26, 28, 34, 36, 38, 42, 45, 47, 48, 53, 54, 55, 58, 124, 133, 134, 140, 141, 143, 161, 167,168, 173, 176,178, 179, 185,194, 200, 201, 205, 207], и этот перечень работ далеко не полон. К настоящему времени разработано значительное число методов минимизации как гладких, так и негладких выпуклых функций, ,и сложилась определенная их классификация. Можно привести примеры довольно больших классов методой выпуклого программирования, исследованных, в частности, в указанных выше работах. Это методы возможных направлений, методы типа линеаризации, штрафных и барьерных функций, методы центров, модифицированных функций Лагранжа и др. Большую группу методов минимизации недифференцируемых выпуклых функций образуют основанные на идеях метода обобщенного градиентного спуска [207] так называемые субгра-диентные методы (напр., [42, 57, 73, 151, 169, 174, 181, 202, 207]), связанные с методами фейеровских приближений (напр., [26, 54]), методами отсечений (напр., [6, 169]). Близкими к этой группе являются е - субградиентные методы, предложенные сначала в виде алгоритмов типа наискорейшего спуска для минимаксных задач (см., напр., [43]) и разработанные затем для минимизации как функций максимума, так и произвольных выпуклых функций (напр., [31, 42, 43, 68, 131,159, 173,186, 200, 201, 207, 223, 224, 230, 231]). В отдельные группы методов выпуклого программирования можно выделить алгоритмы погружений - отсечений (напр., [6, 7, 9, 21, 62, 69, 133, 161, 207, 210, 220, 229]), а также основанные на идеях, подробно описанных в [23, 24, 195] , методы регуляризации и итеративной регуляризации (напр., [25, 46, 189, 196]). Отметим, что в тесной связи с разработкой методов выпуклого программирования находились и находятся вопросы оценки их эффективности (напр., [7, 169, 170, 171, 193, 210]).
Однако, практикой востребованы и методы минимизации функций более общих, чем выпуклые. Исследованиям задач нелинейного программирования, не входящих в раздел выпуклого программирования, и построению методов их решения также посвящено не-

І2 ( тоба сдвига штрафов, который при определенном способе задания коэффициентов А*-можно интерпретировать и как метод модифицированной функции Лагранжа ([179], с. 256).
Замечание 1.10 . Если 1,(х) = \х - У^Ц2, а{ — г = 1,2,..., і!0(х) = 0, то процедура7Гг представляет собой вариант известного проксимального метода для задачи с выпуклой целевой функцией ([!])■ Отметим, что в предлагаемом здесь варианте точки уі ищутся из условия приближенного минимума вспомогательных функций Уі(х) на множествах Мі, а не на исходном множестве Є, и, кроме того, для функции д(х) не требуется условие выпуклости.
Если в процедуре 7г2 вместе с у{ отыскивать также точки !/,£(? из условия (1.3), то на каждом шаге алгоритмов, описанных в замечаниях 1.9, 1.10, будем иметь оценки сверху и снизу для значения д*.
Для процедуры 7г2 так же, как и для ях, легко построить обобщающий ее итерационный процесс для задачи (1.1), в которой размерность множества (3 может быть меньше, чем п. Для этого в 7г2 введем те же дополнительные условия на выбор М0, і/, г(, А(, что и в 7?!. Процедуру 7г2 с такими изменениями по аналогии обозначим через 7Г2. Используя лемму 1.1, нетрудно передоказать утверждения леммы 1.4 и теорем 1.2 - 1.4 для последовательности {у*}, построенной процедурой 7Г2.
Приведем далее замечания, с учетом которых в § 1.3 будут предложены еще две итерационные процедуры, используемые в дальнейшем для построения подходящих направлений.

Замечание 1.11 . Пусть множество Є ограничено, т > 1, Сф 0, и точка у такова,

что у ^(3- Считая, что известны точки у3 ЄСЗ; V) Є 3, положим в процедуре тг]
д(х) = тах(р,х ~ у), (1.25)

где Р - конечное множество векторов из \г1(у,С), выберем в качестве Мо выпуклый многогранник, содержащий хотя бы одну точку из У*, и будем вычислять уг согласно условию (1.11). Тогда через конечное число итераций выполнится включение Є в, либо согласно лемме 1.3 любая предельная точка выработанной последовательности {Ні} будет принадлежать (3. Таким образом, если у ([ С и )ф ф С У) € Т, то такую реализацию процедуры тгх можно считать схемой отыскания точки множества Є. Поскольку схема, вообще говоря, не обеспечивает решение задачи нахождения точки из множества за конечное число шагов, то ее нельзя назвать эффективной. Однако, эта схема, как будет видно далее, может применяться для построения подходящих направлений в некоторых методах минимизации.