# Стивен Бойд: Классы задач в выпуклой оптимизации Источник: https://www.youtube.com/watch?v=d2jF3SXcFQ8 Канал: Stanford Online Опубликовано: 16.03.2024 --- ## Обзор классов задач в выпуклой оптимизации 🚀 [[JUMP:0:05]] Лекция профессора Стивена Бойда посвящена завершению обзора различных классов задач оптимизации. Основное внимание уделяется квазивыпуклым задачам, линейному программированию, задачам с квадратичными и коническими ограничениями, а также методам их решения с помощью современных вычислительных инструментов. --- ## 📉 Квазивыпуклая оптимизация [[JUMP:0:18]] В отличие от выпуклых задач, где любой локальный минимум является глобальным, в квазивыпуклой оптимизации это правило не действует, что требует особой осторожности. * **Принцип решения:** Если функция квазивыпукла, её подмножества уровней выпуклы. Задача решается путём построения выпуклой функции, чьё нулевое подмножество уровней совпадает с ключевым подмножеством исходной функции. * **Метод бисекции:** Позволяет эффективно находить решение, многократно решая задачу выпуклой осуществимости. Каждая итерация бисекции сокращает область неопределенности относительно оптимального значения в два раза, предоставляя один «бит» информации на каждом шаге. * **Пример:** Отношение выпуклой функции к вогнутой (при положительном знаменателе) является квазивыпуклым, что позволяет проверять наличие решений с помощью линейного неравенства. --- ## 🏗 Линейное программирование (LP) [[JUMP:5:07]] Линейное программирование — это классический класс задач минимизации аффинной функции на многограннике. По словам С. Бойда, методы решения LP стали по-настоящему мощными с развитием компьютерных технологий. * **Исторический контекст:** Одной из первых прикладных задач LP стала «задача о диете» (diet problem), возникшая, по некоторым данным, в военном секторе для оптимизации рациона солдат при минимальных затратах. * **Матричная упаковка (matrix stuffing):** Профессор Бойд иронизирует над «ручным» приведением задач к стандартному виду, называя этот процесс «матричной упаковкой». Он подчеркивает, что в современной практике это делают программные библиотеки, поэтому вручную заниматься такими преобразованиями не нужно. * **Геометрическая интерпретация:** LP можно представить как поиск точки внутри многогранника, двигаясь по уровню градиента целевой функции. --- ## 📐 Квадратичное программирование (QP) [[JUMP:28:46]] Квадратичное программирование (QP) — это класс задач, где целевая функция является выпуклой квадратичной, а ограничения остаются линейными. * **Практическое применение:** С. Бойд отмечает, что QP настолько надежны, что их можно встраивать в системы управления реального времени, работающие с частотой 1000 раз в секунду без сбоев (например, при посадке первой ступени ракеты Falcon 9). * **Финансы:** По утверждению лектора, более половины всех количественных хедж-фондов используют QP для торговли, оперируя триллионами долларов. * **Изотоническая регрессия:** Минимизация методом наименьших квадратов при условии неубывания параметров — это классический пример QP, который часто выделяют в отдельную дисциплину, хотя, как считает Бойд, достаточно просто воспользоваться решателем для QP. --- ## 🔍 Обобщенное линейное дробное программирование [[JUMP:24:12]] Этот класс задач включает минимизацию максимума дробно-линейных функций. * **Модель экономики фон Неймана:** Стивен Бойд приводит эту модель как пример, где необходимо максимизировать минимальный рост в секторах экономики. * **Решение:** Такие задачи являются квазивыпуклыми и решаются методом бисекции. Важно, что при наличии 10 и более секторов решение такой задачи «вручную» невозможно, однако компьютерные системы позволяют моделировать экономики с 10 000 секторов. --- ## 🧬 Второе коническое программирование (SOCP) [[JUMP:40:06]] SOCP является относительно современным (последние 25 лет) и чрезвычайно выразительным классом задач. * **Низкоуровневый язык:** Бойд называет SOCP «3-байтовым кодом» выпуклой оптимизации, так как большинство прикладных задач (до 95%) могут быть сведены к этому формату. * **Робастная оптимизация:** При работе с неопределенностями (например, изменение качества ингредиентов в задаче о диете) используются эллипсоидальные границы. Робастный LP с такими границами сводится к решению SOCP. * **Статистические модели:** Вероятностные ограничения (шанс выполнения условий > 90–99%) также могут быть выражены через SOCP, если распределение известно. Бойд критически относится к попыткам требовать вероятность успеха выше 99,9%, считая это нереалистичным из-за отсутствия точных данных о хвостах распределений в реальных системах. --- ## 📐 Геометрическое программирование (GP) [[JUMP:53:26]] GP — это класс задач, которые на первый взгляд кажутся невыпуклыми, но после логарифмической трансформации переменных становятся выпуклыми. * **Терминология:** В GP используются понятия «моном» и «позином» (сумма мономов), которые Стивен Бойд просит не путать со стандартными математическими определениями, чтобы не прослыть невеждой в академической среде. * **Пример:** Проектирование консольной балки (минимум веса при ограничениях на стресс и отклонение) является примером задачи, которая после замены переменных $y = \log(x)$ превращается в выпуклую задачу, решаемую при огромных масштабах. --- ## 💠 Семидефинитное программирование (SDP) [[JUMP:111:04]] SDP — это расширение, использующее линейные матричные неравенства (LMI). * **Масштабируемость:** Хотя раньше SDP считалось чисто теоретическим инструментом, сейчас это мейнстрим, применяемый в физике, электротехнике и теоретической информатике. * **Schur Complement:** Профессор поясняет, что этот метод (дополнение Шура) позволяет сводить сложные матричные неравенства к более простым формам, что критически важно для эффективного решения SDP.