Выпуклая оптимизация

📚 Краткое содержание

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

Освойте математическую основу и практические алгоритмы выпуклой оптимизации для инженерии и анализа данных.

Автор: Стивен Боуди, Ливен Ванденберге

Благодарности: Поддерживается частично Национальным научным фондом (NSF), а также благодаря вкладу студентов и коллег из Стэнфорда и Университета Калифорнии в Лос-Анджелесе, включая особые упоминания Аркади Немировского и Кишана Бахети.

🎯 Цели обучения

1. Определить компоненты математической задачи оптимизации, включая целевую функцию, ограничения и переменные.
2. Различать задачи на наименьшие квадраты, линейное программирование и выпуклую оптимизацию на основе их математических свойств.
3. Сравнить локальные и глобальные стратегии оптимизации и оценить вычислительную сложность каждого из них.
4. Определить и различать аффинные множества, выпуклые множества и конусы с использованием формальной комбинаторной записи.
5. Идентифицировать и представлять стандартные выпуклые множества, такие как евклидовы шары, эллипсоиды, полиэдры и положительно полуопределённый конус.
6. Применять операции, сохраняющие выпуклость, такие как пересечение, аффинные преобразования и перспективные функции, для проверки свойств множеств.
7. Идентифицировать и применять операции, сохраняющие выпуклость, включая точечную супремум аффинных функций и правила векторной композиции.
8. Вывести сопряжённую функцию Лагранжа для различных функций и применить неравенство Юнга.
9. Характеризовать квазивыпуклость с помощью подуровневых множеств и условий дифференцируемости первого и второго порядка.
10. Формулировать и трансформировать: преобразовывать исходные задачи оптимизации в стандартные выпуклые формы с использованием дополнительных переменных и устранения ограничений.

🔹 Урок 1: Введение в математическую оптимизацию

Обзор: Этот урок представляет основные концепции математической оптимизации, переходя от общей формулировки задачи к конкретным решаемым классам, таким как задачи на наименьшие квадраты и линейное программирование. Подчёркивается ключевое различие между выпуклой и невыпуклой оптимизацией, подробно описывается, как методы выпуклой оптимизации служат надёжным «водоразделом» для эффективности и предоставляют важные инструменты для решения более сложных нелинейных задач.

Результаты обучения:

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

🔹 Урок 2: Теория выпуклых множеств

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

Результаты обучения:

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

🔹 Урок 3: Выпуклые функции и их свойства

Обзор: Этот урок рассматривает продвинутые операции, сохраняющие выпуклость, такие как точечный супремум и специфические правила композиции, а также знакомит с функцией сопряжённой Лагранжа. Расширяется понятие выпуклости до квазивыпуклых и логарифмически вогнутых функций, а также исследуется выпуклость относительно обобщённых неравенств и матричных свойств, таких как дополнение Шура. Эти концепции составляют математическую основу для выявления и формулировки сложных задач оптимизации.

Результаты обучения:

• Идентифицировать и применять операции, сохраняющие выпуклость, включая точечный супремум аффинных функций и правила векторной композиции.
• Вывести сопряжённую функцию Лагранжа для различных функций и применить неравенство Юнга.
• Характеризовать квазивыпуклость с помощью подуровневых множеств и условий дифференцируемости первого и второго порядка.

🔹 Урок 4: Формулировка задач выпуклой оптимизации

Обзор: Этот урок охватывает формальную структуру и преобразование задач выпуклой оптимизации — от стандартных форм и условий оптимальности до конкретных классов задач, таких как линейное (LP), квадратичное (QP) и полулежащее программирование (SDP). Студенты узнают, как определять глобальную оптимальность, использовать метод бисекции для квазивыпуклых задач и применять скаляризацию для многокритериальной векторной оптимизации.

Результаты обучения:

• Формулировать и трансформировать: преобразовывать исходные задачи оптимизации в стандартные выпуклые формы с использованием дополнительных переменных и устранения ограничений.
• Анализировать оптимальность: применять критерий оптимальности на основе градиента для определения глобальной оптимальности точки.
• Классифицировать и решать: различать задачи LP, QP, SOCP, GP и SDP, а также применять специализированные методы, такие как метод бисекции для квазивыпуклых функций.

