# Как Стивен Бойд находит скрытую выпуклость в сложных инженерных задачах

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

---

В лекции из курса Стэнфордского университета профессор Стивен Бойд представляет детальный обзор ключевых классов задач выпуклой оптимизации, ставших фундаментом для современных инженерных и экономических расчетов. Лектор разбирает эволюцию математических методов от классического линейного программирования до современных конических и полуопределенных ситемы, демонстрируя их применение на реальных примерах — от систем посадки ракет Falcon 9 до моделей роста экономики Фон Неймана. Главная идея занятия заключается в том, что многие кажущиеся невыпуклыми задачи могут быть элегантно преобразованы в выпуклые с помощью замены переменных.

## 🔄 Квазивыпуклая оптимизация: преодоление локальных минимумов
[[JUMP:0:18]]

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

Свойство квазивыпуклости функции означает, что все её множества подуровня являются выпуклыми. Чтобы решить такую задачу, Стивен Бойд предлагает ввести вспомогательную функцию $\phi_t(x)$, нулевое множество подуровня которой совпадает с ключевым множеством подуровня исходной функции. Эта функция обязательно должна быть выпуклой по $x$, и хотя существуют её общие универсальные конструкции, на практике структура $\phi_t(x)$ обычно подсказывается самой спецификой задачи.

Классическим примером квазивыпуклой, но не выпуклой функции является отношение неотрицательной выпуклой функции к положительной вогнутой функции: $f_0(x) = p(x)/q(x)$. Проверка условия $p(x)/q(x) \le t$ при положительном $t$ эквивалентна неравенству $p(x) - tq(x) \le 0$. Поскольку функция $q(x)$ вогнутая, её произведение на положительное число $t$ остаётся вогнутым, а со знаком минус становится выпуклым, что превращает всю левую часть выражения в выпуклую функцию.

Такой подход позволяет свести проверку существования решения, удовлетворяющего ограничению $f_0(x) \le t$, к выпуклой задаче допустимости (feasibility problem). На этой основе строится алгоритм бисекции (дихотомии).

Процесс выглядит следующим образом:

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

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

## 📊 Линейное программирование: от Фурье до управления цепочками поставок
[[JUMP:5:21]]

Линейное программирование (LP) — один из самых известных и распространенных классов задач оптимизации. Математически оно формулируется как минимизация аффинной функции при наличии набора аффинных ограничений в виде равенств и неравенств. Иными словами, задача сводится к минимизации линейной функции на многограннике.

Современная история линейного программирования берет начало в 1940-х годах, хотя основы метода заложил ещё Жан-Батист Жозеф Фурье в своей научной работе. Однако настоящий взрыв интереса к LP произошел с наступлением компьютерной эры, когда появилась возможность проводить реальные масштабные вычисления. Геометрически этот процесс можно представить как скольжение по многограннику ограничений вдоль линий уровня целевой функции, ортогональных вектору коэффициентов, в поисках экстремальной точки.

Сегодня линейное программирование применяется повсеместно для решения задач планирования и управления цепочками поставок. На практике инженеры регулярно решают задачи LP, содержащие порядка 10 000 переменных и 30 000 ограничений.

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

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

## 📐 Геометрические метаморфозы: кусочно-линейные функции и вписанные сферы
[[JUMP:13:52]]

### Кусочно-линейная минимизация

Кусочно-линейная функция выражается как максимум из семейства аффинных функций, график каждой из которых представляет собой плоскость. Сама по себе такая задача минимизации формально не является линейным программированием, поскольку целевая функция не аффинна. Однако она легко преобразуется в стандартное LP через эпиграфическую форму путем введения новой переменной $t$, выступающей в роли верхней границы для максимума этих функций. Полученная эквивалентная система является честной задачей линейного программирования с линейной целевой функцией и линейными ограничениями.

### Поиск Чебышевского центра

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

Для математического описания шар параметризуется его центром $x_c$ и радиусом $r$. Условие того, что шар лежит внутри полупространства, заданного неравенством $a_i^T x \le b_i$, раскрывается через неравенство Коши-Буняковского-Шварца. В итоге ограничение принимает вид:
$$a_i^T x_c + r \|a_i\|_2 \le b_i$$

Поскольку вектор $a_i$ является фиксированным исходным данным, определяющим грань многогранника, его 2-норма $\|a_i\|_2$ — это просто константа. Следовательно, данное ограничение линейно относительно искомых переменных $x_c$ и $r$. Стивен Бойд указывает, что Чебышевский центр многогранника не обязательно уникален. В качестве примера он приводит обычный вытянутый прямоугольник, внутри которого можно расположить несколько шаров максимального радиуса со смещенными центрами.

## 📈 Линейно-дробное программирование и экономический рост
[[JUMP:22:25]]

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

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

Ярким историческим примером применения этой математической модели служит модель расширяющейся экономики Джона фон Неймана. В ней векторы $x$ и $x^+$ представляют уровни экономической активности в $n$ секторах в текущем и следующем периодах соответственно. Отношение $x_i^+ / x_i$ отражает чистый рост конкретного сектора: например, значение 1.06 означает рост металлургического производства на 6%, а 0.93 — спад на 7%.

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

## 🚀 Квадратичное программирование: надежность на уровне систем управления
[[JUMP:28:46]]

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

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

