URSS.ru Магазин научной книги
Обложка Нестеров Ю.Е. Эффективные методы в нелинейном программировании Обложка Нестеров Ю.Е. Эффективные методы в нелинейном программировании
Id: 304705
929 р.

Эффективные методы в нелинейном программировании № 12. Изд. 2, стереотип.

URSS. 2024. 304 с. ISBN 978-5-9710-7480-9.
Белая офсетная бумага
Машинописный макет.

Аннотация

В настоящей книге представлен ряд результатов, связанных с построением эффективных математических методов решения как линейных, так и нелинейных экстремальных задач.

1. Теория лексикографического дифференцирования негладких функций. В отличие от ранее известных подходов, вводимые здесь дифференциальные характеристики (лексикографические производные) являются линейными операторами и по своим свойствам аналогичны производным гладких функций.... (Подробнее)


Оглавление
top
Предисловие к серии8
Введение10
ГЛАВА 1. Выпуклые множества и выпуклые функции14
1.1. Выпуклые множества14
1.2. Выпуклые функции21
1.3. Равномерно выпуклые функции36
1.4. Гладкие выпуклые функции48
1.5. Квазивыпуклые функции56
1.6. Квазиоднородные функции79
ГЛАВА 2. Математический аппарат дифференцирования негладких функций88
2.1. Проблема дифференцирования негладких функций88
2.2. Класс лексикографически гладких функций91
2.3. Лексикографические производные и их свойства95
2.4. Основная теорема лексикографического дифференциального исчисления104
2.5. Примеры лексикографических производных109
2.6. Необходимые условия экстремума118
2.7. Некоторые теоремы из анализа130
2.8. Лексикографическое дифференцирование в бесконечномерных пространствах141
ГЛАВА 3. Методы минимизации негладких функций146
3.1. Постановка задачи146
3.2. Субградиентный метод149
3.3. Общая схема методов отсечений. Метод центров тяжести161
3.4. Метод описанных эллипсоидов166
3.5. Метод растяжения пространства172
ГЛАВА 4. Методы решения экстремальных задач с гладкими компонентами177
4.1. Оптимальные методы безусловной минимизации функций с липшицевым градиентом177
4.2. Метод сопряженных градиентов184
4.3. Адаптивный метод безусловной минимизации для функций с гельдеровым градиентом190
4.4. Минимизация составных функций. Условные задачи195
ГЛАВА 5. Итеративные методы для задач линейного и квадратичного программирования205
5.1. Полиномиальные алгоритмы в линейном программировании. Постановка задачи205
5.2. Двойственные алгоритмы решения систем линейных неравенств. Вспомогательные результаты208
5.3. Двойственный метод Ньютона214
5.4. Двойственный метод параллельных траекторий221
5.5. Прямой метод параллельных траекторий231
5.6. Метод барьеров для задачи квадратичного программирования247
5.7. Другие полиномиальные алгоритмы линейного и квадратичного программирования260
ПРИЛОЖЕНИЕ Некоторые результаты из теории сложности экстремальных задач272
Библиографический комментарий288
Список литературы293

Введение
top

В математическом программировании, как и во многих других областях вычислительной математики, конечным результатом развития общей теории являются методы решения определенных классов задач. При этом важным показателем зрелости теории выступает перечень свойств, наличие которых у данного метода признается желательным. Расширение этого перечня неизбежно приводит к пересмотру сложившихся представлений о возможностях традиционных алгоритмов, стимулирует разработку новых вычислительных процедур.

К концу 70-х годов в теории оптимизации постепенно сформировалось новое направление, связанное с оценкой эффективности метода по его глобальной скорости сходимости. Если раньше исследователей прежде всего интересовал вопрос о том. сходится та данный метод и какова оценка его скорости сходимости в окрестности точки минимума, то с этого времени стали все чаще появляться работы, в которых выводились оценки скорости сходимости существующих алгоритмов, "работавшие" с первой же итерации метода. Важным вкладом в развитие этого направления стало выявление А.С.Немировским и Д.Б.Юдиным нижних оценок сложности традиционных классов экстремальных задач. Созданная ими теория сложности дала мощный импульс для разработки новых вычислительных алгоритмов по двум причинам. Во-первых, были установлены потенциальные границы для скорости сходимости методов оптимизации на различных классах экстремальных задач, сформулировано понятие оптимального метода. А во-вторых, среди существовавших к тому времени алгоритмов лишь два (метод субградиентного спуска и метод центров тяжести) можно было отнести к оптимальным. К настоящему времени арсенал оптимальных методов удалось существенно расширить.

