Аннотация:
Задачи на нахождение максимума или минимума приходится решать постоянно и при этом важно глyбокое понимание математической теории оптимизации. С задачами на экстремум знакомятся ещё в школе при изучении производной. Однако аппарат производных (или градиентов в случае функций многих переменных) годится не для всех оптимизационных задач. Можно к примеру рассмотреть задачу о нахождении наименьшего круга, покрывающего заданный набор точек (т.е. нахождения некоторого аналога описанной окружности около многоугольника). Смысл задачи очевиден: где поставить передатчик так, чтобы наиболее удалённый из нужных пунктов находился как можно ближе? Целевая функция такой задачи не будет дифференцируемой, причём на бесконечном множестве точек.Такие задачи называют негладкими и вместо градиентов для них используют так называемые субградиенты. Мы рассмотрим ещё несколько примеров известных негладких оптимизационных задач, связанных с анализом данных (регрессия LASSO, задача о восстановлении малоранговой матрицы с неевклидовой метрикой качества). Также поговорим об основных фактах из теории субградиентов и численных методах для решения негладких оптимизационных задач, поясним некоторые принципиальные особенности использования методов с использованием субградиентов. Поясним, почемy субградиентные методы можно считать оптимальными для негладких липшицевых задач в случае пространства большой размерности. В заключении скажем несколько слов о некоторых современных работах в этой области и предложим
некоторые направления для возможных исследований (в частности, кyрсовых и дипломных работ).
|
