Метод предиктора-корректора Мехротры

Метод предиктора-корректора Мехротры в оптимизации представляет собой особый метод внутренней точки линейного программирования . Он был предложен в 1989 году Санджаем Мехротрой. ^{[ 1 ]}

Метод основан на том, что на каждой итерации алгоритма внутренней точки необходимо вычислить разложение (факторизацию) Холецкого большой матрицы для нахождения направления поиска. Шаг факторизации является самым затратным в вычислительном отношении шагом в алгоритме. Следовательно, имеет смысл использовать одно и то же разложение несколько раз, прежде чем пересчитывать его.

На каждой итерации алгоритма метод предиктора-корректора Мехротры использует одно и то же разложение Холецкого для поиска двух разных направлений: предиктора и корректора.

Идея состоит в том, чтобы сначала вычислить оптимизирующее направление поиска на основе термина первого порядка (предиктора). Размер шага, который можно сделать в этом направлении, используется для оценки того, насколько необходима коррекция центральности. Затем вычисляется корректирующий член: он содержит как член центральности, так и член второго порядка.

Полное направление поиска представляет собой сумму направления предиктора и направления корректора.

Хотя теоретическая сложность пока не связана с этим, метод предиктора-корректора Мехротры широко используется на практике. ^{[ 2 ]} На этапе корректора используется то же разложение Холецкого эффективно , что и на этапе прогнозирования, и поэтому он лишь незначительно дороже, чем стандартный алгоритм внутренней точки. Однако дополнительные затраты на итерацию обычно окупаются за счет сокращения количества итераций, необходимых для достижения оптимального решения. Кроме того, оказывается, что он сходится очень быстро, когда он близок к оптимальному.

Вывод

Вывод этого раздела следует схеме Носедаля и Райта. ^{[ 3 ]}

Шаг предиктора — направление аффинного масштабирования

Линейную программу всегда можно сформулировать в стандартной форме.

${\begin{aligned}&{\underset {x}{\min }}&q(x)&=c^{T}x,\\&{\text{s.t.}}&Ax&=b,\\&\;&x&\geq 0,\end{aligned}}$

где $c\in \mathbb {R} ^{n\times 1},\;A\in \mathbb {R} ^{m\times n}$ и $b\in \mathbb {R} ^{m\times 1}$ определить проблему с $m$ ограничения и $n$ уравнения в то время как $x\in \mathbb {R} ^{n\times 1}$ представляет собой вектор переменных.

Условия Каруша -Куна-Такера (ККТ) для задачи таковы:

${\begin{aligned}A^{T}\lambda +s&=c,\;\;\;{\text{(Lagrange gradient condition)}}\\Ax&=b,\;\;\;{\text{(Feasibility condition)}}\\XSe&=0,\;\;\;{\text{(Complementarity condition)}}\\(x,s)&\geq 0,\end{aligned}}$

где $X={\text{diag}}(x)$ и $S={\text{diag}}(s)$ откуда $e=(1,1,\dots ,1)^{T}\in \mathbb {R} ^{n\times 1}$ .

Эти условия можно переформулировать как отображение $F:\mathbb {R} ^{2n+m}\rightarrow \mathbb {R} ^{2n+m}$ следующее

${\begin{aligned}F(x,\lambda ,s)={\begin{bmatrix}A^{T}\lambda +s-c\\Ax-b\\XSe\end{bmatrix}}&=0\\(x,s)&\geq 0\end{aligned}}$

Затем метод предиктора-корректора работает с использованием метода Ньютона для получения направления аффинного масштабирования. Это достигается путем решения следующей системы линейных уравнений

$J(x,\lambda ,s){\begin{bmatrix}\Delta x^{\text{aff}}\\\Delta \lambda ^{\text{aff}}\\\Delta s^{\text{aff}}\end{bmatrix}}=-F(x,\lambda ,s)$

где $J$ , определяемый как

$J(x,\lambda ,s)={\begin{bmatrix}\nabla _{x}F&\nabla _{\lambda }F&\nabla _{s}F\end{bmatrix}},$

является якобианом F.

Таким образом, система становится

${\begin{bmatrix}0&A^{T}&I\\A&0&0\\S&0&X\end{bmatrix}}{\begin{bmatrix}\Delta x^{\text{aff}}\\\Delta \lambda ^{\text{aff}}\\\Delta s^{\text{aff}}\end{bmatrix}}={\begin{bmatrix}-r_{c}\\-r_{b}\\-XSe\end{bmatrix}},\;\;\;r_{c}=A^{T}\lambda +s-c,\;\;\;r_{b}=Ax-b$

Шаг центрирования

Средняя стоимость продукции $x_{i}s_{i},\;i=1,2,\dots ,n$ представляют собой важную меру желательности определенного набора $(x^{k},s^{k})$ (верхние индексы обозначают значение номера итерации, $k$ , метода). Это называется мерой двойственности и определяется формулой

$\mu ={\frac {1}{n}}\sum _{i=1}^{n}x_{i}s_{i}={\frac {x^{T}s}{n}}.$

Для значения параметра центрирования $\sigma \in [0,1],$ шаг центрирования можно вычислить как решение

${\begin{bmatrix}0&A^{T}&I\\A&0&0\\S&0&X\end{bmatrix}}{\begin{bmatrix}\Delta x^{\text{cen}}\\\Delta \lambda ^{\text{cen}}\\\Delta s^{\text{cen}}\end{bmatrix}}={\begin{bmatrix}-r_{c}\\-r_{b}\\-XSe+\sigma \mu e\end{bmatrix}}$

Шаг корректора

