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

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

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

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

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

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

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

Вывод

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

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

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

${ displaystyle { begin {align} & { underset {x} { min}} & q (x) & = c ^ {T} x, & { text {st}} & Ax & = b, & ; & x & geq 0, end {выровнено}}}$

где ${ 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 х в mathbb {R} ^ {п раз 1}}$ - вектор переменных.

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

${ displaystyle { begin {align} A ^ {T} lambda + s & = c, ; ; ; { text {(условие градиента Лагранжа)}} Ax & = b, ; ; ; { text {(Условие выполнимости)}} XSe & = 0, ; ; ; { text {(Условие дополнительности)}} (x, s) & geq 0, end {выровнено}} }$

где ${ displaystyle X = { text {diag}} (x)}$ и ${ displaystyle S = { text {diag}} (s)}$ откуда ${ Displaystyle е = (1,1, точки, 1) ^ {T} in mathbb {R} ^ {п раз 1}}$ .

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

${ displaystyle { begin {align} F (x, lambda, s) = { begin {bmatrix} A ^ {T} lambda + sc Ax-b XSe end {bmatrix}} & = 0 (x, s) & geq 0 end {выровнено}}}$

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

${ 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 + sc, ; ; ; r_ {b} = Ax-b}$

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

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

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

Для значения параметра центрирования ${ Displaystyle сигма в [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 {align} 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 {выравнивается}}}$

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

Длина шага

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

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

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

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

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

[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.

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

[1]

[2]

[3]