Стивен Бойд: «Любой локальный оптимум выпуклой задачи является глобальным»

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

📉 Переломный момент и переход к практике 0:07

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

Лектор рекомендует слушателям уже сейчас установить библиотеку CVXPY для Python, поскольку синтаксис этого инструмента в точности повторяет изученные правила композиции и математические принципы. По словам Стивена Бойда, переход от абстрактных формул к коду помогает сделать обучение более реалистичным и наглядным. Текущее домашнее задание является последним чисто теоретическим и скучным, а со следующей недели начнется работа над действительно полезными и интересными задачами.

📊 Логарифмически вогнутые функции: теория и асимметрия 2:23

В математическом анализе существует целая индустрия расширений концепции выпуклости, включающая квазивыпуклость, псевдовыпуклость и логарифмическую выпуклость. Однако для практики необходим лишь небольшой набор этих инструментов, и одним из наиболее важных понятий, особенно в статистике, являются логарифмически вогнутые (log-concave) функции.

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

Если проэкспонировать неравенство Йенсена для логарифма такой функции, мы увидим, что значение функции от смеси аргументов оценивается не через арифметическое среднее, а через взвешенное геометрическое среднее. В качестве примеров логарифмически вогнутых функций лектор приводит степенные функции при неотрицательных показателях степени, а также плотности распределения вероятностей.

Классическим примером является плотность стандартного нормального (гауссовского) распределения. При взятии логарифма константа не влияет на кривизну, а экспонента превращается в отрицательную квадратичную форму, которая вогнута благодаря положительно определенной матрице сигма. Меры, обладающие такими плотностями, крайне важны в экономике и статистике, где они служат отличными регуляризаторами при аппроксимации данных. Примечательно, что функция распределения (CDF) стандартного гауссовского распределения также является логарифмически вогнутой, что доказывается в рамках сложного домашнего задания с подсказками. Любая функция распределения, порожденная логарифмически вогнутой плотностью, наследует это свойство.

📐 Свойства и алгебра логарифмической вогнутости 7:47

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

Свойства операций над логарифмически вогнутыми функциями включают следующие положения:

• Произведение двух логарифмически вогнутых функций всегда является логарифмически вогнутым, так как логарифм произведения равен сумме логарифмов, а сумма вогнутых функций вогнута.
• Сумма логарифмически вогнутых функций далеко не всегда сохраняет это свойство.

В качестве

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

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

🏭 Практическое применение: максимизация выхода годной продукции 12:04

Теорема об интеграле позволяет решать серьезные прикладные задачи, например, определять оптимальные параметры в микроэлектронике и промышленном производстве. Стивен Бойд приводит пример, где геометрическая область определяет набор допустимых параметров интегральной схемы (например, критический размер транзистора в 3 нанометра), а случайный вектор описывает производственные погрешности.

В этой модели используются следующие элементы:

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

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

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

⚖️ Обобщенные неравенства и коническая выпуклость 19:11

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

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

🛠️ Анатомия задачи оптимизации и её патологии 22:44

Выпуклые задачи оптимизации трактуемы, то есть их можно гарантированно решить на компьютере за разумное время. Профессор Бойд предлагает смотреть на задачу оптимизации как на объект в концепции объектно-ориентированного программирования, обладающий определенными атрибутами и полями.

Стандартная форма задачи включает в себя:

• Целевую функцию (objective), которую необходимо минимизировать.
• Список ограничений-неравенств типа «меньше или равно нулю».
• Список ограничений-равенств.

Математический термин «минимизировать» (minimize) отличается от операции нахождения минимума (min) конечного набора чисел. Если в прикладной области требуется максимизировать показатель (например, полезность или прибыль в экономике), задача легко сводится к стандартной форме путем минимизации функции с противоположным знаком. Аналогично, ограничения вида «больше или равно» переносятся в стандартную форму умножением на минус единицу.

Оптимальное значение задачи обозначается как $p^*$ (причем используется именно символ звездочки, а не астериск) и представляет собой инфимум целевой функции на множестве допустимых точек. В теории и практике оптимизации выделяются две основные патологии:

1. Недопустимость (infeasibility) — когда пересечение всех ограничений пусто. В этом случае по определению $p^* = +\infty$.
2. Неограниченность снизу (unbounded below) — когда целевая функция может стремиться к минус бесконечности на допустимом множестве. В этом случае $p^* = -\infty$.

В контексте управления рисками неограниченность снизу образно называют «эйфорическим срывом» (euphoric breakdown), когда алгоритм видит возможность бесконечного извлечения прибыли, что обычно свидетельствует о глупой ошибке в формулировке модели.

