Алгоритмы линейного программирования

Линейное определение программирования

Линейное программирование является задачей нахождения векторный x, который минимизирует линейную функцию ^fTx, удовлетворяющий линейным ограничениям:

$\min_{x} f^{T} x$

таким образом, что один или несколько из следующего содержит:

A·x ≤ b
Aeq·x = beq
l ≤ x ≤ u.

Внутренняя точка `linprog` Алгоритм

linprog 'interior-point' алгоритм очень похож на выпуклый внутренней точкой quadprog Алгоритм. Это также совместно использует много функций с linprog 'interior-point-legacy' алгоритм. Эти алгоритмы имеют ту же общую схему:

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

Предварительно решить

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

Проверяйте, имеют ли какие-либо переменные равные верхние и нижние границы. Если так, проверяйте на выполнимость, и затем зафиксируйте и удалите переменные.
Проверяйте, включает ли какое-либо линейное ограничение неравенства только одну переменную. Если так, проверяйте на выполнимость, и затем измените линейное ограничение в связанное.
Проверяйте, включает ли какое-либо линейное ограничение равенства только одну переменную. Если так, проверяйте на выполнимость, и затем зафиксируйте и удалите переменную.
Проверяйте, имеет ли какая-либо линейная матрица ограничений нулевые строки. Если так, проверяйте на выполнимость, и затем удалите строки.
Определите, сопоставимы ли границы и линейные ограничения.
Проверяйте, появляются ли какие-либо переменные только как линейные члены в целевой функции и не появляются ни в каком линейном ограничении. Если так, проверяйте на выполнимость и ограниченность, и затем зафиксируйте переменные в их соответствующих границах.
Измените любые линейные ограничения неравенства в линейные ограничения равенства путем добавления слабых переменных.

Если алгоритм обнаруживает неосуществимую или неограниченную проблему, он останавливает и выпускает соответствующее выходное сообщение.

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

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

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

Сгенерируйте начальную точку

Установить начальную точку, x0, алгоритм делает следующее.

Инициализируйте x0 к ones(n,1), где n число элементов вектора целевой функции f.
Преобразуйте все ограниченные компоненты, чтобы иметь нижнюю границу 0. Если i компонента имеет конечную верхнюю границу u(i), затем x0(i) = u/2.
Для компонентов, которые имеют только один связанный, измените компонент при необходимости, чтобы лечь строго в связанном.
Помещать x0 близко к центральному пути сделайте один шаг корректора предиктора, и затем измените получившееся положение и слабые переменные, чтобы лечь хорошо в любых границах. Для получения дополнительной информации центрального пути, смотрите Носедэла и Райта [7], страница 397.

Корректор предиктора

Подобно fmincon алгоритм внутренней точки, interior-point-convex алгоритм пытается найти точку, где условия Karush-Kuhn-Tucker (KKT) содержат. Чтобы описать эти уравнения для задачи линейного программирования, рассмотрите стандартную форму задачи линейного программирования после предварительной обработки:

