# Профессор Стивен Бойд о скрытой выпуклости и глобальных оптимумах

Источник: https://www.youtube.com/watch?v=AAjG1TQcL7c
Канал: Stanford Online
Опубликовано: 15.03.2024

---

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

## 📉 Логарифмическая вогнутость и асимметрия в статистике
[[JUMP:2:23]]

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

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

Если проанализировать неравенство Йенсена для логарифма и потенцировать его, свойство логарифмической вогнутости раскрывается через взвешенное геометрическое среднее аргументов вместо привычного арифметического среднего. Классическим примером такой структуры служит плотность стандартного нормального распределения в пространстве $\mathbb{R}^n$. При взятии логарифма от нормальной плотности константы не влияют на кривизну, а в остатке образуется отрицательная квадратичная форма, вогнутость которой гарантируется положительной определенностью матрицы ковариации. Стивен Бойд подчеркивает, что логарифмически вогнутые меры имеют колоссальное значение в экономике и статистике, выступая, например, в качестве весьма разумного регуляризатора при аппроксимации данных распределениями. Согласно его оценке, как минимум половина всех известных именованных плотностей вероятности обладают этим свойством.

## 🧪 Интегрирование, свертка и управление производственными рисками
[[JUMP:6:51]]

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

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

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

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

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

Этот абстрактный вывод находит прямое применение в инженерном деле и оптимизации производственных рисков. Если $C$ — выпуклое множество допустимых параметров, а случайная величина ошибок имеет логарифмически вогнутую плотность, то вероятность попадания системы в рамки спецификаций (производственный выход, или yield) является логарифмически вогнутой функцией от вектора целевых настроек оборудования. Профессор приводит жизненный пример из полупроводниковой индустрии: при проектировании микросхем инженер задает целевой критический размер элемента, например 3 нанометра. Реальный технологический процесс неизбежно вносит погрешности. Для максимизации процента выхода годных изделий интуитивно необходимо целиться точно в центр допустимого множества. Стивен Бойд указывает на важнейшее экономическое следствие: если предприятие устанавливает жесткую нижнюю границу рентабельности по выходу годной продукции (например, не менее 85%), то область допустимых целевых настроек фабрики гарантированно представляет собой выпуклое множество, что позволяет эффективно находить оптимальные режимы работы.

## 📐 Обобщенные неравенства и переход к практическим задачам
[[JUMP:19:11]]

Последним теоретическим расширением анализа становится концепция выпуклости относительно обобщенного неравенства, или $K$-выпуклость. В данном случае векторная функция отображает пространство $\mathbb{R}^n$ в $\mathbb{R}^m$, а классическое неравенство Йенсена переформулируется через собственный конус $K$. Ярким примером служит операция возведения в квадрат симметричной матрицы, которая сохраняет свойства конусной выпуклости. В то же время Стивен Бойд призывает аудиторию к осторожности: интуитивно понятные аналогии часто подводят, и, к примеру, матричная экспонента симметричной матрицы вопреки первому впечатлению выпуклой не является.

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

## 🏗️ Анатомия задачи оптимизации и её патологии
[[JUMP:23:39]]

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

1.  Целевую функцию (objective function), которую необходимо минимизировать.
2.  Список ограничений типа неравенств (inequality constraints).
3.  Список ограничений типа равенств (equality constraints).

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

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

* Если множество точек, удовлетворяющих всем жестким ограничениям, пусто, то по определению инфимум пустого множества равен плюс бесконечности ($p^* = +\infty$), а задача называется недопустимой (infeasible).
* Если целевая функция может убывать бесконечно на допустимом множестве, то оптимальное значение равен минус бесконечности ($p^* = -\infty$), а задача называется неограниченной снизу. В теории управления рисками для этого феномена существует выразительный термин — «эйфорический срыв» (euphoric breakdown).

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

