Методы отсечений с обновлением аппроксимирующих множеств для задач нелинейного программирования

• Автор: Яруллин, Рашид Саматович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Казань
• Количество страниц: 147 с. : ил.

Оглавление
Введение

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

1.1 Метод отсечений на основе аппроксимации допустимой области

семейством опорных плоскостей без вложения погружающих множеств

1.2 Метод отсечений с отбрасыванием секущих плоскостей и возможностью построения на его основе смешанных алгоритмов

1.3 Метод проектирования точки, использующий аппроксимирующие множества

1.4 Метод отсечений, допускающий параллельные вычисления

1.5 Численные эксперименты

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

функции
2.1 Метод отсечений для отыскания дискретного минимакса с отбрасыванием секущих плоскостей
2.2 Метод отсечений с обновлением аппроксимирующих множеств,
использующий обобщенно-опорные элементы
2.3 Модифицированный метод уровней
2.4 Метод отсечений и построение на его основе смешанных алгоритмов минимизаций
2.5 Численные эксперименты
3 Методы отсечений с одновременной аппроксимацией допустимой области и надграфика целевой функции
3.1 Метод с аппроксимацией области ограничений и надграфика
на основе обобщенно-опорных отсекающих плоскостей
3.2 Метод с аппроксимацией допустимой области и надграфика,
использующий обновление погружающих множеств

3.3 Численные эксперименты
Заключение
Список литературы
Введение
Довольно часто в различных областях прикладной математики возникают оптимизационные задачи, которые решаются методами нелинейного программирования. В связи с этим разработка методов условной минимизации с удобной численной реализацией продолжает пользоваться вниманием специалистов в области математического программирования. К настоящему времени накоплено значительное число методов решения задач нелинейного программирования. Различные подходы к построению таких методов были предложены в [3] - [6], [11], [12], [17], [24] - [31], [33] - [42], [45] - [53|, [55] - [60], |62| - [66], [68], [72] - [78], [82] - [84], [86] - [92], [95] - [100], [103| - [110|, [112] -[117], [119], [124], [126], и этот перечень работ можно существенно расширить. Среди упомянутых — работы, посвященные построению методов минимизации выпуклых и невыпуклых, дифференцируемых и недифференцируемых функций. Сложилась и определенная классификация этих методов. Например, в отдельные классы выделились методы штрафных и барьерных функций, методы возможных направлений, методы типа линеаризации, квазиньютоновские методы, еубградиентные и c-субградиентные методы, методы типа приведенных градиентов, методы центров и другие.
Известный и довольно широкий класс образуют методы отсечений, которые используются как для задач целочисленного программирования, так и для задач непрерывной оптимизации. Построению методов отсечений, предназначенных для решения задач целочисленного программирования, посвящены, например, работы [67], [69] - [71], [101], [111], [118], (120] - [123], [127], [148] - [153]. Пожалуй, большее число работ посвящено методам отсечений для задач нелинейного программирования. Разные подходы к построению таких методов можно найти в ]2], [7] - [10|, [13] - [15], |18] - [23|, |79| - |81|. [102], [125], [161], [163].
Значительное число методов отсечений для задач нелинейного программирования основывается на следующей идеи. При построении итерационных точек в этих методах используется последовательное погружение либо множества ограничений исходной задачи, либо надграфика целевой функции в

Доказательство. 1) Пусть к = 0. Если уо £ £>'0, то согласно п. 3 метода Д = 0, хо = уо, и равенство (1.2.6) при к = О выполняется. Поэтому будем считать, что уо (Ё ЁД0. Покажем тогда существование номера i = Д > 0, для которого справедливо включение
т0 е д:0. (1.2.29)
Допустим противное, то есть
Уг ^ Д(0 V?. £ К, 'I > 0. (1.2.30)
Выделим из последовательности {у,;}, г £ К. г > 0, сходящуюся подпоследовательность {уг}, г € К' С /’, и пусть у' — ее предельная точка. Согласно п. 2 метода с учетом допущения (1.2.30) множество (5, для всех г £ /С * > 0. имеет вид (1.2.4), и для тех же г выполняется равенство (1.2.5). Тогда по лемме 1.2.3 имеем включение у' £ Д, и
7Ду')<0. ■ (1.2.31)
С другой стороны, в силу (1.2.30) П(уг) > £о для всех г £ /С. Переходя
в последнем неравенстве к пределу по г £ К1, получим Д(у') > £« > 0,
что противоречит (1.2.31). Таким образом, существование номера Д > 0, для которого справедливо (1.2.29), доказано, и равенство (1.2.6) при к = 0 имеет место.
2) Допустим теперь, что (1.2.6) выполняется при некотором фиксированном к > 0, то есть Хк = уц при выбранном к. Покажем существование такого номера Д+] > Д, что
Уч+^1Уем, (1.2.32)
тогда ту;+1 = Уд+1-. и лемма будет доказана.
Предположим противное, то есть
Щ с К. г > (1.2.33)
Выберем среди точек у,, г £ К, г > Д., сходящуюся подпоследовательность {уг}, г € К"■ Пусть у" — ее предельная точка. Согласно предположению (1.2.33) для всех г £ К. г > Д, выполняются равенства (1.2.5), а множества СД задаются в виде (1.2.4). Значит, по лемме 1.2.3 имеет место неравенство
Ну") < О- (1.2.34)
Как и в первой части доказательства из (1.2.33) с учетом (1.1.21) легко полу-
чается неравенство Р(у") > 0, противоречаще® (1.2.34). Таким образом, доказано существование номера Д+ь для которого справедливо (1.2.32). Лемма доказана.