$\min_{x} f^{T} x при ограничениях {\begin{matrix} \bar{A} x = \bar{b} \\ x + t = u \\ x, t \geq 0. \end{matrix}$

Примите на данный момент, что все переменные имеют по крайней мере один конечный связанный. Путем сдвига и отрицания компонентов, при необходимости, это предположение означает, что все компоненты x имеют нижнюю границу 0.
$\bar{A}$ расширенная линейная матрица, которая включает и линейные неравенства и линейные равенства. $\bar{b}$ соответствующий линейный вектор равенства. $\bar{A}$ также включает условия для расширения векторного x со слабыми переменными s, которые поворачивают ограничения неравенства к ограничениям равенства:
$\bar{A} x = (\begin{matrix} A_{e q} & 0 \\ A & I \end{matrix}) (\begin{matrix} x_{0} \\ s \end{matrix}),$
где x ₀ средних значений исходный вектор x.
t является вектором слаксов, которые преобразуют верхние границы в равенства.

Функция Лагранжа для этой системы включает следующие векторы:

y, множители Лагранжа сопоставлены с линейными равенствами
v, множители Лагранжа, сопоставленные с нижней границей (ограничение положительности)
w, множители Лагранжа сопоставлены с верхней границей

Функция Лагранжа

$L = f^{T} x - y^{T} (\bar{A} x - \bar{b}) - v^{T} x - w^{T} (u - x - t) .$

Поэтому условия KKT для этой системы

$\begin{matrix} f - {\bar{A}}^{T} y - v + w = 0 \\ \bar{A} x = \bar{b} \\ x + t = u \\ v_{i} x_{i} = 0 \\ w_{i} t_{i} = 0 \\ (x, v, w, t) \geq 0. \end{matrix}$

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

Алгоритм сначала предсказывает шаг от формулы Ньютона-Raphson, и затем вычисляет шаг корректора. Корректор пытается уменьшать невязку в нелинейных уравнениях взаимозависимости _sizi = 0. Шаг Ньютона-Raphson

(\begin{matrix} 0 & - {\bar{A}}^{T} & 0 & - I & I \\ \bar{A} & 0 & 0 & 0 & 0 \\ - I & 0 & - I & 0 & 0 \\ V & 0 & 0 & X & 0 \\ 0 & 0 & W & 0 & T \end{matrix}) (\begin{matrix} Δ x \\ Δ y \\ Δ t \\ \begin{array}{l} Δ v \\ Δ w \end{array} \end{matrix}) = - (\begin{matrix} f - {\bar{A}}^{T} y - v + w \\ \bar{A} x - \bar{b} \\ u - x - t \\ \begin{array}{l} V X \\ W T \end{array} \end{matrix}) = - (\begin{matrix} r_{d} \\ r_{p} \\ r_{u b} \\ \begin{array}{l} r_{v x} \\ r_{w t} \end{array} \end{matrix}),

(1)

где X, V, W и T являются диагональными матрицами, соответствующими векторам x, v, w и t соответственно. Вектора невязок на ультраправой стороне уравнения:

_rd, двойная невязка
_rp, основная невязка
_rub, невязка верхней границы
_rvx, невязка взаимозависимости нижней границы
_rwt, невязка взаимозависимости верхней границы

Итеративное отображение сообщает об этих количествах:

$\begin{array}{l} Основная недопустимость = {‖ r_{p} ‖}_{1} + {‖ r_{u b} ‖}_{1} \\ Двойная недопустимость = {‖ r_{d} ‖}_{\infty} . \end{array}$

Чтобы решить уравнение 1, сначала преобразуйте его в форму симметрической матрицы

(\begin{matrix} - D & {\bar{A}}^{T} \\ \bar{A} & 0 \end{matrix}) (\begin{matrix} Δ x \\ Δ y \end{matrix}) = - (\begin{matrix} R \\ r_{p} \end{matrix}),

(2)

где

$\begin{array}{l} D = X^{- 1} V + T^{- 1} W \\ R = - r_{d} - X^{- 1} r_{v x} + T^{- 1} r_{w t} + T^{- 1} W r_{u b} . \end{array}$

Все обратные матрицы в определениях D и R просты вычислить, потому что матрицы являются диагональными.

Чтобы вывести уравнение 2 из уравнения 1, заметьте, что вторая строка уравнения 2 совпадает со второй строкой матрицы уравнения 1. Первая строка уравнения 2 прибывает из решения последних двух строк уравнения 1 для Δv и Δw и затем решения для Δt.

Уравнение 2 симметрично, но это не положительно определенный из-за термина –D. Поэтому вы не можете решить его с помощью факторизации Холесского. Еще несколько шагов приводят к различному уравнению, которое является положительно определенный, и следовательно может быть решено эффективно факторизацией Холесского.

Второй набор строк уравнения 2

$\bar{A} Δ x = - r_{p}$

и первый набор строк

$- D Δ x + {\bar{A}}^{T} Δ y = - R .$

Замена

$Δ x = D^{- 1} {\bar{A}}^{T} Δ y + D^{- 1} R$

дает

\bar{A} D^{- 1} {\bar{A}}^{T} Δ y = - \bar{A} D^{- 1} R - r_{p} .

(3)

Обычно, самый эффективный способ найти шаг Ньютона состоит в том, чтобы решить уравнение 3 для Δy с помощью факторизации Холесского. Факторизация Холесского возможна, потому что матрица, умножающаяся Δy, очевидно симметрична и, в отсутствие степеней вырождения, положительна определенный. Позже, чтобы найти шаг Ньютона, назад займите место, чтобы найти Δx, Δt, Δv, и Δw. Однако, когда $\bar{A}$ имеет плотный столбец, может быть более эффективно решить уравнение 2 вместо этого. linprog алгоритм внутренней точки выбирает алгоритм решения на основе плотности столбцов.

Для получения дополнительной информации алгоритма смотрите Mehrotra [6].

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

Алгоритм корректора предиктора является в основном тем же самым как полным quadprog 'interior-point-convex' версия, за исключением квадратичных условий. Смотрите Полный Корректор Предиктора.

Остановка условий

Алгоритм корректора предиктора выполняет итерации, пока он не достигает точки, которая выполнима (удовлетворяет ограничениям к в допусках), и где относительные размеры шага малы. А именно, задайте

$ρ = \max (1, ‖ \bar{A} ‖, ‖ f ‖, ‖ \bar{b} ‖) .$

Алгоритм останавливается, когда всем этим условиям удовлетворяют:

$\begin{matrix} {‖ r_{p} ‖}_{1} + {‖ r_{u b} ‖}_{1} \leq ρ TolCon \\ {‖ r_{d} ‖}_{\infty} \leq ρ TolFun \\ r_{c} \leq TolFun, \end{matrix}$

где

$r_{c} = \max_{i} (\min (| x_{i} v_{i} |, | x_{i} |, | v_{i} |), \min (| t_{i} w_{i} |, | t_{i} |, | w_{i} |)) .$

_rc по существу измеряет размер остаточных значений взаимозависимости xv и tw, которые являются каждым нулевые вектора в решении.

Устаревшее внутренней точкой линейное программирование

Введение

Устаревший внутренней точкой метод по умолчанию основан на LIPSOL ([52]), который является вариантом алгоритма корректора предиктора Мехротры ([47]), основной двойной метод внутренней точки.

Основной алгоритм

Алгоритм начинается путем применения ряда предварительной обработки шагов (см. Предварительную обработку). После предварительной обработки проблема имеет форму

\min_{x} f^{T} x таким образом , что {\begin{matrix} A \cdot x = b \\ 0 \leq x \leq u . \end{matrix}

(4)

Ограничения верхних границ неявно включены в матрицу ограничений A. Со сложением основных слабых переменных s уравнение 4 становится

\min_{x} f^{T} x таким образом , что {\begin{matrix} A \cdot x = b \\ x + s = u \\ x \geq 0, s \geq 0. \end{matrix}

(5)

который упоминается как основная проблема: x состоит из основных переменных, и s состоит из основных слабых переменных. Двойная проблема

\max b^{T} y - u^{T} w таким образом , что {\begin{matrix} A^{T} \cdot y - w + z = f \\ z \geq 0, w \geq 0, \end{matrix}

(6)

то, где y и w состоят из двойных переменных and z, состоит из двойных слаксов. Условия оптимальности для этой линейной программы, т.е. основное уравнение 5 и двойное уравнение 6,

\begin{array}{l} F (x, y, z, s, w) = (\begin{matrix} A \cdot x - b \\ x + s - u \\ A^{T} \cdot y - w + z - f \\ x_{i} z_{i} \\ s_{i} w_{i} \end{matrix}) = 0, \\ x \geq 0, z \geq 0, s \geq 0, w \geq 0, \end{array}

(7)

где _xizi и _siwi обозначают покомпонентное умножение.

Квадратные уравнения _xizi = 0 и _siwi = 0 называются условиями взаимозависимости для линейной программы; другие (линейные) уравнения называются условиями выполнимости. Количество

^xTz + ^sTw

разрыв дуальности, который измеряет невязку фрагмента взаимозависимости F когда (x,z,s,w) ≥ 0.

Алгоритм является основным двойным алгоритмом, означая, что и основное и двойные программы решены одновременно. Это может быть рассмотрено подобным Ньютону методом, применился к линейно-квадратичной системе F (x,y,z,s,w) = 0 в уравнении 7, в то время как одновременно хранение выполняет итерации x, z, w и положительного s, таким образом метод внутренней точки имени. (Выполнение итерации находится в строго внутренней области, представленной ограничениями неравенства в уравнении 5.)

Алгоритм является вариантом алгоритма корректора предиктора, предложенного Mehrotra. Рассмотрите выполнить итерации v = [x;y;z;s;w], где [x;z;s;w] > 0 Первых вычисляет так называемое направление предсказания

$Δ v_{p} = - {(F^{T} (v))}^{- 1} F (v),$

который является направлением Ньютона; затем так называемое направление корректора

$Δ v_{c} = - {(F^{T} (v))}^{- 1} F (v + Δ v_{p}) - μ \hat{e},$

где μ > 0 называется сосредотачивающимся параметром и должен быть выбран тщательно. $\hat{e}$ нулевой вектор с теми соответствующими квадратным уравнениям в F (v), т.е. возмущения только применяются к условиям взаимозависимости, которые все квадратичны, но не к условиям выполнимости, которые все линейны. Эти два направления объединены параметром длины шага α > 0 и обновляются, v, чтобы получить новое выполняют итерации v ⁺:

$v^{+} = v + α (Δ v_{p} + Δ v_{c}),$

где параметр длины шага α выбран так, чтобы

^v+ = [^{x+;y+;z+;s+;w+}]

удовлетворяет

[^x+;z+;s+;w+]> 0.

В решении для предыдущих направлений предиктора/корректора алгоритм вычисляет (разреженную) прямую факторизацию на модификации Факторов Холесского ^A·AT. Если A имеет плотные столбцы, он вместо этого использует формулу Шермана-Моррисона. Если то решение не соответствует (невязка является слишком большой), это выполняет LDL-разложение увеличенной системной формы уравнений шага, чтобы найти решение. (См. Пример 4 — Структура D (MATLAB) в MATLAB^® ldl страница ссылки на функцию.)

Алгоритм затем циклы до выполнения итерации сходится. Основной критерий остановки является стандартным:

$\max (\frac{‖ r_{b} ‖}{\max (1, ‖ b ‖)}, \frac{‖ r_{f} ‖}{\max (1, ‖ f ‖)}, \frac{‖ r_{u} ‖}{\max (1, ‖ u ‖)}, \frac{| f^{T} x - b^{T} y + u^{T} w |}{\max (1, | f^{T} x |, | b^{T} y - u^{T} w |)}) \leq t o l,$

где

$\begin{matrix} r_{b} = A x - b \\ r_{f} = A^{T} y - w + z - f \\ r_{u} = {x} + s - u \end{matrix}$

основная невязка, двойная невязка и выполнимость верхней границы соответственно ({x} означает тех x с конечными верхними границами), и

$f^{T} x - b^{T} y + u^{T} w$

различие между основными и двойными объективными значениями, и tol является некоторым допуском. Сумма в критерии остановки измеряет общие относительные погрешности условий оптимальности в уравнении 7.

Мера основной недопустимости || _rb ||, и мера двойной недопустимости || _rf ||, где норма является Евклидовой нормой.

Предварительная обработка

Проверяйте, имеют ли какие-либо переменные равные верхние и нижние границы. Если так, проверяйте на выполнимость, и затем зафиксируйте и удалите переменные.
Проверяйте, включает ли какое-либо линейное ограничение неравенства только одну переменную. Если так, проверяйте на выполнимость, и затем измените линейное ограничение в связанное.
Проверяйте, включает ли какое-либо линейное ограничение равенства только одну переменную. Если так, проверяйте на выполнимость, и затем зафиксируйте и удалите переменную.
Проверяйте, имеет ли какая-либо линейная матрица ограничений нулевые строки. Если так, проверяйте на выполнимость, и затем удалите строки.
Определите, сопоставимы ли границы и линейные ограничения.
Проверяйте, появляются ли какие-либо переменные только как линейные члены в целевой функции и не появляются ни в каком линейном ограничении. Если так, проверяйте на выполнимость и ограниченность, и затем зафиксируйте переменные в их соответствующих границах.
Измените любые линейные ограничения неравенства в линейные ограничения равенства путем добавления слабых переменных.

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

Для простоты алгоритм переключает все нижние границы, чтобы обнулить.

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

Двойной симплексный алгоритм

На высоком уровне, linprog 'dual-simplex' алгоритм по существу выполняет симплексный алгоритм на dual problem.

Алгоритм начинается путем предварительной обработки как описано в Предварительной обработке. Для получения дополнительной информации смотрите Андерсена и Андерсена [1] и Носедэл и Райт [7], Глава 13. Эта предварительная обработка уменьшает исходную задачу линейного программирования до формы уравнения 4:

$\min_{x} f^{T} x таким образом , что {\begin{matrix} A \cdot x = b \\ 0 \leq x \leq u . \end{matrix}$

A и b являются преобразованными версиями исходных ограничительных матриц. Это - основная проблема.

Основная выполнимость может быть задана в терминах ⁺ функция

$x^{+} = {\begin{array}{l} x & если x > 0 \\ 0 & если x \leq 0. \end{array}$

Мера основной недопустимости

$Primal infeasibility = \sqrt{{({(lb - x)}^{+})}^{2} + {({(x - ub)}^{+})}^{2} + {({(A x - b)}^{+})}^{2} + {| Aeq x - beq |}^{2}} .$

Как объяснено в уравнении 6, двойная проблема состоит в том, чтобы найти векторы y и w и слабым переменным векторным z, которые решают

$\max b^{T} y - u^{T} w таким образом , что {\begin{matrix} A^{T} \cdot y - w + z = f \\ z \geq 0, w \geq 0. \end{matrix}$

Мера двойной недопустимости

$Dual infeasibility = {‖ A^{T} y + z - w - f ‖}_{2} .$

Это известно (например, см. [7]), что любое конечное решение двойной проблемы дает решение основной проблемы, и любое конечное решение основной проблемы дает решение двойной проблемы. Кроме того, если или основная или двойная проблема неограниченна, то другая проблема неосуществима. И если или основная или двойная проблема неосуществима, то другая проблема или неосуществима или неограниченна. Поэтому эти две проблемы эквивалентны в терминах получения конечного решения, если вы существуете. Поскольку основные и двойные проблемы математически эквивалентны, но вычислительные шаги отличаются, может быть лучше решить основную задачу путем решения двойной задачи.

Чтобы помочь облегчить степень вырождения (см. Носедэла и Райта [7], страница 366), двойной симплексный алгоритм начинается путем беспокойства целевой функции.

Фаза 1 двойного симплексного алгоритма должна найти двойную допустимую точку. Алгоритм делает это путем решения вспомогательной задачи линейного программирования.

Фаза 1 Схема

В фазе 1 алгоритм находит начальное основное возможное решение (см. Основные и Неосновные Переменные для определения) путем решения вспомогательной кусочной задачи линейного программирования. Целевая функция вспомогательной проблемы является линейной функцией штрафа $P = \sum_{j} P_{j} (x_{j})$ ,

где _Pj (_xj) задан

$P_{j} (x_{j}) = {\begin{array}{l} x_{j} - u_{j} & если x_{j} > u_{j} \\ 0 & если l_{j} \leq x_{j} \leq u_{j} \\ l_{j} - x_{j} & если l_{j} > x_{j} . \end{array}$

P (x) измеряется, насколько точка x нарушает условия нижней и верхней границы. Вспомогательная проблема

$\min_{x} \sum_{j} P_{j} при ограничениях {\begin{matrix} A \cdot x \leq b \\ A e q \cdot x = b e q . \end{matrix}$

Исходная проблема имеет выполнимый пункт, если и только если вспомогательная проблема имеет минимальное значение 0.

Алгоритм находит начальную точку для вспомогательной проблемы эвристическим методом, который добавляет слабые и искусственные переменные по мере необходимости. Алгоритм затем использует эту начальную точку вместе с симплексным алгоритмом, чтобы решить вспомогательную задачу. Решение является начальной точкой для фазы 2 основного алгоритма.

Во время Фазы 2 решатель неоднократно выбирает входящую переменную и переменную отъезда. Алгоритм выбирает переменную отъезда согласно методу, предложенному Форрестом и Голдфарбом [3] названный двойной оценкой самого крутого ребра. Алгоритм выбирает входящую переменную с помощью изменения теста отношения Харриса, предложенного Коберштайном [5]. Чтобы помочь облегчить степень вырождения, алгоритм может ввести дополнительные возмущения во время Фазы 2.

Фаза 2 Схема

Решатель выполняет итерации, пытаясь обеспечить двойную выполнимость при сокращении основной недопустимости, пока решение уменьшаемой, встревоженной проблемы не и основное выполнимый и двойной выполнимый. Алгоритм раскручивает возмущения, которые он ввел. Если решение (к встревоженной проблеме) двойное неосуществимый для невозмутимой (исходной) проблемы, то решатель восстанавливает двойную выполнимость с помощью основного симплекса или алгоритмов Фазы 1. Наконец, решатель раскручивает шаги предварительной обработки, чтобы возвратить решение исходной проблемы.

Основные и неосновные переменные

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

$\min_{x} f^{T} x таким образом , что {\begin{matrix} A \cdot x = b, \\ l b \leq x \leq u b . \end{matrix}$

(Обратите внимание на то, что A и b не являются матрицей и вектором, задающим неравенства в исходной проблеме.) Принимают, что A является m-by-n матрица ранга m < n, столбцами которого является {a ₁, a ₂ ..., _an}. Предположим это ${a_{i_{1}}, a_{i_{2}}, ..., a_{i_{m}}}$ основание для пробела столбца A, с набором индекса B = {i ₁, i ₂..., _im}, и что N = {1, 2 ..., n }\\B является дополнением B. Субматрица A _B называется основанием и дополнительной субматрицей A _N, называется неоснованием. Вектором основных переменных является x _B, и вектором неосновных переменных является x _N. В каждой итерации в фазе 2 алгоритм заменяет один столбец текущего основания со столбцом неоснования и обновляет переменные x_{B и}x_N соответственно.

Если x является решением A·x = , b и все неосновные переменные в x _N равны или их нижним или верхним границам, x называется основным решением. Если кроме того, основные переменные в x _B удовлетворяют своим нижним и верхним границам, так, чтобы x был допустимой точкой, x называется основным возможным решением.

Ссылки

[1] Андерсен, E. D. и К. Д. Андерсен. Предварительное решение в линейном программировании. Математика. Программирование 71, 1995, стр 221–245.

[2] Applegate, D. L. R. E. Биксби, В. Чватэл и В. Дж. Кук, проблема коммивояжера: вычислительное исследование, издательство Принстонского университета, 2007.

[3] Форрест, J. J. и Д. Голдфарб. Алгоритмы симплекса самого крутого ребра для линейного программирования. Математика. Программирование 57, 1992, стр 341–374.

[4] Gondzio, J. “Несколько коррекций центрированности в основном двойном методе для линейного программирования”. Вычислительная Оптимизация и Приложения, Объем 6, Номер 2, 1996, стр 137–156. Доступный в https://www.maths.ed.ac.uk/~gondzio/software/correctors.ps.

[5] Коберштайн, A. Прогресс двойного симплексного алгоритма для того, чтобы решить крупномасштабные задачи LP: методы для быстрой и устойчивой реализации. Вычислительный Optim. и Приложение 41, 2008, стр 185–204.

[6] Mehrotra, S. “На Реализации Основного Двойного Метода внутренней точки”. SIAM Journal на Оптимизации, Издании 2, 1992, стр 575–601.

[7] Nocedal, J. и С. Дж. Райт. Числовая оптимизация, второй выпуск. Ряд Спрингера в исследовании операций, Springer-Verlag, 2006.

Документация