Множество оптимальных точек задачи всегда является выпуклым. Локально оптимальная точка представляет собой решение в некоторой ограниченной окрестности. На примере невыпуклой функции $x^3 - 3x$ Стивен Бойд демонстрирует, что точка локального минимума не является глобальным решением, так как функция уходит в минус бесконечность. В качестве контраста приводятся выпуклые функции: $1/x$ (где $p^*=0$, но оптимум недостижим на конечных значениях), $-\log x$ (неограниченна снизу) и $x \log x$ (отрицательная энтропия, имеющая единственный строгий минимум в точке $1/e$).

Ограничения делятся на явные и неявные (implicit). Неявные ограничения накладываются самой областью определения функций: например, для функции логарифма или $1/x$ переменная обязана быть строго положительной. Если алгоритму передать точку вне области определения, он выдаст критическую ошибку, так как не сможет даже вычислить значение функции. Задача без явных ограничений называется безусловной. Если целевая функция тождественно равна нулю, задача превращается в задачу поиска допустимой точки (feasibility problem), что часто применяется, например, для поиска условий отсутствия арбитража в экономике.

📐 Выпуклые задачи оптимизации и эквивалентность форм 45:07

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

Профессор иллюстрирует это на примере псевдокода функции prob.is_convex(), которая последовательно проверяет кривизну целевой функции и всех типов ограничений. При этом одна и та же задача может быть записана в невыпуклой форме (например, с нелинейным равенством или дробным неравенством) и в эквивалентной выпуклой форме.

Понятие эквивалентности задач аналогично идее сведения (reduction) в теории вычислительных систем: если мы можем легко трансформировать решение одной задачи в решение другой и наоборот, эти задачи эквивалентны, хотя их формальное описание и количество переменных могут различаться.

🏆 Глобальность оптимума и условия дифференцируемости 52:59

Фундаментальное свойство выпуклых задач состоит в том, что любой локальный оптимум автоматически является глобальным. Стивен Бойд вспоминает скепсис опытных инженеров, у которых заявление о достижении истинного глобального минимума в задаче с десятками тысяч переменных вызывало ощущение гордыни (хубриса) со стороны математиков. Однако это строгий математический факт.

Доказательство этого свойства строится геометрически:

1. Пусть существуют две рабочие точки: локальный минимум и гипотетический более выгодный глобальный минимум.
2. В силу выпуклости допустимого множества, весь отрезок между ними состоит из допустимых точек.
3. Ограничение выпуклой целевой функции на этот отрезок дает выпуклую функцию одной переменной.
4. График выпуклой функции, соединяющий эти две точки, обязан монотонно убывать в самом начале движения от локального минимума.
5. Это означает, что в любой сколь угодно малой окрестности локального минимума найдутся точки с меньшим значением критерия, что опровергает само предположение о локальной оптимальности.

Для дифференцируемых целевых функций критерием оптимальности точки является неотрицательность скалярного произведения градиента и вектора направления на любую другую допустимую точку. Геометрически это означает, что антиградиент (направление спуска) образует тупой угол со всеми разрешенными направлениями, а сам градиент задает опорную гиперплоскость к допустимому множеству.

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

🔄 Методы редукции: исключение и введение ограничений 1:05:18

Программные комплексы оптимизации часто выполняют автоматические редукции задач за кулисами. Одним из базовых методов является исключение линейных равенств через переход к базису нуль-пространства матрицы ограничений. На первый взгляд, уменьшение числа переменных (например, со 100 до 50 за счет 50 ограничений) кажется наивным пользователям выгодным шагом, однако Стивен Бойд предупреждает, что в крупномасштабных разреженных задачах такое преобразование может, напротив, ухудшить структуру матрицы и замедлить вычисления.

Существуют и обратные приемы:

• Введение дополнительных равенств для разделения переменных.
• Введение слабых переменных (slack variables), переводящих неравенства в равенства с добавлением условия неотрицательности. Термин «слабина» (slack) пришел из механики и ассоциируется со стальным тросом, связывающим два объекта: если они на максимальном расстоянии, трос натянут (активное ограничение), если ближе — появляется слабина (неактивное ограничение, избыточный зазор).
• Эпиграфная форма задачи, при которой целевая функция переносится в ограничения, а минимизируется вспомогательная скалярная переменная. Это доказывает универсальность линейного критерия оптимизации.
• Частичное (селективное) минимизирование по подмножеству переменных, что лежит в основе аналитических шагов динамического программирования и построения функций ценности (value functions).

🎯 Квазивыпуклая оптимизация и метод дихотомии 1:17:01

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

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

Алгоритм решения такой задачи сводится к методу бисекции (дихотомии) по целевому значению. На каждом шаге компьютер решает задачу поиска допустимой точки (feasibility problem) для текущего уровня. Если точка найдена, верхняя граница оптимума сдвигается вниз; если задача недопустима — нижняя граница сдвигается вверх.