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

Ідея первинно-подвійного методу легко продемонструвати для обмеженої нелінійної оптимізації. Для простоти розглянемо варіант нерівності нелінійної задачі оптимізації:
мінімізувати функцію ${\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 }).}}$

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