# Профессор Стивен Бойд объяснил конструктивный анализ выпуклости в Стэнфорде Источник: https://www.youtube.com/watch?v=U2HRwA7XePU Канал: Stanford Online Опубликовано: 14.03.2024 --- В лекции профессора Стэнфордского университета СТИВЕНА БОЙДА (Stephen Boyd) рассматривается так называемое «исчисление выпуклости» — конструктивный подход к анализу математических функций. Вместо редкого и трудоёмкого вычисления гессианов или проверки по базовому определению, на практике выпуклость сложных выражений доказывается пошаговым применением правил сохранения свойств. Лектор подробно разбирает операции композиции, частичной минимизации, сопряжения, а также практические обобщения выпуклости на примере квазивыпуклых функций и финансового показателя внутренней нормы доходности (IRR). ## 🛠️ Базовые операции и конструктивный анализ выпуклости [[JUMP:0:05]] Проверка математических функций на выпуклость или вогнутость напрямую по определению или через матрицу Гессе (гессиан) в реальных инженерных задачах встречается крайне редко. По словам Стивена Бойда, большинство специалистов на практике используют конструктивный подход — своеобразное исчисление, где из базового набора выпуклых функций и множеств строятся сложные структуры с помощью правил, гарантированно сохраняющих выпуклость. Именно по такому принципу работает современное программное обеспечение для оптимизации. Простейшие правила включают в себя базовые алгебраические трансформации: * Умножение на положительный скаляр: если функция изгибается вверх, то при её умножении на положительный коэффициент (например, 3.7) она просто станет изгибаться сильнее, сохраняя свойство выпуклости. * Сумма выпуклых функций: сложение двух и более выпуклых функций всегда дает выпуклую функцию. * Прекомпозиция с аффинной функцией: выражение вида $f(Ax + b)$ сохраняет выпуклость исходной функции $f$, что, по заверениям лектора, можно легко доказать самостоятельно всего в три строки. ## 📈 Поточечный максимум и супремум функций [[JUMP:2:16]] Поточечный максимум семейства выпуклых функций всегда остается выпуклым. Стивен Бойд иллюстрирует это свойство на примере кусочно-линейных функций: хотя их традиционно описывают через разбиение Вороного в пространстве $R^n$, в контексте выпуклого анализа их гораздо эффективнее представлять как максимум некоторого набора аффинных функций. Ярким примером применения этого правила выступает функция суммы $r$ крупнейших элементов вектора. Данная функция недифференцируема и не имеет гессиана, однако она выпукла, поскольку математически эквивалентна максимуму из всех возможных $\binom{n}{r}$ линейных комбинаций элементов вектора. Стивен Бойд отмечает, что это определение можно расширить даже на нецелые числа: например, «сумма 5.6 крупнейших элементов» будет означать сумму 5 самых больших компонентов плюс 0.6 от шестого по величине значения. Такая экзотическая функция тоже будет выпуклой. Данное свойство масштабируется на супремум бесконечного семейства выпуклых функций $f(x, y)$, параметризованных переменной $y$ из произвольного множества $A$. Множество $A$ при этом может иметь абсолютно любую природу, включая сложные комбинаторные структуры, такие как набор всех путей в графе или множество перестановок. Примерами супремумов, сохраняющих выпуклость, служат: * Опорная функция множества. * Расстояние до самой дальней точки множества, что находит прямое практическое применение при проектировании беспроводных сетей, когда инженеру необходимо оптимально разместить базовую станцию для покрытия удаленных контрактных зон. * Максимальное собственное значение симметричной матрицы. Касаясь темы матриц, Стивен Бойд делает историческое отступление: если для корней многочленов второй, третьей и четвертой степеней существуют аналитические формулы, то около 200 лет назад математики доказали отсутствие формулы в радикалах для уравнений пятой степени и выше. Тем не менее, численно собственные значения вычисляются компьютерными системами ежедневно, а сама функция максимального собственного значения выпукла, поскольку является супремумом выражения $y^T X y$, которое строго линейно относительно матрицы $X$. ## 🔗 Правила композиции функций и «глупая арифметика знаков» [[JUMP:13:31]] Правила композиции составляют фундамент для построения и проверки сложных оптимизационных моделей. В простейшем одномерном случае композиция функций $h(g(x))$ выпукла, если внутренняя функция $g$ выпукла, а внешняя функция $h$ выпукла и монотонно возрастает. Классическим примером служит экспонента от выпуклой функции ($e^{g(x)}$). Если же внешняя функция $h$ выпукла, но монотонно убывает, то для сохранения выпуклости всей композиции внутренняя функция $g$ обязана быть вогнутой. Пример такого сочетания — функция $1/g(x)$ для положительной вогнутой функции $g$. Для быстрого восстановления в памяти этих правил лектор предлагает использовать мнемонический метод, названный им «глупой арифметикой знаков». Если предположить дифференцируемость функций в $R^1$, то вторая производная композиции раскрывается по формуле: $$f''(x) = h'(g(x))g''(x) + h''(g(x))(g'(x))^2$$ Стивен Бойд с иронией объясняет базовые математические принципы: произведение двух отрицательных чисел (когда $h$ убывает, а $g$ вогнута) дает положительное число, а произведение неотрицательного числа на квадрат другого также неотрицательно. Сумма двух неотрицательных величин дает неотрицательный результат, что и доказывает итоговую выпуклость функции. В многомерном векторном случае для функции $h(g_1(x), \dots, g_k(x))$ действует универсальное сквозное правило: каждый её аргумент должен быть либо аффинным, либо выпуклым (при условии возрастания функции $h$ по этому аргументу), либо вогнутым (при условии убывания $h$). Это системное правило покрывает практически все частные случаи, включая сложение или взятие максимума функций. Примером служит функция log-sum-exp (или softmax) от набора выпуклых функций, повсеместно применяемая в качестве функции потерь при статистическом моделировании. ### Программная верификация и сложные выражения Методология Disciplined Convex Programming (DCP — дисциплинированное выпуклое программирование) составляет технологическую основу современного софта для выпуклой оптимизации. Программа автоматически верифицирует код пользователя, обходя дерево выражений от «листьев» к корню и размечая каждый узел как выпуклый, вогнутый или аффинный на основе правил композиции. В качестве примера сложной недифференцируемой функции лектор приводит выражение: $$(\sum x_i)^2 / \min(2, \sqrt{x_3})$$ Браться за аналитическое вычисление гессиана здесь бессмысленно, но через правила DCP выпуклость доказывается тривиально. Сама по себе функция $x^2/y$ выпукла при $y > 0$, не монотонна по первому аргументу в общем случае (но возрастает при $x \ge 0$) и монотонно убывает по второму аргументу $y$. В рассматриваемом выражении числитель аффинен перед возведением в квадрат, а знаменатель представляет собой минимум двух вогнутых функций (константы 2 и квадратного корня), что дает вогнутый результат. Поскольку вогнутый знаменатель находится в позиции убывания для функции $x^2/y$, вся композиция признается строго выпуклой. ## 📉 Частичная минимизация и совместная выпуклость [[JUMP:37:32]] Если функция $f(x, y)$ является совместно выпуклой по переменным $x$ и $y$, то её минимизация по одной из переменных $y$ на выпуклом множестве сохраняет выпуклость по оставшейся переменной $x$. Этот принцип частичной минимизации лежит в основе динамического программирования, где последовательное исключение переменных формирует так называемую функцию ценности (value function). Стивен Бойд акцентирует внимание на жесткости условия совместной выпуклости: функция может быть выпуклой по $x$ при любом фиксированном $y$ и выпуклой по $y$ при любом фиксированном $x$, но не обладать совместной выпуклостью. Классический контрпример — простейшая билинейная функция $xy$. Она абсолютно линейна по каждой переменной в отдельности, однако в плоскости $xy$ под углом 45 градусов она изгибается вниз, формируя седловую поверхность, и не является совместно выпуклой. Примером успешной частичной минимизации выступают совместные квадратичные формы, которые замкнуты относительно этой операции. Исключение переменной из квадратичной формы приводит к понятию дополнения Шура (Schur complement). Дополнение Шура повсеместно возникает в численном линейном анализе, теории цепей в электротехнике, прикладной механике, экономике и алгоритмах расчета условных распределений для гауссовских случайных векторов. ## 🔍 Перспектива функции и сопряжение [[JUMP:43:57]] Перспективой функции $f(x)$ называется математическое выражение $g(x, t) = t \cdot f(x/t)$ при условии $t > 0$. Если исходная функция выпукла, то и её перспектива гарантированно будет выпуклой. Например, перспектива для базовой квадратичной функции $x^T x$ превращается в сумму квадратично-линейных выражений $\sum x_i^2 / t$, выпуклость которых теперь можно констатировать без вычисления матрицы Гессе. Для отрицательного логарифма перспективой выступает функция $-t \log(x/t)$, которая лежит в основе теории информации и определяет относительную энтропию (расхождение Кульбака — Лейблера). ### Сопряжённая функция и её экономический смысл Сопряжённая функция (или преобразование Фенхеля) определяется через оптимизационную задачу: $$f^*(y) = \sup_x (y^T x - f(x))$$ Удивительный факт заключается в том, что сопряженная функция всегда выпукла, даже если исходная функция $f(x)$ не являлась выпуклой. Это объясняется тем, что операция по своей структуре представляет собой супремум семейства аффинных функций по переменной $y$. Стивен Бойд предлагает наглядную экономическую интерпретацию сопряжения: * Пусть вектор $x$ — это объемы производства $n$ различных видов товаров, а функция $f(x)$ задает внутренние финансовые затраты компании на их выпуск. * Если вектор $y$ отражает текущие рыночные цены на эти товары, то скалярное произведение $y^T x$ определяет валовую выручку предприятия. * Разность $y^T x - f(x)$ в таком случае является чистой прибылью. В данном контексте сопряженная функция $f^*(y)$ имеет прозрачный смысл — она показывает максимально возможную (оптимальную) прибыль компании как прямую функцию рыночных цен. В математике слово «сопряжение» обычно ассоциируется со свойством полной обратимости (как в случае комплексных чисел). Однако для функций равенство $f^{**} = f$ выполняется только тогда, когда исходная функция $f$ изначально была выпуклой. Если $f$ невыпукла, то её двойное сопряжение $f^{**}$ формирует так называемую выпуклую оболочку (convex envelope) — наибольшую выпуклую функцию, лежащую под графиком исходной, что геометрически эквивалентно выпуклой оболочке её надграфика (эпиграфа). ## 📊 Обобщения выпуклости: квазивыпуклые функции и финансовый IRR [[JUMP:56:59]] Математическое сообщество сформировало целую академическую индустрию вокруг обобщений выпуклости (включая псевдовыпуклость и квазивыпуклость), часто перегружая учебники громоздкими классификационными диаграммами. Стивен Бойд выделяет лишь два практически полезных обобщения: логарифмическую выпуклость и квазивыпуклость. Функция называется квазивыпуклой (или унимодальной), если все её множества подуровня являются выпуклыми множествами. График такой функции может содержать участки с отрицательной кривизной, но её множества подуровня всегда представляют собой выпуклые интервалы, точки или полубесконечные лучи. ### Парадокс целочисленных выпуклых функций В ходе интерактивной дискуссии со студентами о существовании целочисленных выпуклых функций лектор разбирает несколько типичных ошибочных предположений. Ступенчатые функции или функция количества ненулевых элементов вектора (кардинальность, обозначаемая в инвестициях как портфельный показатель «числа имен» активов) целочисленны, но не являются выпуклыми. Строгая математическая теория гласит, что на непрерывном интервале целочисленные выпуклые функции могут быть исключительно константами. Однако Стивен Бойд демонстрирует «противоестественный» пример: функция, принимающая дискретное значение 7 внутри открытого интервала $(-3, 2)$, значение 10 в изолированной точке $-3$ и 12 в точке $2$, формально является целочисленной и выпуклой, поскольку все её геометрические хорды лежат не ниже графика. Лектор с иронией добавляет, что в реальной жизни не стоит общаться с людьми, которые умышленно придумывают подобные примеры. ### Квазивогнутость внутренней нормы доходности (IRR) Практическим примером квазивогнутой функции выступает внутренняя норма доходности (Internal Rate of Return — IRR), повсеместно используемая в корпоративных финансах и венчурном бизнесе. Денежный поток описывается вектором $x = (x_0, x_1, \dots, x_n)$, где начальные инвестиции $x_0 < 0$, а совокупная сумма всех последующих выплат положительна. Чистая приведенная стоимость (NPV) рассчитывается путем дисконтирования потоков по временным периодам со ставкой $R$. Показатель IRR — это наименьшая процентная ставка, при которой NPV обращается в ноль. Расчет IRR требует решения уравнения многочлена степени $n$, для которого при $n \ge 5$ не существует аналитической формулы в радикалах. По словам Бойда, мало кто в сфере финансового учета или аудита догадывается о том, что IRR математически квазивогнута. Это доказывается через анализ множеств суперуровня (где IRR $\ge R$). Условие того, что IRR превышает заданную ставку, эквивалентно тому, что чистая приведенная стоимость проекта остается строго положительной для всех промежуточных ставок от $0$ до $R$. Для каждой фиксированной ставки неравенство NPV $> 0$ задает открытое полупространство в пространстве денежных потоков $x$, которое по определению является выпуклым множеством. Итоговое множество суперуровня представляет собой пересечение бесконечного семейства таких полупространств, что гарантирует его выпуклость. Для квазивыпуклых функций также формулируется модифицированное неравенство Йенсена: вместо классического ограничения сверху средней взвешенной функцией, значение функции от смеси аргументов ограничивается простым максимумом из значений функций в крайних точках. Завершая лекцию, Стивен Бойд обнадеживает студентов, уставших от долгого математического марафона: «Солнце взойдет примерно через 20 минут после начала следующей лекции во вторник».