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