🔹 Урок 5: Двойственность Лагранжа и условия ККТ

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

Результаты обучения:

• Вывести двойную функцию Лагранжа и сформулировать двойственную задачу для различных оптимизационных проблем.
• Оценить связь между прямой и двойственной задачами с помощью слабой/сильной двойственности и условия допустимости Слейтера.
• Применить условия оптимальности ККТ для решения и проверки оптимальных решений в выпуклых и невыпуклых задачах.

🔹 Урок 6: Приближение, подгонка и регуляризация

Обзор: Этот урок исследует математические основы и практические приложения приближения решений систем линейных уравнений и подгонки функций к данным. Рассматриваются приближения на основе норм, включая штрафные функции и регуляризацию для управления выбросами и разреженностью, а также методы робастной оптимизации для работы с неопределённостью данных. Кроме того, рассматриваются методы подгонки функций при заданных ограничениях, таких как выпуклость и монотонность.

Результаты обучения:

• Формулировать и решать задачи приближения по норме, интерпретируя геометрические и статистические различия между методами наименьших квадратов, Чебышёва и L1.
• Проектировать и реализовывать регуляризованные модели приближения для достижения компромисса между ошибкой остатка, величиной решения и разреженностью.
• Создавать робастные рамки приближения, учитывающие неопределённость в матрице данных.

🔹 Урок 7: Статистическая оценка и вывод

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

Результаты обучения:

• Формулировать и решать задачи максимального правдоподобия (MLE) и логистической регрессии как задачи выпуклой оптимизации.
• Проектировать оптимальные детекторы с помощью линейного программирования (LP) и интерпретировать характеристики приемника (ROC).
• Применять непараметрические методы оценки, включая максимум энтропии и минимизацию расстояния Кульбака–Лейблера.

🔹 Урок 8: Геометрические задачи и классификация

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

Результаты обучения:

• Формулировать и решать задачи проекции и расстояний между выпуклыми множествами с использованием условий ККТ и двойственных представлений.
• Приближать сложные выпуклые множества экстремальными эллипсоидами максимального объёма и определять их эффективные коэффициенты.
• Вычислять различные центры множеств и применять их для робастной классификации и дискриминации.

🔹 Урок 9: Алгоритмы безусловной минимизации

Обзор: Этот урок охватывает теоретические основы и алгоритмическую реализацию безусловной минимизации для выпуклых функций. Подробно рассматриваются методы спуска — от первого порядка, градиентного спуска, до второго порядка, метода Ньютона. Значительная часть посвящена анализу сходимости, с акцентом на сильно выпуклость и аффинно-инвариантную теорию самосогласованности.

Результаты обучения:

• Определить сильно выпуклость и использовать её следствия для получения верхних границ на субоптимальность и расстояние до оптимума.
• Сравнить и противопоставить градиентный спуск и наискорейший спуск в метриках Евклида, квадратичной и L1.
• Вычислить шаг Ньютона и уменьшение Ньютона, объясняя, почему метод Ньютона является аффинно-инвариантным.

🔹 Урок 10: Минимизация при равенствах

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

Результаты обучения:

• Вычислять и интерпретировать шаг Ньютона и уменьшение для задач с равенствами.
• Демонстрировать эквивалентность метода Ньютона с равенствами и исключения этих ограничений.
• Реализовывать метод Ньютона с недопустимым стартом и объяснять его свойство снижения двойственного и прямого остатков.

🔹 Урок 11: Методы внутренней точки

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

Результаты обучения:

• Определить и построить логарифмические барьерные функции, охарактеризовать центральный путь и соответствующие ему двойственные точки.
• Реализовать барьерный метод, включая компромисс между шагами центрирования и внешними итерациями.
• Формулировать и решать задачи первоначальной фазы (Phase I) для нахождения строго допустимых начальных точек.