Аннотация результатов, полученных в 2020 году
1) Впервые исследованы негладкие задачи оптимизации разности выпуклых функций (DC оптимизации) с коническими ограничениями, включая негладкие задачи полуопределённого программирования (негладкие задачи с матричными ограничениями). Для данного класса негладких задач предложено естественное условие регулярности ограничений и получено несколько эквивалентных условий оптимальности, тесно связанных с условиями оптимальности в терминах квазидифференциалов Демьянова-Рубинова. Также подробно исследовано два численных метода решения негладких задач DC оптимизации с коническими ограничениями, обобщающих один из наиболее популярных методов DC оптимизации, т.н. DC алгоритм, на случай задач с коническими ограничениями. Подробно исследована сходимость данных методов и, в частности, получено несколько достаточных условий сходимости одного из методов к допустимой точке, удовлетворяющей условиям оптимальности, из произвольного начального приближения, возможно не удовлетворяющего ограничениям в рассматриваемой задаче. Кроме того, детально изучены негладкие задачи DC оптимизации с матричными ограничениями. Рассмотрено два подхода к определению матричнозначных DC функций, исследована связь между этими подходами и приведён ряд примеров представления нелинейных матричнозначных функций, возникающих в различных приложениях, в виде разности выпуклых отображений. 2) Исследована выпуклая задача поиска расстояния между эллипсоидами и соответствующая невыпуклая многоэкстремальная задача поиска расстояния между границами эллипсоидов. На основе метода чередующихся направлений разработаны новые численные методы решения данных классов задач и изучены адаптивные правила настройки штрафного параметра для данных методов. Для метода нахождения расстояния между границами эллипсоидов предложена процедура рестарта (выбора нового начального приближения), позволяющая находить глобальный минимум в рассматриваемой многоэкстремальной задаче. Численные эксперименты с использованием метода глобальной оптимизации, гарантированно находящего глобальный минимум, показали, что предложенная процедура рестарта всегда позволяет найти глобальный минимум, даже если изначально алгоритм сходится к точке локального минимума. Кроме того, численные эксперименты в пространствах различных размерностей (от 2 до 2000) показали, что разработанные методы существенно превосходят все существующие аналоги по скорости сходимости. 3) Разработан метод заряженных шариков для нахождения проекции точки на множество с негладкой границей, определяемое максимумом конечного числа гладких функций. Для этого использовались гладкие аппроксимации функции максимума в окрестности существенно негладких точек. С помощью численных экспериментов была проверена работоспособность предложенного алгоритма. 4) Разработан новый вариационный метод решения линейных нестационарных интервальных систем дифференциальных уравнений вида dx/dt = A(t) x + b(t), где элементы матрицы A(t) и вектора b(t) в каждый момент времени лежат в некоторых заданных, изменяющихся во времени интервалах. Задача нахождения решения подобных систем с заданными граничными условиями сведена к задаче минимизации некоторого функционала в пространстве кусочно-непрерывных функций. Для данного функционала получены необходимые и достаточные условия минимума в конструктивной форме, на основе которых разработан вариационный численный метод решения исходной задачи. Работоспособность данного метода проверена на численных примерах. 5) Предложена новая факторизация матрицы ортогонального проектирования на подпространство и разработан простой алгоритм вычисления подобной факторизации, основанный на методе последовательного понижения ранга матрицы. Матрицы ортогонального проектирования на подпространство играют важную роль в методах условной оптимизации и наличие удобной факторизации подобной матрицы позволяет понизить трудоёмкость соответствующих методов. 6) Исследована задача поиска оптимальной по стоимости затрат на строительство траектории дороги. С помощью аппарата математического моделирования выведен интегральный функционал стоимости, аргументом в котором выступает функция, описывающая траекторию пути. Для полученной таким образом вариационной задачи выведено условие оптимальности, представляющее из себя интегро-дифференциальное уравнение, решение которого, описывающее оптимальную траекторию дороги, может быть эффективно найдено с помощью численных методов.

