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

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

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

$\underset{}{}^{} minxfTx$

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

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

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

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

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

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

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

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

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

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

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

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

Создать начальную точку

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

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

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

Аналогично fmincon алгоритм внутренней точки, interior-point алгоритм пытается найти точку, где сохраняются условия Каруша-Куна-Такера (KKT). Чтобы описать эти уравнения для задачи линейного программирования, рассмотрим стандартную форму задачи линейного программирования после предварительной обработки:

$\underset{}{}^{} minxfTx при условии {\begin{matrix} \overset{}{} \overset{}{} \\ A¯x=b¯x+t=ux,t≥0. \end{matrix}$

Предположим, что все переменные имеют хотя бы одну конечную границу. При сдвиге и отрицании компонентов, если необходимо, это предположение означает, что все компоненты x имеют нижнюю границу 0.
$\overset{}{}$ A - это расширенная линейная матрица, которая включает в себя как линейные неравенства, так и линейные равенства. $\overset{b}{}$ - соответствующий линейный вектор равенства $\overset{}{.}$ Кроме того, элемент «s» включает в себя элементы для расширения вектора «x» с переменными «s», которые превращают ограничения неравенства в ограничения равенства:
$\overset{}{A}_x \begin{matrix} _{=} & ( \end{matrix} \begin{matrix} _{Aeq0AI} \\ ) \end{matrix} ($ x0s),
где x0 означает исходный x-вектор.
t - вектор слабых элементов, преобразующих верхние границы в равенства.

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

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

Лагранжиан - это

$^{}^{} \overset{}{} \overset{}{} L=fTx-yT (A¯x-b¯)^{}^{} −vTx−wT$ (u−x−t).

Следовательно, условия KKT для этой системы

$\begin{matrix} f {\overset{}{-}}^{A} Ty − \\ \overset{v}{} + \overset{w}{} \\ = 0A \\ _{_}_{x} = \\ _{b}_{_} x \\ + t = uvixi \end{matrix}$ = 0witi = 0 (x, v, w, t) ≥0.

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

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

(\begin{matrix} 0 & {\overset{}{-}}^{A} & DW-T0 \\ \overset{}{} & − \\ IIA-60000 \\ − \\ I0 & - \end{matrix} \begin{matrix} \begin{array}{l} I00V00X000W0T \end{array} \end{matrix}) (\begin{matrix} {\overset{}{}}^{} ΔxΔyΔtΔvΔw) \\ \overset{=}{} - \overset{(}{} \\ f - A-t \\ \begin{array}{l}  \end{array} \end{matrix} Ty - \begin{matrix} v_{} \\ +_{} \\ _{wA} \\ \begin{array}{l} __{x} \\ _{-} \end{array} \end{matrix} b

wetu − x − tVXWT) = − (rdrprprubru

(1)

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

_rd, двойной остаток
_rp, основной остаток
_руб., остаток верхней границы
_rvx, остаток комплементарности нижней границы
_rwt, остаток комплементарности верхней границы

Итеративный просмотр сообщает о следующих количествах:

$\begin{array}{l} Первобытный {_{}}_{} {_{}}_{} \\ infeasibility=‖rp‖1+‖rub‖1Dual {_{}}_{infeasibility=‖rd‖∞} . \end{array}$

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

(\begin{matrix} - & {\overset{DA}{}}^{} \\ \overset{}{DTA} \end{matrix} \begin{matrix} = \\ 0) \end{matrix} (\begin{matrix} {ΔxΔy}_{)} \end{matrix} =

− (Rrp),

(2)

где

$\begin{array}{l} D =^{X} -^{1V} \\ + T_{-}^{1WR}_{=} -^{rd}_{-} X^{-}_{1rvx} \end{array}$ + T − 1rwt + T − 1Wrub.

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

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

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

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

$\overset{}{A} Δx_{=}$ − rp

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

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

Замена

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

дает

\overset{}{A}_^{D} {\bar{}}^{} 1A _dw \overset{}{}^{TΔy} = -_{} A

_ D − 1R − rp.

(3)

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

Дополнительные сведения об алгоритме см. в разделе Mehrotra [6].

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

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

Условия остановки

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

$start= max (\overset{,}{1} ‖ A \overset{}{‖,} ‖$ f ‖, ‖ b ‖).

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

$\begin{matrix} {‖_{}}_{} {_{}}_{} \\ {_{}}_{} \\ _{} rp‖1+‖rub‖1≤ρTolCon‖rd‖∞≤ρTolFunrc≤TolFun \end{matrix}$ ,

где

$_{rc} \underset{}{=} макси ({мин}_{} (_{|}_{xivi} |,_{|} xi |, |_{} {vi}_{} |),_{} мин (_{|}$ tiwi |, | ti |, | wi |)).

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

Линейное программирование внутренних точек и старых версий

Введение

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

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

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

\underset{}{}^{} minxfTx такой , что {\begin{matrix} A⋅x=b0≤x≤u . \end{matrix}

(4)

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

\underset{}{}^{} minxfTx, что {\begin{matrix} A⋅x=bx+s=ux≥0, s≥0. \end{matrix}

(5)

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

^{} maxbTy -^{} uTw такой , что {\begin{matrix} ^{} \\ AT⋅y−w+z=fz≥0, w≥0, \end{matrix}

(6)

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

\begin{array}{l} F (x, y, z, s, \begin{matrix} w) = \\ ( \\ ^{} \\ _{}_{} \\ _{}_{} \end{matrix} \\ A⋅x−bx+s−uAT⋅y−w+z−fxizisiwi )  =  0 ,    x≥0 , z≥0, s≥0, w≥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.)

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

$_{Δvp} = {-^{} (FT}^{(v})) -$ 1F (v),

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

$_{Δvc} = {-^{} (FT}^{(v})) -_{1F} (v \overset{+}{}$ Δvp) − мке ^,

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

$v^{} + = v +_{} α (_{} Δvp$ + Δvc),

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

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

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

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

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

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

$\max \frac{(‖_{}}{rb‖max (1,} ‖ \frac{b_{} ‖}{), ‖} rf‖max \frac{(_{1},}{‖ f ‖), ‖} \frac{^{} {ru‖max}^{} (1,^{} ‖}{u ‖), |^{} fTx -^{} bTy^{+}} uTw 'max$ (1, | fTx |, | bTy − uTw |)) ≤tol,

где

$\begin{matrix} _{rb} = Ax \\ _{-}^{} brf = ATy \\ _{-} w + z - \end{matrix}$ fru = {x} + s − u

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

$^{} fTx -^{} {bTy}^{} +$ uTw

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

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

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

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

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

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

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

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

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

$\underset{}{}^{} minxfTx такой , что {\begin{matrix} A⋅x=b0≤x≤u . \end{matrix}$

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

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

$x^{} + \begin{array}{l} = & {xif \\ x & > 00if \end{array}$ x≤0.

Мера первичной несходимости -

$Основная несходимость \sqrt{{= {((lb}^{-}}^{x}) {{+) 2 +}^{} (}^{(} x {{- ub)}^{+})}^{} 2 {+ ((Ax −}^{b}})$ +) 2 + | Aeqx − beq | 2.

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

$^{} maxbTy -^{} uTw такой , что {\begin{matrix} ^{} \\ AT⋅y−w+z=fz≥0, w≥0. \end{matrix}$

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

$Двойная {^{}}_{infeasibility=‖ATy+z−w−f‖2} .$

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

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

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

Схема этапа 1

В фазе 1 алгоритм находит начальное базовое осуществимое решение (определение см. в разделе Основные и неосновные переменные), решая задачу вспомогательного кусочно-линейного программирования. Целевой функцией вспомогательной задачи является линейная штрафная функция P=∑jPj (xj), $\underset{}{}_{}_{}$

где _Pj (_xj) определяется

$_{Pj} (_{} xj) \begin{array}{l} =_{} {_{xj} & −_{} {ujif}_{} \\ xj >_{}_{} uj0if_{} \\ _{}_{} & _{}_{} lj\leqxj\lequjlj-xjif \end{array}$ lj > xj.

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

$\underset{}{} \underset{}{}_{minx∑jPj} подлежит {\begin{matrix} A⋅x≤bAeq⋅x=beq . \end{matrix}$

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

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

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

Схема этапа 2

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

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

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

$\underset{}{}^{} minxfTx такой , что {\begin{matrix} A⋅x=b,lb≤x≤ub . \end{matrix}$

(Обратите внимание, что A и b не являются матрицей и вектором, определяющими неравенства в исходной задаче.) Предположим, что A является матрицей m-на-n ранга m < n, столбцами которой являются {a1, a2, ..., an_}. Предположим, что { $_{{ai1}_{,}}_{_{ai2}}, ...,_{_{}} цель$ } является основой для пространства столбцов A, с индексным набором B = {_i1, _i2,..., _im}, и что N = {1, 2, ..., n }\B является дополнением B. Подматрица AB называется базисом, а комплементарная подматрица AN называется нонбазисом. Вектор основных переменных - xB, а вектор неосновных переменных - xN_. При каждой итерации в фазе 2 алгоритм заменяет один столбец текущего базиса столбцом неосновных и соответствующим образом обновляет переменные xB и xN.

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

Ссылки

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

[2] Эпплгейт, Д. Л., Р. Э. Биксби, В. Чватал и У. Дж. Кук, «Проблема коммивояжера: вычислительное исследование», Princeton University Press, 2007.

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

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

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

[6] Mehrotra, S. «О реализации метода первичных и двойственных внутренних точек». Журнал SIAM по оптимизации, том 2, 1992, стр. 575-601.

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

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