|
Оглавление
Введение
В математическом программировании, как и во многих других областях вычислительной математики, конечным результатом развития общей теории являются методы решения определенных классов задач. При этом важным показателем зрелости теории выступает перечень свойств, наличие которых у данного метода признается желательным. Расширение этого перечня неизбежно приводит к пересмотру сложившихся представлений о возможностях традиционных алгоритмов, стимулирует разработку новых вычислительных процедур. К концу 70-х годов в теории оптимизации постепенно сформировалось новое направление, связанное с оценкой эффективности метода по его глобальной скорости сходимости. Если раньше исследователей прежде всего интересовал вопрос о том. сходится та данный метод и какова оценка его скорости сходимости в окрестности точки минимума, то с этого времени стали все чаще появляться работы, в которых выводились оценки скорости сходимости существующих алгоритмов, "работавшие" с первой же итерации метода. Важным вкладом в развитие этого направления стало выявление А.С.Немировским и Д.Б.Юдиным нижних оценок сложности традиционных классов экстремальных задач. Созданная ими теория сложности дала мощный импульс для разработки новых вычислительных алгоритмов по двум причинам. Во-первых, были установлены потенциальные границы для скорости сходимости методов оптимизации на различных классах экстремальных задач, сформулировано понятие оптимального метода. А во-вторых, среди существовавших к тому времени алгоритмов лишь два (метод субградиентного спуска и метод центров тяжести) можно было отнести к оптимальным. К настоящему времени арсенал оптимальных методов удалось существенно расширить. Подтверждением продуктивности нового направления стало обоснование Л.Г.Хачияном полиномиальной разрешимости задачи линейного программирования (ЛП), опиравшееся на глобальную оценку скорости сходимости метода эллипсоидов. С помощью методики Л.Г.Хачияна любой итеративный метод решения задачи ЛП, сходящийся со скоростью геометрической прогрессии, знаменатель которой зависит лишь от числа переменных, может быть превращен в полиномиальный алгоритм ЛП. С такой интерпретацией связан бурный прогресс в построении полиномиальных алгоритмов ЛП, наблюдавшийся в последние годы. Результаты, связанные с проблематикой оптимальных алгоритмов нелинейного программирования, полиномиальных алгоритмов ЛП, в силу их новизны еще не успели найти отражения в монографической литературе. В настоящей монографии делается попытка восполнить этот пробел. Остановимся вкратце на содержании монографии. Первая глава носит вводный характер и содержит необходимые для дальнейшего сведения из выпуклого анализа. Рассматриваются традиционные классы гладких выпуклых,- равномерно выпуклых и квазивыпуклых функций, исследуются их свойства. Вводится новый класс квазиоднородных функций, основная характеристика которых оказывается инвариантной относительно линейной замены переменных. Во второй главе описывается аппарат дифференцирования негладких функций, позволяющий конструктивно вычислять дифференциальные характеристики, необходимые для методов негладкой оптимизации. Предлагается новый способ введения аналога производной негладкой функции, при котором таким аналогом оказывается линейный оператор - лексикографическая производная. Для , однозначного определения лексикографической производной в точке достаточно зафиксировать произвольный базис в пространстве переменных. Класс функций, у которых можно вычислять лексикографические производные, - лексикографически гладкие функции, является линейным пространством, содержит все дифференцируемые, выпуклые и квазидифференцируемые по Демьянову-Рубинову функции и все суперпозиции лексикографически гладких функций. При этом для пересчета лексикографических производных таких функций при операции суперпозиции удается выписать формулы по своей простоте сравнимые с формулами классического дифференциального исчисления. Лексикографические производные негладких функций естественным образом согласуются с ранее известными дифференциальными объектами. Так, лексикографический градиент гладкой функции совпадает с ее градиентом по Гато, лексикографический градиент выпуклой функций является крайней точкой ее субдифференциала, а лексикографический градиент квазивыпуклой функции - опорным функционалом к ее множеству уровня. Исследуются свойства лексикографически гладких функций, формулируются необходимые условия безусловного экстремума. Устанавливается справедливость формулы Ньютона-Лейбница для лексикографических производных по любому фиксированному базису в пространстве переменных. Демонстрируются возможности лексикографических производных как инструмента, анализа негладких функций. В третьей главе рассматриваются методы минимизации негладких выпуклых и квазивыпуклых функций: метод субградиентного спуска, метод центров тяжести, метод эллипсоидов. Обосновываются оценки их скорости сходимости. Описывается версия метода растяжения пространства в направлении градиента, применимого для минимизации квазиоднородных функций. Четвертая глава посвящена описанию оптимальных методов решения гладких.экстремальных задач Рассматриваются оптимальные методы минимизации сильно выпуклых функций, обладающих липшицевым градиентом, метод минимизации функций с гельдеровым градиентом, автоматически настраивающийся на параметры гладкости целевой функции, метод минимизации негладких сверток гладких функций, обладающий оценкой скорости сходимости, характерной для гладкого случая, методы решения условных задач. В пятой главе рассматриваются итеративные методы решения задач линейного и квадратичного программирования. Наряду с обоснованием полиномиальности метода внутенних штрафных функций, исследуются вычислительные схемы и новых методов: метода параллельных траекторий (прямого и двойственного) и полиномиального метода квадратичного программирования, основанного на использовании оптимальных алгоритмов минимизации гладких функций. Трудоемкость решения соответствующей задачи у лучших из этих методов оценивается произведением логарифма требуемой точности на полином третьей степени от размерности задачи. В приложении» написанном А.С.Немировским, приведены основные результаты из теории сложности, относящиеся к рассмотренным постановкам задач.
Об авторе
 Нестеров Юрий Евгеньевич Доктор физико-математических наук. С 1993 г. работает в Католическом университете города Лувен в Бельгии; ныне состоит в должности ординарного профессора Католического университета Лувена. Его основные результаты связаны с построением новых эффективных методов выпуклой оптимизации. Опубликовал более 150 статей и пять монографий. Среди его главных достижений можно отметить разработку полиномиальных методов внутренней точки, быстрых градиентных методов и современных методов второго и более высоких порядков. Лауреат нескольких престижных международных премий (Данцига, фон Неймана, Ланчестера и др.). Член Европейской академии наук и Национальной академии наук США.
В 2023 г. совместно с А. С. Немировским удостоен Премии Всемирной ассоциации лауреатов (WLA) в области компьютерных наук или математики (World Laureates Association Prize in Computer Science or Mathematics) — аналога Нобелевской премии в этих дисциплинах. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