В качестве примера профессор приводит систему посадки первых ступеней ракет-носителей Falcon 9 компании SpaceX, где параллельно выполняются несколько задач QP, одна из которых просчитывается с частотой 1000 раз в секунду. Кроме того, по оценке Бойда, более половины всех количественных хедж-фондов строят свои торговые стратегии исключительно на решении QP-задач, управляя таким образом триллионами долларов в реальном времени.

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

В качестве примера приводится изотоническая регрессия, используемая в статистике для моделирования износа систем. Если авиационный двигатель наработал 10 000 часов, его зазоры и повреждения могут только увеличиваться, то есть параметры износа математически обязаны быть монотонно негибыми. Моделирование этого процесса через QP реализуется буквально в одну-две строки кода.

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

Учет неопределенности через минимизацию среднего значения стоимости с поправкой на её дисперсию порождает задачу оптимизации скорректированной на риск стоимости, которая представляет собой классическое выпуклое квадратичное программирование. Лектор добавляет, что если параметр неприятия риска $\gamma$ становится отрицательным (склонность к риску), задача теряет выпуклость, становится крайне сложной и, по его мнению, бессмысленной для практического проектирования.

## 📐 Коническое программирование второго порядка: «байт-код» выпуклой оптимизации
[[JUMP:39:54]]

Коническое программирование второго порядка (SOCP) представляет собой относительно новое направление, сформировавшееся за последние 25 лет. В этой задаче минимизируется линейная целевая функция, а ограничения включают в себя требования нахождения образа аффинного отображения внутри конуса второго порядка. Математически это выражается через 2-норму (не возведенную в квадрат):
$$\|A_i x + b_i\|_2 \le c_i^T x + d_i$$

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

По мнению Стивена Бойда, SOCP можно метафорически назвать «низкоуровневым трехбайтовым кодом» выпуклой оптимизации. Высокоуровневые спецификации задач в библиотеках вроде CVXPY автоматически компилируются в форму SOCP перед отправкой в солверы. Этот класс задач поглощает в себя линейное (LP) и квадратичное программирование (QCQP), покрывая около 95% всех возможных оптимизационных задач из сотни различных прикладных областей.

В качестве примера применения SOCP рассматривается робастное линейное программирование с эллипсоидальной неопределенностью в ограничениях. Если параметры питательных веществ в задаче о диете колеблются от партии к партии, исследователь может описать область неопределенности в виде эллипсоида. Переход к гарантированному выполнению условий при любых колебаниях внутри этого эллипсоида математически трансформирует задачу в форму SOCP. Полученное уравнение наглядно демонстрирует, какой запас (margin) прочности необходимо заложить в систему, причем этот запас динамически зависит от выбора вектора переменных $x$.

Аналогичным образом к SOCP сводятся стохастические модели с вероятностными ограничениями (chance constraints), где требуется, чтобы ограничение выполнялось с заданной вероятностью $\eta$ (например, 95% или 99%) для гауссовских случайных векторов. Через функцию распределения Гаусса ограничения преобразуются в коническую структуру. Лектор делает важное математическое предостережение: этот переход к SOCP корректен только в том случае, если требуемая вероятность превышает 50% ($\eta > 0.5$), иначе знак неравенства инвертируется, разрушая выпуклость.

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

## 📐 Геометрическое программирование: логарифмическая трансформация невыпуклых задач
[[JUMP:53:13]]

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

История GP полна иронии: в западной науке 1960-х годов активно писались книги по геометрическому программированию, но исследователи решали эти задачи вручную и не осознавали их скрытую выпуклость вплоть до 1980-х годов. В то же время, как рассказывает Бойд со слов своих друзей, советские математики в Москве еще в 1960-х годах прекрасно знали о выпуклой природе этого класса задач и недоумевали, почему на Западе этого не замечают.

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

Суть логарифмического перехода заключается в переходе к переменным $y_i = \log x_i$. При такой операции логарифм монома превращается в линейную (аффинную) функцию, а позиномы трансформируются в выпуклую функцию вида log-sum-exp от аффинных выражений. В результате невыпуклая система становится строго выпуклой.

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

В качестве примера Бойд приводит классическую задачу проектирования консольной балки из учебников по инженерному дизайну. Цель — минимизировать общий вес балки при ограничениях на геометрию, максимальное внутреннее напряжение в сегментах и величину прогиба наконечника под воздействием силы. Функция веса представляет собой скалярное произведение ширины и высоты сегментов балки, что порождает невыпуклую квадратичную форму. Однако применение правил GP позволяет переписать все physical уравнения прогиба и веса в виде позиномов и решить задачу за доли секунды.

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

## 📐 Полуопределенное программирование: матрицы и конусы высших порядков
[[JUMP:1:11:04]]

Завершающим этапом обзора становятся задачи в конической форме, где вместо скалярных неравенств используются векторные ограничения по конусу $K$. Если конус представляет собой положительный квадрант, система вырождается в обычное линейное программирование. Если же ограничения накладываются на симметричные матрицы, задача переходит в класс полуопределенного программирования (SDP). Ограничение в SDP формулируется в виде линейного матричного неравенства (LMI — Linear Matrix Inequality), требующего, чтобы аффинная комбинация симметричных матриц была отрицательно полуопределенной.

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

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

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