Skip to content
Назад к результатам поиска

Выпуклая оптимизация

Автор метода
Stephen Boyd & Lieven Vandenberghe
Год
2004
Тип
Mathematical optimization framework
Семейство
Mathematical programming

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

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

Интуиция метода

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

История

Теоретические основы выпуклого анализа восходят к работам Минковского и Фаркаса начала двадцатого века, а линейное программирование появилось в 1940-х годах благодаря Данцигу. Методы внутренней точки, представленные Кармаркаром в 1984 году и усовершенствованные в 1990-х годах, сделали общие выпуклые программы вычислительно решаемыми. Учебник Бойда и Ванденберге 2004 года, изданный Cambridge University Press и свободно доступный онлайн, синтезировал десятилетия результатов в единую, доступную структуру и породил парадигму дисциплинированного выпуклого программирования, реализованную в CVX, CVXPY и связанных инструментах.

Когда применять

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

Ограничения и замечания

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

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

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

Применение

  • Оптимизация портфеля: минимизация дисперсии или CVaR при заданных целевых показателях доходности и ограничениях на распределение активов в количественных финансах.
  • Машинное обучение: обучение машин опорных векторов, регрессии Лассо и Риджа, а также логистическая регрессия являются каноническими выпуклыми программами.
  • Обработка сигналов и изображений: сжатое зондирование, шумоподавление методом полного изменения и восстановление разреженных сигналов формулируются как выпуклые программы.
  • Сетевое распределение ресурсов: оптимальная маршрутизация, управление мощностью в беспроводных сетях и распределение полосы пропускания при ограничениях пропускной способности.
  • Системы управления: синтез H-бесконечных регуляторов на основе полудефинитного программирования и проверка устойчивости по Ляпунову.

Как это работает

Как это работает

1

Аналитик формулирует задачу принятия решений как выпуклую программу стандартной формы: минимизировать выпуклую целевую функцию f0(x) при ограничениях-неравенствах fi(x) ≤ 0 и ограничениях-равенствах Ax = b, где все функции fi выпуклы, а ограничения являются аффинными. Правильная формулировка — выбор правильного представления переменных и выражение всех ограничений в выпуклой форме — является критически важным первым шагом, определяющим, применимы ли мощные гарантии.

Формула
\min_{x \in \mathcal{C}} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0,\; i=1,\ldots,m,\; Ax = b
2

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

Формула
f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y), \quad \forall x,y \in \text{dom}\,f,\; \theta \in [0,1]
3

Лагранжиан L(x, λ, ν) формируется путём релаксации ограничений с помощью двойственных множителей. При квалификации ограничений Слейтера выполняется сильная двойственность: примарные и дуальные оптимумы совпадают, а условия ККТ — стационарность, примарная/дуальная допустимость и дополнительная нежёсткость — являются необходимыми и достаточными условиями глобальной оптимальности. Двойственность также даёт сертификаты оптимальности и информацию о чувствительности относительно того, как оптимум изменяется в зависимости от данных задачи.

Формула
L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^T(Ax-b), \quad \lambda_i \geq 0
4

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

Формула
x^{(k+1)} = x^{(k)} - t_k \nabla f_0(x^{(k)}), \quad t_k > 0

Частые ошибки

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

Часто задаваемые вопросы

Как узнать, является ли моя задача выпуклой?

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

В чём разница между выпуклой оптимизацией и линейным программированием?

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

Может ли выпуклая оптимизация обрабатывать целочисленные или бинарные переменные?

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

Похожие методы

Источники

  1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

    ISBN: 978-0-521-83378-3
    Скопировано.