Также критически важно разделять явные ограничения и неявные (implicit) ограничения, задающие естественную область определения функций (domain). Например, для функций $\log z$ или $1/x$ неявным требованием является строгая положительность аргумента. Если алгоритму предложить точку вне области определения, он даже не сможет вычислить значения уравнений, что Стивен Бойд называет грубейшей ошибкой проектирования. Частным случаем общей структуры выступает задача поиска допустимой точки (feasibility problem), где целевая функция тождественно равна нулю. Такие конфигурации моделируют серьезные практические проблемы, например, отсутствие арбитража на финансовых рынках.

## 🔍 Критерии выпуклости и иллюзия невыпуклых описаний
[[JUMP:44:54]]

Классическая задача выпуклой оптимизации накладывает жесткие рамки на геометрию уравнений: целевая функция и все ограничения-неравенства должны быть выпуклыми, а ограничения-равенства — исключительно аффинными (линейными вида $Ax = b$). На вопрос аудитории, почему равенства не могут быть выпуклыми, Стивен Бойд прямо отвечает: такова базовая дефиниция, без которой алгоритмы выпуклого поиска попросту теряют работоспособность.

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

$$\frac{x_1}{1 + x_2^2} \le 0$$

$$x_1 + x_2^2 = 0$$

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

## 👑 Локальный оптимум как глобальный гарант
[[JUMP:52:59]]

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

Профессор предлагает наглядное геометрическое доказательство от противного. Предположим, что точка $x_{local}$ является локальным минимумом, но существует некая далекая точка $\tilde{x}$ с более низким значением целевой функции. Поскольку допустимое множество выпукло, весь отрезок между ними также состоит из допустимых точек. Если ограничить выпуклую целевую функцию на этот отрезок, мы получим выпуклую функцию одной переменной, график которой обязан лежать ниже прямой, соединяющей значения в крайних точках. Следовательно, при сколь угодно малом смещении из точки $x_{local}$ в сторону $\tilde{x}$ значение функции начнет строго убывать. Это полностью опровергает предположение о том, что исходная точка была локальным минимумом, доказывая несостоятельность гипотезы о существовании нескольких локальных экстремумов.

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

## 🛠️ Инструменты редукции: от исключения равенств до бисекции
[[JUMP:1:05:18]]

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

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

1.  **Исключение ограничений-равенств.** Любое линейное уравнение $Ax = b$ можно параметризовать через частное решение $x_0$ и базисную матрицу нуль-пространства $F$, перейдя к новой переменной $z$ меньшей размерности. Профессор предостерегает от поверхностного вывода о том, что уменьшение числа переменных (например, со 100 до 50) всегда облегчает задачу. В реальных вычислениях структура и разреженность матриц могут сделать исходную задачу со 100 переменными значительно более быстродействующей.
2.  **Введение дополнительных равенств и слак-переменных (slack variables).** Линейное неравенство $a_i^T x \le b_i$ преобразуется в равенство путем добавления неотрицательной переменной зазора $s_i$. Стивен Бойд приводит наглядную физическую аналогию с натянутым стальным кабелем длиной в один метр между двумя объектами. Если объекты разнесены ровно на метр, трос натянут; если расстояние меньше — натяжение исчезает, и кабель провисает (становится слаком), что отражает строгое неравенство в системе.
3.  **Эпиграфная форма.** Любую задачу с нелинейным критерием качества можно свести к эквивалентной конфигурации с линейной целевой функцией, минимизируя искусственную переменную $t$ при условии, что исходная функция лежит в её эпиграфе ($f_0(x) \le t$). Это делает линейный критерий универсальным. Если доступный в интернете оптимизатор умеет работать только с линейными целями, достаточно переписать уравнения в эпиграфной форме.
4.  **Метод бисекции для квазивыпуклых задач.** Если целевая функция является квазивыпуклой (например, отношение выпуклой функции к строго положительной вогнутой), её глобальный минимум можно эффективно найти с помощью дихотомии (бисекции) по уровню $t$. На каждом шаге bisection-алгоритм решает выпуклую задачу проверки допустимости ограничений. Если точка найдена, верхняя граница оптимума сдвигается вниз, если нет — нижняя граница поднимается, что позволяет быстро локализовать глобальное решение.