Подтверждением продуктивности нового направления стало обоснование Л.Г.Хачияном полиномиальной разрешимости задачи линейного программирования (ЛП), опиравшееся на глобальную оценку скорости сходимости метода эллипсоидов. С помощью методики Л.Г.Хачияна любой итеративный метод решения задачи ЛП, сходящийся со скоростью геометрической прогрессии, знаменатель которой зависит лишь от числа переменных, может быть превращен в полиномиальный алгоритм ЛП. С такой интерпретацией связан бурный прогресс в построении полиномиальных алгоритмов ЛП, наблюдавшийся в последние годы.

Результаты, связанные с проблематикой оптимальных алгоритмов нелинейного программирования, полиномиальных алгоритмов ЛП, в силу их новизны еще не успели найти отражения в монографической литературе. В настоящей монографии делается попытка восполнить этот пробел.

Остановимся вкратце на содержании монографии.

Первая глава носит вводный характер и содержит необходимые для дальнейшего сведения из выпуклого анализа. Рассматриваются традиционные классы гладких выпуклых,- равномерно выпуклых и квазивыпуклых функций, исследуются их свойства. Вводится новый класс квазиоднородных функций, основная характеристика которых оказывается инвариантной относительно линейной замены переменных.

Во второй главе описывается аппарат дифференцирования негладких функций, позволяющий конструктивно вычислять дифференциальные характеристики, необходимые для методов негладкой оптимизации. Предлагается новый способ введения аналога производной негладкой функции, при котором таким аналогом оказывается линейный оператор - лексикографическая производная. Для , однозначного определения лексикографической производной в точке достаточно зафиксировать произвольный базис в пространстве переменных. Класс функций, у которых можно вычислять лексикографические производные, - лексикографически гладкие функции, является линейным пространством, содержит все дифференцируемые, выпуклые и квазидифференцируемые по Демьянову-Рубинову функции и все суперпозиции лексикографически гладких функций. При этом для пересчета лексикографических производных таких функций при операции суперпозиции удается выписать формулы по своей простоте сравнимые с формулами классического дифференциального исчисления.

Лексикографические производные негладких функций естественным образом согласуются с ранее известными дифференциальными объектами. Так, лексикографический градиент гладкой функции совпадает с ее градиентом по Гато, лексикографический градиент выпуклой функций является крайней точкой ее субдифференциала, а лексикографический градиент квазивыпуклой функции - опорным функционалом к ее множеству уровня. Исследуются свойства лексикографически гладких функций, формулируются необходимые условия безусловного экстремума. Устанавливается справедливость формулы Ньютона-Лейбница для лексикографических производных по любому фиксированному базису в пространстве переменных. Демонстрируются возможности лексикографических производных как инструмента, анализа негладких функций.

В третьей главе рассматриваются методы минимизации негладких выпуклых и квазивыпуклых функций: метод субградиентного спуска, метод центров тяжести, метод эллипсоидов. Обосновываются оценки их скорости сходимости. Описывается версия метода растяжения пространства в направлении градиента, применимого для минимизации квазиоднородных функций.

Четвертая глава посвящена описанию оптимальных методов решения гладких.экстремальных задач Рассматриваются оптимальные методы минимизации сильно выпуклых функций, обладающих липшицевым градиентом, метод минимизации функций с гельдеровым градиентом, автоматически настраивающийся на параметры гладкости целевой функции, метод минимизации негладких сверток гладких функций, обладающий оценкой скорости сходимости, характерной для гладкого случая, методы решения условных задач.

В пятой главе рассматриваются итеративные методы решения задач линейного и квадратичного программирования. Наряду с обоснованием полиномиальности метода внутенних штрафных функций, исследуются вычислительные схемы и новых методов: метода параллельных траекторий (прямого и двойственного) и полиномиального метода квадратичного программирования, основанного на использовании оптимальных алгоритмов минимизации гладких функций. Трудоемкость решения соответствующей задачи у лучших из этих методов оценивается произведением логарифма требуемой точности на полином третьей степени от размерности задачи.

В приложении» написанном А.С.Немировским, приведены основные результаты из теории сложности, относящиеся к рассмотренным постановкам задач.


Об авторе
top
photoНестеров Юрий Евгеньевич
Доктор физико-математических наук. С 1993 г. работает в Католическом университете города Лувен в Бельгии; ныне состоит в должности ординарного профессора Католического университета Лувена. Его основные результаты связаны с построением новых эффективных методов выпуклой оптимизации. Опубликовал более 150 статей и пять монографий. Среди его главных достижений можно отметить разработку полиномиальных методов внутренней точки, быстрых градиентных методов и современных методов второго и более высоких порядков. Лауреат нескольких престижных международных премий (Данцига, фон Неймана, Ланчестера и др.). Член Европейской академии наук и Национальной академии наук США.

В 2023 г. совместно с А. С. Немировским удостоен Премии Всемирной ассоциации лауреатов (WLA) в области компьютерных наук или математики (World Laureates Association Prize in Computer Science or Mathematics) — аналога Нобелевской премии в этих дисциплинах.