Аннотация результатов, полученных в 2021 году
1) Задачи проектирования точки на выпуклый многогранник и поиска расстояния между двумя выпуклыми многогранниками возникают в различных приложениях, включая негладкую оптимизацию, машинное обучение, задачи минимизации субмодулярных функций и др. В рамках данного проекта была разработана техника ускорения сходимости методов решения данных задач в случае, когда многогранники заданы в виде выпуклой оболочки конечного числа точек. Данная техника применима к произвольным методам решения этих задач и основана на сведении исходной задачи к конечной последовательности аналогичных задач значительной меньшей размерности. Было проведено большое количество численных экспериментов, в которых предложенная техника ускорения сходимости применялась к различным методам решения рассматриваемых задач. Численные эксперименты показали, что разработанная техника позволяет значительно сократить время вычислений и её эффективность увеличивается с ростом размерности пространства и количества точек в заданном выпуклом многограннике (выпуклых многогранниках). Для целого ряда методов (в частности, методов, основанных на решении задач квадратичного программирования, и МДМ метода) сокращение времени вычислений при использовании техники ускорения сходимости оказалось прямо пропорциональным количеству точек в многограннике/многогранниках (см. препринт https://arxiv.org/abs/2205.04553). 2) Численные методы, основанные на использовании точных штрафных функций, часто используются при решении задач математического программирования. Эффективность данных методов существенно зависит от величины штрафного параметра, что приводит к важной задаче построения автоматических правил настройки данного параметра, которая является малоизученной в негладком случае. В рамках данного проекта был разработан новый метод точных штрафных функций с адаптивным правилом автоматической настройки штрафного параметра для решения негладких невыпуклых задач оптимизации с ограничениями равенствами и неравенствами, задаваемыми в виде разности выпуклых функций. Предложенное правило автоматической настройки штрафного параметра основано на решении некоторых вспомогательных задач выпуклого программирования для определения подходящего значения штрафного параметра на каждой итерации, гарантирующего сбалансированное приближение построенной последовательности к допустимому множеству рассматриваемой задачи и убывание меры нестационарности. Была доказана корректность предложенного правила настройки штрафного параметра (т.е. конечная разрешимость всех соответствующих подзадач) и подробно изучена сходимость разработанного метода. В частности, были получены естественные достаточные условия ограниченности штрафного параметра. Предложенный метод был с успехом применён к решению двух дискретных негладких невыпуклых задач оптимального управления размерностью до 2000 переменных (см. препринт https://arxiv.org/abs/2107.01433). 3) Теория точных модифицированных функций Лагранжа является эффективным, но малоизвестным подходом к построению численных методов оптимизации. Главной особенностью данных функций является тот факт, что при выполнении некоторых естественных предположений, точки локального/глобального минимума этих функций одновременно по прямым и двойственным переменным соответствуют точкам локального/глобального минимума в исследуемой задаче математического программирования. Кроме того, в отличие от точных штрафных функций, данные функции не подвержены т.н. эффекту Маратоса, препятствующему достижению сверхлинейной скорости сходимости соответствующих численных методов. В рамках выполнения проекта теория модифицированных функций Лагранжа была распространена на случай задач оптимизации в бесконечномерных пространствах с ограничениями, задаваемыми с помощью нелинейных операторов. В частности, были получено несколько различных условий, гарантирующих совпадение точек локального/глобального минимума и стационарных точек точной модифицированной функции Лагранжа и соответствующих точек в исследуемой задаче условной оптимизации. Разработанная теория может быть применена для построения новых численных методов решения задач вариационного исчисления с ограничениями, некоторых классов задач оптимального управления и задач оптимизации с ограничениями в виде дифференциальных уравнений в частных производных. 4) С помощью аппарата конструктивного негладкого анализа были разработаны новые методы оптимизации выпуклых и невыпуклых кусочно-аффинных функций. В выпуклом случае был предложен метод, позволяющий сводить рассматриваемую задачу к двум задачам линейного программирования, размерность которых значительно меньше, чем размерность задачи, получаемой при прямом сведении задачи минимизации выпуклой кусочно-аффинной функции к линейному программированию. В невыпуклом случае были получены необходимые и достаточные условия глобальной оптимальности для кусочно-аффинных функций в терминах коэкзостеров, на основе которых был построен новый метод глобальной оптимизации подобных функций. 5) Непрерывные кусочно-аффинные функции находят широкое применение в вычислительной математике. В одномерном случае такие функции называются ломаными. Были исследованы различные аналитические представления ломаных, как в формах, принятых в теории полиномиальных сплайнов, так и в виде разности максимумов двух конечных семейств аффинных функций. Была установлена связь между этими представлениями и предложены методы перехода от одной формы представления заданной ломаной к любой другой форме. 6) Был разработан новый вариационный численный метод нахождения решения систем обыкновенных дифференциальных уравнений, содержащих в правой части управления, разрывные по фазовым переменным. С помощью разработанного ранее членами научного коллектива аппарата решения дифференциальных включений, построен вариационный метод нахождения траекторий данной системы, движущейся в скользящем режиме и удовлетворяющей некоторым дополнительным условиям, например, имеющей заданные начальное и конечное положения. Данный метод состоит в сведении исходной задачи к задаче минимизации некоторого вариационного функционала специальной структуры, для исследования и решения которой был применён аппарат конструктивного негладкого анализа.

Аннотация результатов, полученных в 2022 году
1) Подробно разработана теория гиподифференциалов негладких выпуклых функций, определённых на банаховых пространствах. Доказана качественно новая теорема о характеризации гиподифференцируемости негладких выпуклых функций и структуре их гиподифференциалов, построено исчисление гиподифференциалов для функций, определённых на банаховых пространствах, и изучено свойство липшицевости гиподифференциалов в негладком случае. На основе построенной теории гиподифференциалов выпуклых функций, изучена сходимость метода гиподифференциального спуска для минимизации негладких выпуклых функций, определённых на гильбертовых пространствах. Доказана скорость сходимость О(1/k) данного метода в общем случае и линейная скорость сходимости в некоторых частных случаях. Кроме того, с помощью общей теории ускоренных градиентных методов выпуклой оптимизации, построенной Ю.Е. Нестеровым и др., предложена ускоренная версия метода гиподифференциального спуска для минимизации негладких выпуклых функций и доказано, что данный метод обладает более высокой скоростью сходимости О(1/k^2), аналогичной скорости сходимости ускоренных градиентных методов гладкой выпуклой оптимизации. 2) Разработан и подробно изучен адаптивный метод точных штрафных функций для решения негладких задач оптимального управления с негладкими фазовыми и смешанными ограничениями неравенствами, целевая функция и ограничения которой являются DC-функциями (т.е. функциями, представимыми в виде разности выпуклых функций). Данный метод допускает неточное (приближённое) решение всех вспомогательных выпуклых подзадач и использует адаптивное правило настройки штрафного параметра, позволяющее гарантировать сбалансированное убывание некоторой меры нестационарности и расстояния до множества допустимых траекторий и управлений. Кроме того, на каждой итерации метода осуществляется немонотонных линейный поиск с адаптивными правилами настройками параметров поиска, учитывающими поведение последовательности итераций метода. Исследована сходимость метода, доказана корректность адаптивных правил настойки параметров и критериев остановки, а также доказана сходимость метода к точкам, приближённо удовлетворяющим условиям оптимальности. Приведены численные примеры, продемонстрировавшие эффективность немонотонного линейного поиска (сокращение количества итераций и времени вычислений при его использовании) и робастность разработанного метода к ошибкам вычислений и неточности решений вспомогательных подзадач. 3) Теория точных модифицированных функций Лагранжа применена к исследованию различных задач вариационного исчисления с ограничениями и задач оптимального управления. Были построены качественно новые модифицированные функции Лагранжа для задач вариационного исчисления с дополнительными ограничениями на границе рассматриваемой области, многомерных задач вариационного исчисления с изопериметрическими ограничениями и многомерных задач вариационного исчисления с неголономными ограничениями равенствами. Были получены легко проверяемые условия на данные задачи, гарантирующие, что построенные модифицированные функции Лагранжа является точными, то есть что задача безусловной минимизации этих функций Лагранжа одновременно по прямым и двойственным переменным эквивалентна соответствующим задачам вариационного исчисления с ограничениями. Также была построена новая гладкая модифицированная функция Лагранжа для выпуклых задач оптимального управления линейными эволюционными уравнениями с закреплённым правым концом. Было показано, что в случае, когда рассматриваемая система является точно управляемой, задача минимизации предложенной модифицированной функции Лагранжа, представляющая из себя задачу оптимального управления со свободным правым концом, эквивалентна исходной. Более того, было доказано, что все стационарные точки данной модифицированной функции Лагранжа являются точками глобального минимума, несмотря на то, что эта функция является невыпуклой. 4) Рассмотрена задача нахождения решений дифференциальных включений с заданными граничными условиями, удовлетворяющих фазовым ограничениям равенствам (т.е. лежащих на некоторой заданной поверхности), в предположении, что опорная функция многозначного отображения, стоящего в правой части включения, представима в виде максимума конечного числа непрерывно дифференцируемых (по фазовым координатам) функций. С помощью аппарата опорных функций данная задача сведена к вариационной задаче минимизации некоторого негладкого функционала в пространстве кусочно-непрерывно дифференцируемых функций. С помощью аппарата конструктивного негладкого анализа доказано, что полученный минимизируемый функционал является супердифференцируемым, сформулированы необходимые условия минимума данного функционала в терминах супердифференциала и построен метод супердифференциального спуска для нахождения стационарных точек этого функционала. Доказана «слабая» сходимость предложенного метода. Работа предложенного вариационного метода продемонстрирована на иллюстративных примерах. 5) Разработан новый подход к решению негладких задач оптимизации на матричных многообразиях, основанный на сведении таких задач к задачам DC (Difference-of-Convex functions) оптимизации с коническими ограничениями (cone constrained optimization). Для решения таких задач предложено воспользоваться методом точных штрафных функций для негладких задач оптимизации с коническими ограничениями, разработанным членами научного коллектива ранее. Кроме того, было предложено новое правило настройки штрафного параметра для данного метода. Разработанный метод был применён к задаче нахождения разряженных решений (sparse solutions) вариационных задач, возникающих в физике и представляющих из себя негладкую задачу оптимизации на многообразии Штифеля, и к задаче упаковке сфер на многообразии Грассманна. Результаты численных экспериментов показали высокую эффективность предложенного метода и его применимость к негладким задачам оптимизации на матричных многообразиях размерности порядка 10^4. Кроме того, численные эксперименты показали, что предложенное новое правило настройки штрафного параметра позволяет методу находить более глубокие точки локального минимума (точки с лучшим значением целевой функции). Так, в задаче упаковки сфер на многообразии Грассмана, разработанный численный метод с новым правилом настройки штрафного параметра нашёл допустимую точку с лучшим значением целевой функции (более глубокий локальный минимум), чем в ранее опубликованных работах по данной тематике. 6) Исследован вопрос эквивалентности результатов, описанных в терминах используемых в рамках конструктивного негладкого анализа кодифференциалов и коэкзостеров негладких функций, а также связь этих объектов с DC-функциями. Доказана эквивалентность ряда условий ограниченности и оптимальности, сформулированных с помощью этих понятий. Кроме того, изучена связь между неоднородными аппроксимациями негладких функция и производными по направлениям и проблема формулировки условий оптимальности в терминах таких аппроксимаций.