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

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

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

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

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

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

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

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

Предварительно решите, имея в виду упрощение и преобразование проблемы к стандартной форме.
Сгенерируйте начальную точку. Выбор начальной точки особенно важен для решения алгоритмов внутренней точки эффективно, и этот шаг может быть длительным.
Итерации корректора предиктора, чтобы решить уравнения 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}$

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

(\begin{matrix} 0 & - {\bar{A}}^{T} & 0 & - I & I \\ \bar{A} & 0000 \\ - I & 0 & - I & 00 \\ V & 00 & X \\ 000 & 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} Основной infeasibility = {‖ r_{p} ‖}_{1} + {‖ r_{u b} ‖}_{} \\ 1Dual infeasibility = {‖ 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.

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

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

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

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

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

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

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

На высоком уровне алгоритм 'dual-simplex' linprog по существу выполняет симплексный алгоритм на 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}$

Мера основного infeasibility

$Основной 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}$

Мера двойного infeasibility

$Двойной 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 Схема

Решатель выполняет итерации, пытаясь поддержать двойную выполнимость при сокращении основного infeasibility, пока решение уменьшаемой, встревоженной проблемы не и основное выполнимый и двойной выполнимый. Алгоритм раскручивает возмущения, которые он ввел. Если решение (к встревоженной проблеме) двойное неосуществимый для невозмутимой (исходной) проблемы, то решатель восстанавливает двойную выполнимость с помощью основного симплекса или алгоритмов Фазы 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. Доступный в http://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.

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