Метод внутрішньої точки

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

Джон фон Нейман запропонував внутрішній точковий метод лінійного програмування, який не був ні методом поліноміального часу, ні ефективним методом на практиці. Насправді він виявився повільнішим, ніж широко використовуваний симплекс-метод. У 1984 р. Нарендра Кармаркар розробив метод лінійного програмування, який називається алгоритмом Кармаркара, який працює за поліноміальний час і також є дуже ефективним на практиці. Це дало змогу вирішити задачі лінійного програмування, що вийшли за межі можливостей симплексного методу. На відміну від симплексного методу, він досягає найкращого рішення шляхом обходу внутрішніх областей допустимих рішень. Метод може бути узагальнений до випуклого програмування на основі самокоректної бар'єрної функції, що використовується для кодування опуклого набору.

Будь-яка проблема оптимізації опуклості може бути перетворена на мінімізацію (або максимізацію) лінійної функції над опуклою множиною шляхом перетворення її у форму епіграфа. Ідея кодування множини допустимих ріщень за допомогою бар'єру та проектування бар'єрних методів була вивчена Антонієм В. Юрієм Нестеровим та Аркадієм Немировським, вони придумали особливий клас таких бар'єрів, який можна використовувати для кодування будь-якої опуклої множини. Вони гарантують, що кількість ітерацій алгоритму обмежена поліномом у розмірності та точності рішення.

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

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

Первинний-подвійний метод внутрішньої точки для нелінійної оптимізації

Ідея первинно-подвійного методу легко продемонструвати для обмеженої нелінійної оптимізації. Для простоти розглянемо варіант нерівності нелінійної задачі оптимізації:
мінімізувати функцію ${\displaystyle {\displaystyle f(x)}}$ за умови ${\displaystyle {\displaystyle c_{i}(x)\geq 0~{\text{for}}~i=1,\ldots ,m,~x\in \mathbb {R} ^{n},}}$ де

${\displaystyle {\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ,c_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} \quad (1).}}$

Логарифмічна бар'єрна функція, пов'язана з (1),

${\displaystyle {\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}}$

Тут ${\displaystyle \mu }$ — невеликий позитивний скаляр, який іноді називають «параметром бар'єру». Оскільки ${\displaystyle \mu }$ збігається до нуля, то мінімум ${\displaystyle {\displaystyle B(x,\mu )}}$ повинен переходити до рішення (1).

Градієнт бар'єрної функції дорівнює

${\displaystyle {\displaystyle g_{b}=g-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x),\quad (3)}}$

де ${\displaystyle g}$ — градієнт вихідної функції ${\displaystyle f(x)}$, а ${\displaystyle \nabla c_{i}}$ — градієнт ${\displaystyle c_{i}}$.

На додаток до оригінальної («первинної») змінної ${\displaystyle x}$ ми вводимо подвійну змінну, натхненну множником Лагранжа

${\displaystyle {\displaystyle \lambda \in \mathbb {R} ^{m}}}$

${\displaystyle {\displaystyle c_{i}(x)\lambda _{i}=\mu ,\forall i=1,\ldots ,m.\quad (4)}}$

(4) іноді називають умовою «збуреної взаємодоповнюваності» за її схожість з «комплементарною слабкістю» в умовах KKT.

Ми намагаємося знайти ті ${\displaystyle {\displaystyle (x_{\mu },\lambda _{\mu })}}$, для яких градієнт бар'єрної функції дорівнює нулю.

Застосовуючи (4) до (3), отримуємо рівняння для градієнта:

${\displaystyle {\displaystyle g-A^{T}\lambda =0,\quad (5)}}$

де матриця ${\displaystyle A}$ — якобіан обмежень ${\displaystyle c(x)}$.

Інтуїція позаду (5) полягає в тому, що градієнт ${\displaystyle f(x)}$ повинен лежати в підпросторі, що охоплюється градієнтами обмежень. «Збурену взаємодоповнюваність» з малим ${\displaystyle \mu }$ (4) можна розуміти як умову, що рішення повинно лежати біля межі ${\displaystyle {\displaystyle c_{i}(x)=0}}$, або що проєкція градієнта ${\displaystyle g}$ на компонент обмеження ${\displaystyle {\displaystyle c_{i}(x)}}$ нормально повинна бути майже нульовою.

Застосовуючи метод Ньютона до (4) і (5), ми отримуємо рівняння ${\displaystyle (x,\lambda )}$ для оновлення ${\displaystyle {\displaystyle (p_{x},p_{\lambda })}}$:

${\displaystyle {\displaystyle {\begin{pmatrix}W&-A^{T}\\\Lambda A&C\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-g+A^{T}\lambda \\\mu 1-C\lambda \end{pmatrix}},}}$

Де ${\displaystyle W}$ матриця Гессея ${\displaystyle {\displaystyle B(x,\mu )}}$, ${\displaystyle {\displaystyle \Lambda }}$ є діагональною матрицею ${\displaystyle {\displaystyle \lambda }}$ і ${\displaystyle C}$ is a diagonal matrix with ${\displaystyle {\displaystyle C_{ii}=c_{i}(x)}.}$

Через (1), (4) умова

${\displaystyle \lambda \geq 0}$

повинна застосовуватися на кожному кроці. Це можна зробити, вибравши відповідне ${\displaystyle \alpha :}$

${\displaystyle {\displaystyle (x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}}$

Див. також

• Умови Каруша — Куна — Такера

Посилання

1. Dantzig, George (1963). Linear Programming and Extensions. doi:10.7249/r366. Процитовано 24 грудня 2019.
2. Boyd, Stephen; Vandenberghe, Lieven (8 березня 2004). Convex Optimization. Cambridge University Press. ISBN .
3. Wright, Margaret H. (21 вересня 2004). The interior-point revolution in optimization: History, recent developments, and lasting consequences. Bulletin of the American Mathematical Society. Т. 42, № 01. с. 39—57. doi:10.1090/s0273-0979-04-01040-7. ISSN 0273-0979. Процитовано 24 грудня 2019.
4. Potra, Florian A.; Wright, Stephen J. (2000-12). Interior-point methods. Journal of Computational and Applied Mathematics. Т. 124, № 1-2. с. 281—302. doi:10.1016/s0377-0427(00)00433-7. ISSN 0377-0427. Процитовано 24 грудня 2019.