Выпуклое программирование

---

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

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

Задача выпуклого программирования — это задача оптимизации, в которой целевая функция является выпуклой функцией и область допустимых решений выпукла. Функция ${\displaystyle f}$, отображающая некоторое подмножество ${\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)\leqslant \theta f(x)+(1-\theta )f(y)}$. Множество выпукло, если для всех его элементов ${\displaystyle x,y}$ и любого ${\displaystyle \theta \in [0,1]}$ также и ${\displaystyle \theta x+(1-\theta )y}$ принадлежит множеству.

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

---