Опукла оптимізація

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

Опукла оптимізація

Опукла оптимізація у Вікісховищі

Опукла оптимізація має застосування в широкому спектрі дисциплін, таких як автоматичні системи управління, оцінка та обробка сигналів, комунікації та мережі, проєктування електронних схем^[5], аналіз та моделювання даних, фінанси, статистика (оптимальний експериментальний дизайн),^[6] та структурна оптимізація, де концепція наближення виявилась ефективною.^[5][7] З недавніми досягненнями в галузі обчислювальних та оптимізаційних алгоритмів, опукле програмування майже настільки ж просте, як і лінійне програмування^[5].

Визначення

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

Конкретно, проблема опуклої оптимізації — це проблема пошуку ${\displaystyle \mathbf {x^{\ast }} \in C}$ маючи

${\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}$,

де об'єктивна функція ${\displaystyle f}$ є опуклою, як і допустима множина ${\displaystyle C}$^[8][9]. Якщо така точка існує, вона називається оптимальною точкою ; множина всіх оптимальних точок називається оптимальною множиною. Якщо ${\displaystyle f}$ є необмеженою внизу над ${\displaystyle C}$ або мінімум не досягнуто, тоді, як кажуть, проблема оптимізації є необмеженою. Інакше, якщо ${\displaystyle C}$ є порожньою множиною, тоді проблема, як кажуть, невирішувана^[5].

Стандартна форма

Кажуть, що проблема опуклої оптимізації є в стандартній формі, якщо вона записана як

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}$

де ${\displaystyle x\in \mathbb {R} ^{n}}$ — змінна оптимізації, функції ${\displaystyle f,g_{1},\ldots ,g_{m}}$ є опуклими, і функції ${\displaystyle h_{1},\ldots ,h_{p}}$ є афінними^[5]. У цьому позначенні функція ${\displaystyle f}$ — це цільова функція задачі, і функції ${\displaystyle g_{i}}$ і ${\displaystyle h_{i}}$ називаються функціями обмеження. Можливим набором задачі оптимізації є множина, що складається з усіх точок ${\displaystyle x\in \mathbb {R} ^{n}}$ задовольняючи ${\displaystyle g_{1}(x)\leq 0,\ldots ,g_{m}(x)\leq 0}$ і ${\displaystyle h_{1}(x)=0,\ldots ,h_{p}(x)=0}$. Ця множина є опуклою, оскільки підмножини опуклих функцій опуклі, афінні множини опуклі, а перетин опуклих множин — опуклий^[5].

Багато проблем оптимізації можуть бути сформульовані в цій стандартній формі. Наприклад, проблема максимізації увігнутої функції ${\displaystyle f}$ може бути переформульовано як проблема мінімізації опуклої функції ${\displaystyle -f}$ ; така проблема максимізації увігнутої функції над опуклою множиною часто називається проблемою оптимізації опуклої форми.

Властивості

Наступні корисні властивості задач опуклої оптимізації:^[5][10]

• кожен локальний мінімум — це глобальний мінімум;
• оптимальна множина опукла;
• якщо цільова функція строго опукла, то задача має щонайменше одну оптимальну точку.

Ці результати використовуються теорією опуклої мінімізації разом з геометричними поняттями функціонального аналізу (в просторах Гільберта), такими як теорема проєкції Гільберта, теорема розділення гіперплан та лема Фаркаса.

Приклади

Перелічені класи задач — це все задачі опуклої оптимізації, або їх можна звести до задачі опуклої оптимізації за допомогою простих перетворень:^[5][11]

Ієрархія задач опуклої оптимізації. (LP: лінійна програма, QP: квадратична програма, програма конусів SOCP другого порядку, SDP: напіввизначена програма, CP: програма конуса.)

• Найменші квадрати
• Лінійне програмування
• Опукла квадратична мінімізація з лінійними обмеженнями
• Квадратна мінімізація з опуклими квадратичними обмеженнями
• Конічна оптимізація
• Геометричне програмування
• Програмування конуса другого порядку
• Напівскінченне програмування
• Максимізація ентропії з відповідними обмеженнями

Множники Лагранжа

Розглянемо проблему мінімізації опуклої форми, задану в стандартній формі функцією витрат ${\displaystyle f(x)}$ та обмеженням нерівності ${\displaystyle g_{i}(x)\leq 0}$ для ${\displaystyle 1\leq i\leq m}$. Домен ${\displaystyle {\mathcal {X}}}$ є:

${\displaystyle {\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.}$

Функцією Лагранжа для задачі є

${\displaystyle L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).}$

Для кожної точки ${\displaystyle x}$ в ${\displaystyle X}$ що мінімізує ${\displaystyle f}$ над ${\displaystyle X}$, існують реальні числа ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},}$ котрі називаються множниками Лагранжа, які одночасно задовольняють ці умови:

1. ${\displaystyle x}$ мінімізує ${\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})}$ над усім ${\displaystyle y\in X,}$
2. ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,}$ принаймні з одним ${\displaystyle \lambda _{k}>0,}$
3. ${\displaystyle \lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0}$ (додаткова млявість).

Якщо існує «строго допустима точка», тобто точка ${\displaystyle z}$, котра задовольняє

${\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,}$

тоді твердження вище може вимагати ${\displaystyle \lambda _{0}=1}$.

І навпаки, якщо якісь ${\displaystyle x}$ в ${\displaystyle X}$ задовольняють (1) — (3) для скалярів ${\displaystyle \lambda _{0},\ldots ,\lambda _{m}}$ з ${\displaystyle \lambda _{0}=1}$, то ${\displaystyle x}$ мінімізує ${\displaystyle f}$ над ${\displaystyle X}$.

Алгоритми

Задачі опуклої оптимізації можуть бути розв'язані такими сучасними методами:^[12]

• Методи розшарування (Вулф, Лемарель, Ківіль) та
• Методи субградієнтної проєкції (Поляк),
• Методи внутрішніх точок^[1], в яких використовуються самокорегуючі бар'єрні функції^[13] та саморегулярні бар'єрні функції.^[14]
• Ріжучі площинні методи
• Еліпсоїдний метод
• Субградієнтний метод
• Подвійні субградієнти та метод дрейфу плюс-штраф

Субградієнтні методи можуть бути реалізовані просто і тому широко застосовуються.^[15] Подвійні субградієнтні методи — це субградієнтні методи, застосовані до подвійної задачі. Метод дрейфування плюс-штрафу схожий з методом подвійного субградієнта.

Розширення

Розширення опуклої оптимізації включають оптимізацію функцій двоопуклої, псевдоопуклої та квазіопуклої. Розширення теорії опуклого аналізу та ітеративних методів приблизно розв'язування задач мінімізації, що не є опуклими, відбуваються в області узагальненої опуклості, також відомої як абстрактний опуклий аналіз.

Див. також

• Двоїстість (оптимізація)
• Умови Каруша — Куна — Такера
• Задача оптимізації
• Метод проксимального градієнта
• Алгоритм Франк — Вульфа