Метод предиктора-корректора Mehrotra - Mehrotra predictor–corrector method

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

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

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

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

Полное направление поиска - это сумма направления предсказателя и направления корректора.

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

Вывод

Вывод этого раздела следует плану Нокедала и Райта.^[3]

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

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

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

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

В Условия Каруша-Куна-Такера (ККТ) для проблемы

${\displaystyle {\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}}}$

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

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

${\displaystyle {\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}}}$

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

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

где ${\displaystyle J}$, определяется как

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

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

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

${\displaystyle {\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}$

Центрирующий шаг

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

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

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

${\displaystyle {\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}}}$

Корректор шаг

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

${\displaystyle \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.}$

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

${\displaystyle {\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}}}$

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

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

Агрегированная система

${\displaystyle {\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}}}$

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

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

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

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

где

${\displaystyle {\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}})^{T}/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}}}$

Вот, ${\displaystyle \mu _{\text{aff}}}$ - мера двойственности аффинного шага и ${\displaystyle \mu }$ - мера двойственности предыдущей итерации.^[3]

Длина шага

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

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

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

использованная литература

1. Мехротра, С. (1992). «О реализации метода прямой – двойственной внутренней точки». SIAM Journal по оптимизации. 2 (4): 575–601. Дои:10.1137/0802028.
2. «В 1989 году Мехротра описал практический алгоритм линейного программирования, который остается основой большинства современных программ; его работа появилась в 1992 году».

   Potra, Florian A .; Стивен Дж. Райт (2000). «Методы внутренней точки». Журнал вычислительной и прикладной математики. 124 (1–2): 281–302. Дои:10.1016 / S0377-0427 (00) 00433-7.

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