Стивен Бойд в очередной лекции курса EE364A углубляется в прикладные аспекты выпуклой оптимизации, разбирая задачи планирования экспериментов и геометрические аппроксимации. В центре внимания — поиск оптимальных эллипсоидов, которые позволяют эффективно описывать сложные выпуклые множества, минимизировать ошибки измерений и даже определять «выбросы» в данных.
🎓 Введение: о студенческих решениях и ошибках в учебниках 0:05
Лекция началась с традиционной доли юмора: Стивен Бойд поздравил студентов с прохождением промежуточного экзамена (midterm) и сделал «публичное признание». По словам профессора, преподавательский состав без тени смущения заимствует удачные решения студентов для официальных ответов к домашним заданиям. Бойд считает это честью для учащихся: «Целые поколения будущих студентов будут читать ваше решение и удивляться, кто до этого додумался».
Кроме того, Стивен Бойд отметил активную помощь студентов в поиске опечаток и фактических ошибок в его книге по выпуклой оптимизации. На данный момент найдено как минимум две существенные неточности, и список продолжает расти, что, по мнению лектора, свидетельствует о глубоком погружении аудитории в предмет.
📊 Планирование эксперимента: как выжать максимум из датчиков 9:15
Основная техническая часть лекции посвящена задаче планирования эксперимента (experiment design). Суть задачи заключается в выборе наилучших измерений из набора доступных вариантов для минимизации ошибки оценки вектора $x$.
Ключевые параметры модели:
- Линейные измерения: $y_i = a_i^T x + w_i$, где $a_i$ — вектор измерения, а $w_i$ — шум.
- Шум: Стивен Бойд нормализует стандартное отклонение шума до единицы.
- Отношение сигнал/шум (SNR): Качество измерения напрямую зависит от величины (нормы) вектора $a_i$. Чем больше вектор, тем выше SNR.
При использовании метода наименьших квадратов ошибка оценки характеризуется ковариационной матрицей $E = (\sum a_i a_i^T)^{-1}$. Геометрически это соответствует эллипсоиду доверия: мы хотим, чтобы этот эллипс был как можно меньше.
Проблема «наилучшего датчика»
Стивен Бойд приводит пример ошибочной логики: выбрать один самый мощный датчик с максимальным SNR и использовать только его. Однако в этом случае матрица $E$ станет вырожденной (ранга 1). Это означает, что мы получим отличную точность в одном направлении, но будем иметь нулевую информацию в остальных $n-1$ измерениях. Следовательно, для хорошей оценки необходим «пакет» разнообразных измерений.
🛠 Релаксация и D-оптимальное проектирование 18:18
Поскольку количество использований конкретного датчика должно быть целым числом, задача планирования эксперимента изначально является комбинаторной (целочисленной). Стивен Бойд предлагает использовать стандартный прием — релаксацию.
Вместо целых чисел $m_i$ вводятся доли $\lambda_i$, которые показывают, какую часть общего бюджета экспериментов занимает данный тип измерения.
- Мы решаем задачу в непрерывных переменных $\lambda_i \in [0, 1]$.
- Затем полученные значения округляются до ближайших целых чисел, соответствующих бюджету.
- По мнению Бойда, если общий бюджет экспериментов $m$ велик по сравнению с количеством вариантов $p$, такая релаксация дает результат, крайне близкий к глобальному оптимуму.
D-оптимальность
Одним из самых популярных методов скаляризации является D-оптимальное проектирование (D-optimal design), где минимизируется логарифм определителя матрицы ошибок $\log \det(\sum \lambda_k v_k v_k^T)^{-1}$. Геометрически это эквивалентно минимизации объема эллипсоида доверия.
Интересна связь с двойственной задачей: поиск D-оптимального дизайна эквивалентен поиску эллипсоида минимального объема, который накрывает все возможные векторы измерений $v_k$. Те точки, которых касается этот эллипс, и являются наиболее полезными экспериментами.
📐 Геометрия эллипсоидов: Лёвнер-Джон и внешние границы 43:08
Стивен Бойд переходит к классической задаче — поиску эллипсоида минимального объема, накрывающего заданное множество $C$. Такой эллипсоид называется эллипсоидом Лёвнера-Джона (Lowner-John ellipsoid).
Математическая постановка:
Для описания эллипсоида используется параметризация $\mathcal{E} = {x \mid |Ax + b|_2 \le 1}$. Задача формулируется как минимизация $\log \det A^{-1}$ при условии, что все точки множества $C$ попадают внутрь.
Бойд выделяет важные нюансы вычислительной сложности:
- Для конечного набора точек или многогранника, заданного вершинами, задача решается легко и быстро.
- Для многогранника, заданного неравенствами, задача внезапно становится NP-трудной. Профессор поясняет: даже проверка того, накрывает ли конкретный эллипс заданный неравенствами многогранник, в общем случае крайне сложна.
Практическое применение: «Эллипсоидное очищение»
Стивен Бойд описывает метод удаления выбросов (ellipsoidal peeling). Мы строим минимальный накрывающий эллипсоид и смотрим, какие точки оказались на его границе. Если это «подозрительные» данные, мы их удаляем и повторяем процесс. Для выбора самых вероятных кандидатов на удаление Бойд советует смотреть на двойственные переменные (dual variables) — чем больше значение переменной у точки, тем сильнее она «распирает» эллипс и тем выше её влияние на результат.
🔍 Вписанные эллипсоиды и универсальная аппроксимация 1:02:01
Обратная задача — поиск эллипсоида максимального объема, вписанного в множество — ведет себя зеркально. Она легко решается для многогранников, заданных неравенствами, но становится NP-трудной для множеств, заданных как выпуклая оболочка вершин.
Теорема об аппроксимации
Бойд приводит впечатляющий математический факт: любое выпуклое множество в $n$-мерном пространстве можно аппроксимировать эллипсоидом с точностью до коэффициента $n$ (или $\sqrt{n}$, если множество симметрично).
Это означает следующее:
- Если взять эллипсоид Лёвнера-Джона и сжать его в $n$ раз относительно центра, он гарантированно окажется внутри множества.
- Для симметричных множеств коэффициент сжатия/расширения составляет всего $\sqrt{n}$.
По словам профессора, это делает эллипсоиды «универсальными аппроксиматорами» для выпуклых тел. Именно поэтому квадратичные методы управления (например, в авиации) работают так хорошо, даже если реальные ограничения системы имеют сложную неквадратичную форму.
🎯 Центрирование: Чебышёв и аналитический центр 1:15:56
В завершение лекции Бойд коснулся темы «центров» выпуклых множеств. В одномерном случае (интервал) центр очевиден, но в высоких размерностях определений много:
- Центр Чебышёва: центр самого большого вписанного шара.
- Центр максимального вписанного эллипсоида: часто более эффективен для вытянутых структур.
- Аналитический центр: точка, максимизирующая произведение расстояний (маржей) до границ.
Аналитический центр особенно важен для алгоритмов внутренней точки, которыми студенты займутся в ближайшие недели.