Рассматривая систему, используемую для вычисления направления аффинного масштабирования, определенного выше, можно отметить, что выполнение полного шага в направлении аффинного масштабирования приводит к тому, что условие дополнительности не удовлетворяется:

$\left(x_{i}+\Delta x_{i}^{\text{aff}}\right)\left(s_{i}+\Delta s_{i}^{\text{aff}}\right)=x_{i}s_{i}+x_{i}\Delta s_{i}^{\text{aff}}+s_{i}\Delta x_{i}^{\text{aff}}+\Delta x_{i}^{\text{aff}}\Delta s_{i}^{\text{aff}}=\Delta x_{i}^{\text{aff}}\Delta s_{i}^{\text{aff}}\neq 0.$

Таким образом, можно определить систему для вычисления шага, который пытается исправить эту ошибку. Эта система опирается на предыдущие вычисления направления аффинного масштабирования.

${\begin{bmatrix}0&A^{T}&I\\A&0&0\\S&0&X\end{bmatrix}}{\begin{bmatrix}\Delta x^{\text{cor}}\\\Delta \lambda ^{\text{cor}}\\\Delta s^{\text{cor}}\end{bmatrix}}={\begin{bmatrix}0\\0\\-\Delta X^{\text{aff}}\Delta S^{\text{aff}}e\end{bmatrix}}$

Агрегированная система - Центр-корректор направления

Вклады предиктора, корректора и центрирования в правую часть системы могут быть объединены в одну систему. Эта система будет зависеть от предыдущего вычисления направления аффинного масштабирования, однако матрица системы будет идентична матрице шага предиктора, так что ее факторизацию можно будет использовать повторно.

Агрегированная система представляет собой

${\begin{bmatrix}0&A^{T}&I\\A&0&0\\S&0&X\end{bmatrix}}{\begin{bmatrix}\Delta x\\\Delta \lambda \\\Delta s\end{bmatrix}}={\begin{bmatrix}-r_{c}\\-r_{b}\\-XSe-\Delta X^{\text{aff}}\Delta S^{\text{aff}}e+\sigma \mu e\end{bmatrix}}$

Затем алгоритм предиктора-корректора сначала вычисляет направление аффинного масштабирования. Во-вторых, он решает агрегированную систему, чтобы получить направление поиска текущей итерации.

Адаптивный выбор параметра центрирования

Направление аффинного масштабирования можно использовать для определения эвристики для адаптивного выбора параметра центрирования как

$\sigma =\left({\frac {\mu _{\text{aff}}}{\mu }}\right)^{3},$

где

${\begin{aligned}\mu _{\text{aff}}&=(x+\alpha _{\text{aff}}^{\text{pri}}\Delta x^{\text{aff}})^{T}(s+\alpha _{\text{aff}}^{\text{dual}}\Delta s^{\text{aff}})/n,\\\alpha _{\text{aff}}^{\text{pri}}&=\min \left(1,{\underset {i:\Delta x_{i}^{\text{aff}}<0}{\min }}-{\frac {x_{i}}{\Delta x_{i}^{\text{aff}}}}\right),\\\alpha _{\text{aff}}^{\text{dual}}&=\min \left(1,{\underset {i:\Delta s_{i}^{\text{aff}}<0}{\min }}-{\frac {s_{i}}{\Delta s_{i}^{\text{aff}}}}\right),\end{aligned}}$

Здесь, $\mu _{\text{aff}}$ – мера двойственности аффинной ступени и $\mu$ — мера двойственности предыдущей итерации. ^{[ 3 ]}

Длина шага

В практических реализациях вариант поиска строки выполняется для получения максимальной длины шага, который можно сделать в направлении поиска без нарушения неотрицательности: $(x,s)\geq 0$ . ^{[ 3 ]}

Адаптация к квадратичному программированию

Хотя модификации, представленные Мехротрой, предназначались для алгоритмов внутренних точек линейного программирования, идеи были расширены и успешно применены к квадратичному программированию . также и ^{[ 3 ]}

Ссылки

^ Мехротра, С. (1992). «О реализации метода прямой и двойственной внутренней точки». SIAM Journal по оптимизации . 2 (4): 575–601. дои : 10.1137/0802028 .
^ «В 1989 году Мехротра описал практический алгоритм линейного программирования, который остается основой большинства современных программ; его работа появилась в 1992 году». Потра, Флориан А.; Стивен Дж. Райт (2000). «Методы внутренних точек». Журнал вычислительной и прикладной математики . 124 (1–2): 281–302. дои : 10.1016/S0377-0427(00)00433-7 .
^ Перейти обратно: ^а ^б ^с ^д Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация . Соединенные Штаты Америки: Спрингер. стр. 392–417, 448–496. ISBN 978-0387-30303-1 .

[1] Мехротра, С. (1992). «О реализации метода прямой и двойственной внутренней точки». SIAM Journal по оптимизации . 2 (4): 575–601. дои : 10.1137/0802028 .

[2] «В 1989 году Мехротра описал практический алгоритм линейного программирования, который остается основой большинства современных программ; его работа появилась в 1992 году». Потра, Флориан А.; Стивен Дж. Райт (2000). «Методы внутренних точек». Журнал вычислительной и прикладной математики . 124 (1–2): 281–302. дои : 10.1016/S0377-0427(00)00433-7 .

[:0-3] Перейти обратно: ^а ^б ^с ^д Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация . Соединенные Штаты Америки: Спрингер. стр. 392–417, 448–496. ISBN 978-0387-30303-1 .

[ 1 ]

[ 2 ]

[ 3 ]