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

---

Выпуклая оптимизация — это раздел математической оптимизации , изучающий проблему минимизации выпуклых функций над выпуклыми множествами (или, что то же самое, максимизации вогнутых функций над выпуклыми множествами). Многие классы задач выпуклой оптимизации допускают алгоритмы с полиномиальным временем ^[1] , тогда как математическая оптимизация, как правило, NP-трудна . ^{[2] [3] [4]}

Выпуклая оптимизация имеет приложения в широком спектре дисциплин, таких как системы автоматического управления , оценка и обработка сигналов , связь и сети, проектирование электронных схем , ^[5] анализ и моделирование данных, финансы , статистика ( оптимальный план эксперимента ), ^[6] и структурная оптимизация , где концепция аппроксимации доказала свою эффективность. ^{[7] [8]}Благодаря последним достижениям в области вычислений и алгоритмов оптимизации , выпуклое программирование почти так же просто, как линейное программирование . ^[9]

Задача выпуклой оптимизации — это задача оптимизации , в которой целевая функция является выпуклой функцией , а допустимое множество — выпуклым множеством . Функция , отображающая некоторое подмножество в, является выпуклой, если ее область определения выпукла и для всех и вся в ее области выполнения выполняется следующее условие: . Множество S является выпуклым, если для всех членов и всех это справедливо .${\displaystyle е}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$${\displaystyle \theta \in [0,1]}$${\displaystyle x,y}$${\displaystyle f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y)}$${\displaystyle x,y\in S}$${\displaystyle \theta \in [0,1]}$${\displaystyle \theta x+(1-\theta)y\in S}$

Конкретно, задача выпуклой оптимизации — это проблема нахождения некоторого достижения${\displaystyle \mathbf {x^{\ast }} \in C}$

где целевая функция выпукла, как и допустимое множество . ^{[10] [11]} Если такая точка существует, ее называют оптимальной точкой или решением ; совокупность всех оптимальных точек называется оптимальным множеством . Если неограничено снизу или нижняя грань не достигается, то задача оптимизации называется неограниченной . В противном случае, если множество пусто, то задача называется неразрешимой . ^[12]${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle C}$${\displaystyle е}$${\displaystyle C}$${\displaystyle C}$

---