Свойства приближенных решений и схемы их построения в задачах математического программирования

• Автор: Волошинов, Владимир Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 142 с. : ил.

Оглавление
Введение
Цели работы

Краткая характеристика содержания работы

Сравнительный обзор содержания работы.

I Условии приближенного оптимума. .

1.1 Условия приближенного оптимума на основе соотношений двойственности .

1.2 Необходимое условие приближенного оптимума в дифференциальной форме

для гладких задач

Еще один способ доказательства необходимых условий 1го порядка

Необходимые условия приближенного оптимума первого порядка

1.3 Условия регулярности ограничений гладкой задачи.
Ограниченность множества приближенно оптимальных множителей Лагранжа
для равномерно гладкой и регулярной задачи Р
1.4 Вспомогательные сведения об остром и квадратичном оптимуме
1.5 Достаточные условия приближенного оптимума для гладких задач
1.6 Свойства устойчивости оптимальных решений.
Устойчивость множества приближенных решений для выпуклых задач .
Устойчивость множества приближенных решений относительно возмущения
исходных данных .
II Построение приближенных решений для случая аддитивных возмущений
.1 Основные предположения и общая схема поиска приближенного решения
задачи Р
Аппроксимация задачи Р выпуклой задачей нулевого приближения
Аппроксимация задачи Р выпуклой задачей первого приближения.
Аппроксимация задачи Р выпуклой задачей второго приближения.
.2 Обсуждение основных предположений.
.3 О регулярности выпуклых и близких к ним невыпуклых систем ограничений
.4 Оценки точности по задаче нулевого приближения
.5 Оценки точности по задаче первого приближения.
.6 Оценки точности по задаче второго приближения
III Построение приближенных решений для случая
суперпозиционных возмущений
III. 1 Основные предположения и общая схема поиска приближенного решения
задачи Р X
Аппроксимация задачи V выпуклой задачей нулевого приближения
Аппроксимация задачи V выпуклой задачей первого приближения.
Аппроксимация задачи V выпуклой задачей второго приближения.
1.2 Обсуждение основных предположений и примеры классов
невыпуклых оптимизационных задач, близких к выпуклым
О классах функций, имеющих выпуклосуперпозицнонпое или аффинно
суперпозиционное представление
Обсуждение предположения о малости суперпозиционных возмущений . .
О выборе операторов и Ч в задаче первого приближения
О выборе операторов Ч т п задаче второго приближения
О некоторых классах невыпуклых задач математического программирования,
близких к выпуклым
1.3 О регулярности систем выпуклых ограничений и их невыпуклых возмущений супсрпозиционного типа
1.4 Оценки точности по задаче нулевого приближения.
1.5 Оценки точности по задаче первого приближения
1.6 Оценки точности по задаче второго приближения
IV Иллюстративные примеры.
IV. 1 Проектирование точки на невыпуклое множество слабо деформированный
параллелепипед
IV.2 Невыпуклая задача, близкая к выпуклой блочносепарабелыюй со связывающим
линейным ограничением.
1У.З Минимизация на выпуклом множестве в К нормы нелинейного оператора .
IV.4 Выбор параметров в слабо нелинейной регрессии по чебышевскому критерию.
V Приближенное решение задачи линейного
программирования в режиме реального времени.
V. 1 Краткая техническая постановка задачи и ее формализация.
У2 Эвристическая схема получения приближенного решения.
У.З Результаты вычислительных экспериментов .
Изменения режимов работы при увеличении нормы вектора управлений . 2 Среднее и максимальное число итераций при интенсивном тестировании . . 4 Заключение.
Список литературы


Пусть для некоторого найден вектор хр некоторое приближенное решение задачи нулевого приближения с точностью . Далее, пусть известны некоторые аппроксимации возмущений щ и у3. X, а ,, и1 совпадают на X с аффинными, причем в некоторой окрестности точки а погрешности этих аппроксимаций малы по сравнению с величиной хх. Тогда можно сформировать еще одну задачу выпуклого программирования, которую мы ниже называем задачей первого приближения. Приближенное решение этой задачи, как будет показано, позволяет уточнить значение оптимума в исходной задаче V. Заметим, что если, в некоторой окрестности точки возмущения геР. V ОеЛ удовлетворяют условию Липшица с малыми константами, то доя аппроксимации первого приближения можно использовать операторы и1хи1х урху5хро геГеЛ. Пусть в некоторой окрестности точки х известны некоторые аппроксимации возмущений и, и соответственно, операторами и2 и у2, такими, что функции О являются выпуклыми наХ,а3,у2 совпадают на X с аффинными, причем в некоторой окрестности точки х погрешности этих аппроксимаций малы по сравнению с величиной хжЦ2. Тогда, рассматривая эту более тонкую аппроксимацию возмущений в окрестности точки х6 можно сформулировать задачу выпуклого программирования, которую мы называем задачей второго приближения. Р по сравнению с результатами первого приближения. Выпуклоаддитивное представления исходных данных задачи Р является частным случаем выпуклосуперпозиционного. РДаР,ж,Оу,, РхЖх,щхЖх,Оъ ге, жг,хх,Оу уеЛ, кажется возможным, формально, представить эти данные в виде, аддитивного возмущения исходных данных соответствующей задачи нулевого приближения. Рх или Озху будучи малым, вообще говоря, не будет локально удовлетворять на X условию Липшица с малой константой Липшица простой пример приводится в III. Следует отметить, что для конкретной оптимизационной задачи Р, близкой к выпуклой, выбор того или иного представления ее исходных данных в виде малого возмущения данных некоторой выпуклой задачи нулевого приближения не является формальной процедурой и зависит от конкретного вида функций 3, , д. Причем использование того или иного представления приводит к различным аппроксимирующим задачам. Гла,
где для геГ, убЛ функции Рх, Фх с1,. С непрерывны в Ж и выпуклы на X, функции Гаг 1,. С, гцх ,Ь принимают малые значения на всем X и локально удовлетворяют на X условию Липшица с малыми константами. Полагая для всех ге1, уе. Ргх ЫхФх, 3Х ТЦ,хГцх,
мы получим выпуклоаддитивное представление. Однако, если для некоторого геР функции ,, при всех с1,. X, то для . К,. Та
кое представление является более детальным по сравнению с выпуклоаддитивным. Ь3, причем это представление является более детальным по сравнению с аффинноаддитивным. Ю ф я. Таким образом, мы получим, вообще говоря, две различные задачи первого приближения. Работа состоит из пяти глав. Глава I посвящена характеризации оптимальных решений задач математического программирования. Приводится обобщение известных необходимых и достаточных условий точного оптимума на случай приближенных решений, как в самой задаче V, так и в двойственной к ней задаче в случае, когда V является конечномерной, причем не обязательно близкой к выпуклой. КарушаКунаТаккера, включающее конструктивный способ определения приближенно оптимальных множителей Лагранжа в результате решения специальной задачи квадратичного программирования. Принятая в работе методика использует важное в теории экстремальных задач и теории возмущений понятие нормальности ограничений хе2, ,,. Для анализа свойств 5оптимальности на основе функции Лагранжа вводятся специальные характеризующие функции, позволяющие сформулировать конструктивно проверяемые необходимые и достаточные условия приближенного оптимума. Во второй главе рассматривается класс задач, близких к выпуклым, исходные данные которых имеют выпуклоаддитивное представление. Основные предположения, на которых базируется общая схема поиска приближенного решения задачи V, а также вид задач первого и второго приближений для этого класса приводятся в II. Обсуждению основных предположений посвящен параграф .