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

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

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

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

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

<reservedrangesplaceholder1> ≤ <reservedrangesplaceholder0>
Aeq·x = beq
<reservedrangesplaceholder2> ≤ <reservedrangesplaceholder1> ≤ <reservedrangesplaceholder0> .

Интерьерно-точечные `linprog` Алгоритм

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

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

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

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

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

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

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

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

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

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

Чтобы задать начальную точку, x0алгоритм делает следующее.

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

Предиктор-корректор

Подобно fmincon алгоритм внутренней точки, interior-point алгоритм пытается найти точку, в которой держатся условия Каруша-Куна-Такера (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 с переменными slack s которые поворачивают ограничения неравенства к ограничениям равенства:
$\bar{A} x = (\begin{matrix} A_{e q} & 0 \\ A & I \end{matrix}) (\begin{matrix} x_{0} \\ s \end{matrix}),$
где x 0 означает исходный вектор 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.

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

(\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, которые являются каждыми нулевыми векторами в решении.

Линейное программирование Interior-Point-Legacy

Введение

Метод interior-point-legacy основан на LIPSOL ([52]), который является вариантом алгоритма Mehrotra predictor-corrector ([47]), метода primal-dual interior-point.

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

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

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

(4)

Ограничения верхних границ неявно включены в A матрицы ограничений. С сложением основных переменных slack 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 состоит из основных переменных slack. Двойственная проблема

\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 состоят из двойственных переменных, а 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 называются условиями комплементарности для линейной программы; другие (линейные) уравнения называются условиями выполнимости. Количество

x^Tz + s^Tw

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

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

Алгоритм является вариантом алгоритма предиктор-корректор, предложенного Мехротрой. Рассмотрим итерацию 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;⁺;⁺; w⁺]

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

[x⁺z;⁺;⁺; w⁺] > 0.

В решении для предыдущих направлений предиктора/корректора алгоритм вычисляет (разреженную) прямую факторизацию на модификации факторов Холецкого A· A^T. Если у A плотные столбцы, он вместо этого использует формулу Шермана-Моррисона. Если это решение не является адекватным (невязка слишком велик), это выполняет LDL-разложение дополненной системной формы уравнений шага, чтобы найти решение. (См. пример 4 - Структура D в 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.

Мера основной недопустимость _{||<reservedrangesplaceholder1>||}, и мера _{двойственной} недопустимость ||<reservedrangesplaceholder0>||, где норма является евклидовой нормой.

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

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

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

Для простоты алгоритм смещает все нижние границы в нуль.

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

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

На высоком уровне, 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, и вектор с переменной slack 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]), что любое конечное решение двойственной задачи даёт решение основной задачи, а любое конечное решение основной задачи даёт решение двойственной задачи. Кроме того, если основная или двойственная задача неограниченна, то другая проблема недопустима. И если либо основная, либо двойственная задача недопустима, то другая проблема либо недопустима, либо неограниченна. Поэтому две задачи эквивалентны с точки зрения получения конечного решения, если оно существует. Поскольку основные и двойственные задачи математически эквивалентны, но вычислительные шаги различаются, может быть лучше решить основную задачу, решив двойственную задачу.

Чтобы помочь облегчить дегенерацию (см. Nocedal и Wright [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.

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

Во время Фазы 2 решатель неоднократно выбирает входящую переменную и уходящую переменную. Алгоритм выбирает уходящую переменную в соответствии с методом, предложенной Forrest и Goldfarb [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 1_, a 2,. .._, an}. Предположим, что ${a_{i_{1}}, a_{i_{2}}, ..., a_{i_{m}}}$ является базисом для пространства столбцов A с набором индексов B = {i 1, _i 2,..., _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] Андерсен, Э. Д. и К. Д. Андерсен. Сохранение в линейном программировании. Math. Программирование 71, 1995, pp. 221-245.

[2] Applegate, D. L., R. E. Bixby, V. Chvátal and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2007.

[3] Форрест, Дж. Дж., и Д. Голдфарб. Алгоритмы простейшего края для линейного программирования. Math. Программирование 57, 1992, pp. 341-374.

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

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

[6] Mehrotra, S. «On the Implementation of a Primal-Dual Interior Point Point Method». SIAM Journal on Optimization, Vol. 2, 1992, pp 575-601.

[7] Nocedal, J. and S. J. Wright. Численная оптимизация, второе издание. Springer Series in Operations Research, Springer-Verlag, 2006.

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