Метод внутренней точки

Алгоритмы решения задач выпуклой оптимизации

Пример поиска решения. Синие линии показывают ограничения, красные точки — повторяющиеся решения.

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

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

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

История

Метод внутренней точки был открыт советским математиком И.И. Дикиным в 1967 году. ^[1] Метод был заново изобретен в США в середине 1980-х годов. В 1984 году Нарендра Кармаркар разработал метод линейного программирования , названный алгоритмом Кармаркара ^[2] , который выполняется за доказуемо полиномиальное время ( операции над L -битными числами, где n — количество переменных и констант), а также очень эффективен на практике. . Статья Кармаркара вызвала всплеск интереса к методам внутренних точек. Два года спустя Джеймс Ренегар изобрел первый метод движения по внутренней точке с использованием времени выполнения . Позже метод был расширен от линейных до задач выпуклой оптимизации на основе самосогласованной барьерной функции , используемой для кодирования выпуклого множества . ^[3] ${\displaystyle O(n^{3.5}L)}$ ${\displaystyle O(n^{3}L)}$

Любую задачу выпуклой оптимизации можно преобразовать в минимизацию (или максимизацию) линейной функции на выпуклом множестве путем преобразования к форме надграфика . ^{[4] : 143} Идея кодирования допустимого множества с использованием барьера и разработки барьерных методов изучалась Энтони В. Фиакко, Гартом П. Маккормиком и другими в начале 1960-х годов. Эти идеи в основном развивались для общего нелинейного программирования , но позже от них отказались из-за наличия более конкурентоспособных методов для этого класса задач (например, последовательного квадратичного программирования ).

Юрий Нестеров и Аркадий Немировский придумали особый класс таких барьеров, с помощью которых можно закодировать любое выпуклое множество. Они гарантируют, что количество итераций алгоритма ограничено полиномом по размерности и точности решения. ^{[5] [3]}

Класс примитивно-двойственных методов следования по внутренней точке считается наиболее успешным. Алгоритм предиктора-корректора Мехротры обеспечивает основу для большинства реализаций этого класса методов. ^[6]

Определения

Нам дана выпуклая программа вида:

$${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &x\in G.\end{aligned}}}$$

выпуклая функциявыпуклое множествоможно предположить, что целевое значение f является линейной функциейG— _{выпуклые}

$${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &g_{i}(x)\leq 0{\text{ for }}i=1,\dots ,m.\\\end{aligned}}}$$

коэффициентовразмеромрешательx _ttсходящимся,εTεtTx _tε-приблизительным,

ж ( Икс ) - ж ^* ≤ ε

г _я ( Икс ) ≤ ε для я в 1,..., м ,

х в G ,

где f ^* — оптимальное решение. Решатель называется полиномиальным , если общее количество арифметических операций за первые T шагов не превосходит

поли(размер проблемы) * log( V / ε ),

где V — некоторая константа, зависящая от данных, например, разница между наибольшим и наименьшим значением в допустимом наборе. Другими словами, V / ε — это «относительная точность» решения — точность по наибольшему коэффициенту. log( V / ε ) представляет количество «цифр точности». Следовательно, решатель является «полиномиальным», если каждая дополнительная цифра точности требует количества операций, полиномиального по размеру задачи.

Типы

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

• Возможные методы уменьшения : алгоритм Кармаркара был первым.
• Методы следования по пути : алгоритмы Джеймса Ренегара ^[7] и Кловиса Гонзаги ^[8] были первыми.
• Первично-двойственные методы .

Методы следования по пути

Идея

Учитывая программу выпуклой оптимизации (P) с ограничениями, мы можем преобразовать ее в программу без ограничений , добавив барьерную функцию . В частности, пусть b — гладкая выпуклая функция, определенная внутри допустимой области G , такая, что для любой последовательности { x _j in Interior(G)}, предел которой находится на границе G : . Мы также предполагаем, что b невырожден, то есть: положительно определен для всех x в интерьере (G). Теперь рассмотрим семейство программ: ${\displaystyle \lim _{j\to \infty }b(x_{j})=\infty }$ ${\displaystyle b''(x)}$

( P _t ) минимизировать t * f(x) + b(x)

Технически программа ограничена, поскольку b определен только внутри G. Но практически ее можно решить как программу без ограничений, поскольку любой решатель, пытающийся минимизировать функцию, не приблизится к границе, где b стремится к бесконечности. Следовательно, ( P _t ) имеет единственное решение — обозначим его x *( t ). Функция x * является непрерывной функцией t , которая называется центральным путем . Все предельные точки x * при стремлении t к бесконечности являются оптимальными решениями исходной программы (P).

Метод следования по пути — это метод отслеживания функции x * вдоль некоторой возрастающей последовательности t ₁ ,t ₂ ,..., то есть: вычисление достаточно хорошего приближения x _i к точке x *( t _i ), такая, что разность x _i - x *( t _i ) приближается к 0, когда i приближается к бесконечности; тогда последовательность x _i приближается к оптимальному решению (P). Для этого необходимо указать три вещи:

• Барьерная функция b(x).
• Политика определения штрафных параметров t _i .
• Решатель неограниченной оптимизации, используемый для решения ( _P i ₎ и поиска xi , например, метод Ньютона . Обратите внимание, что мы можем использовать каждый xi в качестве _{отправной} точки для решения следующей задачи ( P _i+1 ).

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

Ренегар ^[7] и Гонзага ^[8] доказали, что конкретный экземпляр метода следования по пути является политаймовым:

• Ограничения (и цель) являются линейными функциями;
• Барьерная функция является логарифмической : b(x) := - sum _j log( -g _j ( x )).
• Параметр штрафа t обновляется геометрически, то есть , где µ – константа (они взяли , где m – количество ограничений-неравенств); ${\displaystyle t_{i+1}:=\mu \cdot t_{i}}$ ${\displaystyle \mu =1+0.001\cdot {\sqrt {m}}}$
• Решающая программа — это метод Ньютона, и для каждого шага t выполняется один шаг Ньютона .

Они доказали, что в этом случае разница x _i - x *( t _i ) остается не более 0,01, а f( x _i ) - f* составляет не более 2* m / t _i . Таким образом, точность решения пропорциональна 1/ t _i , поэтому для добавления одной цифры точности достаточно умножить ti _на 2 (или любой другой постоянный коэффициент), что требует O(sqrt( m )) шагов Ньютона. . Поскольку каждый шаг Ньютона занимает O( mn ² ) операций, общая сложность составляет O( m ^3/2 n ² ) операций для разряда точности.

Юрий Нестеров распространил идею от линейных программ к нелинейным. Он отметил, что основным свойством логарифмического барьера, использованным в приведенных выше доказательствах, является то, что он самосогласован с конечным параметром барьера. Следовательно, многие другие классы выпуклых программ могут быть решены за политайм с использованием метода следования по пути, если мы сможем найти подходящую самосогласованную барьерную функцию для их допустимой области. ^{[3] : Раздел 1}

Подробности

Нам дана задача выпуклой оптимизации (П) в «стандартной форме»:

минимизировать c ^T x st x в G ,

где G выпуклая и замкнутая. Мы также можем предположить, что G ограничена (мы можем легко сделать ее ограниченной, добавив ограничение | x |≤ R для некоторого достаточно большого R ). ^{[3] : Раздел 4}

Чтобы использовать метод внутренней точки, нам нужен самосогласованный барьер для G. Пусть b — M -самосогласованный барьер для G , где M ≥1 — параметр самосогласования. Мы предполагаем, что можем эффективно вычислить значение b , его градиент и гессиан для каждой точки x внутри G.

Для каждого t > 0 мы определяем штрафную цель f _t (x) := c ^T x + b( x ) . Мы определяем путь минимизаторов следующим образом: x*(t) := arg min f _t (x) . Аппориметрируем этот путь по возрастающей последовательности t _i . Последовательность инициализируется определенной нетривиальной двухфазной процедурой инициализации. Затем он обновляется по следующему правилу: . ${\displaystyle t_{i+1}:=\mu \cdot t_{i}}$

Для каждого t _i мы находим приблизительный минимум _f ti _, обозначаемый xi . Приблизительный минимум выбирается так, чтобы удовлетворять следующему «условию близости» (где L — допуск пути ):

${\displaystyle {\sqrt {[\nabla _{x}f_{t}(x_{i})]^{T}[\nabla _{x}^{2}f_{t}(x_{i})]^{-1}[\nabla _{x}f_{t}(x_{i})]}}\leq L}$.

Чтобы найти x _{i +1} , мы начинаем с x _i и применяем демпфированный метод Ньютона . Мы применяем несколько шагов этого метода, пока вышеуказанное «отношение близости» не будет удовлетворено. Первая точка, удовлетворяющая этому соотношению, обозначается x _{i +1} . ^{[3] : Раздел 4}

Конвергенция и сложность

Скорость сходимости метода определяется следующей формулой для каждого i : ^{[3] : Предложение 4.4.1.}

${\displaystyle c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}}$

Принимая , число шагов Ньютона, необходимое для перехода от xi к xi +1 _{, не} превышает фиксированного числа, которое зависит только от r _и L . В частности, общее число шагов Ньютона, необходимое для нахождения ε -приближенного решения (т.е. нахождения x в G такого, что c ^T x - c* ≤ ε ), не превышает: ^{[3] : Thm.4.4.1} ${\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}$

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1\right)}$

где постоянный множитель O(1) зависит только от r и L. Число шагов Ньютона, необходимое для двухэтапной процедуры инициализации, не превышает: ^{[3] : Thm.4.5.1.}

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1\right)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{\text{Var}}_{G}(c)}{\epsilon }}+1\right)}$^{[ нужны разъяснения ]}

где постоянный множитель O(1) зависит только от r и L и , и является некоторой точкой внутри G . В целом, общая ньютоновская сложность поиска ε -приближенного решения не превышает ${\displaystyle {\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x}$ ${\displaystyle {\bar {x}}}$

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)}$, где V — некоторая константа, зависящая от задачи: . ${\displaystyle V={\frac {{\text{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}}$

Каждый шаг Ньютона занимает O( n ³ ) арифметических операций.

Инициализация: методы фазы I

Чтобы инициализировать методы следования по пути , нам нужна точка внутри допустимой области G. Другими словами: если G определяется неравенствами gi ( x ) ≤ 0, то нам нужен некоторый x , для которого gi ₍ x ₎ < 0 для всех i из 1,..., m . Если у нас нет такой точки, нам нужно найти ее, используя так называемый метод фазы I. ^{[4] : 11.4} Простой метод этапа I заключается в решении следующей выпуклой программы:

$${\displaystyle {\begin{aligned}{\text{minimize}}\quad &s\\{\text{subject to}}\quad &g_{i}(x)\leq s{\text{ for }}i=1,\dots ,m\end{aligned}}}$$

s

• Если s *<0, то мы знаем, что x* является внутренней точкой исходной задачи и можем перейти к «фазе II», которая решает исходную задачу.
• Если s *>0, то мы знаем, что исходная программа недопустима — допустимая область пуста.
• Если s *=0 и оно достигается некоторым решением x*, то задача разрешима, но не имеет внутренней точки; если оно не достигнуто, то задача невыполнима.

Для этой программы легко получить внутреннюю точку: мы можем произвольно взять x = 0 и принять s за любое число, большее max( f ₁ (0),..., f _m (0)). Поэтому ее можно решить методами внутренних точек. Однако время выполнения пропорционально log(1/ s *). Когда s* приближается к 0, становится все труднее и труднее найти точное решение проблемы фазы I и, следовательно, труднее решить, выполнима ли исходная задача.

Практические соображения

Теоретические гарантии предполагают, что параметр штрафа увеличивается со скоростью , поэтому наихудшее число требуемых шагов Ньютона равно . Теоретически, если µ больше (например, 2 или более), то наихудшее количество требуемых шагов Ньютона находится в . Однако на практике большее значение ц приводит к гораздо более быстрой сходимости. Эти методы называются методами длинного шага . ^{[3] : Раздел 4.6} На практике, если µ находится между 3 и 100, то программа сходится за 20-40 шагов Ньютона, независимо от количества ограничений (хотя время выполнения каждого шага Ньютона, конечно, растет с количеством шагов Ньютона). ограничения). Точное значение μ в этом диапазоне мало влияет на производительность. ^{[4] : глава 11} ${\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}$ ${\displaystyle O({\sqrt {M}})}$ ${\displaystyle O(M)}$

Методы снижения потенциала

Для методов потенциальной редукции задача представляется в конической форме : ^{[3] : разд.5}

минимизировать c ^T x st x в {b+L} ᚢ K ,

где b — вектор в Rn ^, L — линейное подпространство в Rn ⁽ поэтому b + L — аффинная плоскость ), а K — замкнутый заостренный выпуклый конус с непустой внутренностью. Любую выпуклую программу можно преобразовать к конической форме. Чтобы использовать метод редукции потенциала (в частности, расширение алгоритма Кармаркара до выпуклого программирования), нам необходимы следующие предположения: ^{[3] : раздел 6.}

• А. Допустимое множество {b+L} ᚢ K ограничено и пересекает внутреннюю часть конуса K .
• Б. Нам заранее дано строго допустимое решение х ^, т. е . допустимое решение внутри К.
• C. Мы заранее знаем оптимальное целевое значение c* задачи.
• D. Дан M -логарифмически-однородный самосогласованный барьер F для конуса K .

Допущения A, B и D необходимы в большинстве методов внутренней точки. Предположение C специфично для подхода Кармаркара; его можно смягчить, используя «скользящее объективное значение». Возможно дальнейшее сведение программы к формату Кармаркара :

минимизировать s ^T x st x в M ᚢ K и e ^T x = 1

где M — линейное подпространство в Rn ^, а оптимальное целевое значение равно 0. Метод основан на следующей скалярной потенциальной функции:

v ( Икс ) знак равно F ( Икс ) + M пер ( s ^Т Икс )

где F — M -самосогласованный барьер для допустимого конуса. Можно доказать, что, когда x строго осуществима и v ( x ) очень мало (- очень отрицательно), x приблизительно оптимален. Идея метода уменьшения потенциала состоит в том, чтобы изменить x так, чтобы потенциал на каждой итерации уменьшался как минимум на фиксированную константу X (в частности, X = 1/3-ln(4/3)). Это означает, что после i итераций разница между целевым значением и оптимальным целевым значением составляет не более V * exp(- i X / M ), где V — константа, зависящая от данных. Следовательно, число шагов Ньютона, необходимое для получения ε -приближенного решения, не превышает . ${\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1}$

Обратите внимание, что в методах следования по пути это выражение, а не M , что теоретически лучше. Но на практике метод Кармаркара позволяет сделать гораздо большие шаги к цели, поэтому он может сойтись гораздо быстрее, чем теоретические гарантии. ${\displaystyle {\sqrt {M}}}$

Первично-двойственные методы

Идею первично-двойственного метода легко продемонстрировать для нелинейной оптимизации с ограничениями . ^{[9] [10]} Для простоты рассмотрим следующую задачу нелинейной оптимизации с ограничениями-неравенствами:

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f(x)\\{\text{subject to}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{\text{ for }}i=1,\ldots ,m,\\{\text{where}}\quad &f:\mathbb {R} ^{n}\to \mathbb {R} ,\ c_{i}:\mathbb {R} ^{n}\to \mathbb {R} .\end{aligned}}\quad (1)}$$

Эта задача оптимизации с ограничениями из-за неравенства решается путем преобразования ее в неограниченную целевую функцию, минимум которой мы надеемся найти эффективно. В частности, логарифмическая барьерная функция , связанная с (1), равна

$${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}$$

Вот небольшой положительный скаляр, иногда называемый «параметром барьера». При сходимости к нулю минимум должен сходиться к решению (1). ${\displaystyle \mu }$ ${\displaystyle \mu }$ ${\displaystyle B(x,\mu )}$

Градиент дифференцируемой функции обозначается . Градиент барьерной функции равен ${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle \nabla h}$

$${\displaystyle \nabla B(x,\mu )=\nabla f(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x).\quad (3)}$$

В дополнение к исходной («основной») переменной мы вводим двойную переменную , основанную на множителе Лагранжа. ${\displaystyle x}$ ${\displaystyle \lambda \in \mathbb {R} ^{m}}$

$${\displaystyle c_{i}(x)\lambda _{i}=\mu ,\quad \forall i=1,\ldots ,m.\quad (4)}$$

Уравнение (4) иногда называют условием «возмущенной дополнительности» из-за его сходства с «дополнительной нежесткостью» в условиях ККТ .

Мы пытаемся найти те, у которых градиент барьерной функции равен нулю. ${\displaystyle (x_{\mu },\lambda _{\mu })}$

Подставив из (4) в (3), получим уравнение для градиента: ${\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu }$

$${\displaystyle \nabla B(x_{\mu },\lambda _{\mu })=\nabla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)}$$

якобиан ${\displaystyle J}$ ${\displaystyle c(x)}$

Интуиция, лежащая в основе (5), заключается в том, что градиент должен лежать в подпространстве, охватываемом градиентами ограничений. «Возмущенную дополнительность» при малых (4) можно понимать как условие, что решение должно либо лежать вблизи границы , либо проекция градиента на нормаль компоненты ограничения должна быть почти равна нулю. ${\displaystyle f(x)}$ ${\displaystyle \mu }$ ${\displaystyle c_{i}(x)=0}$ ${\displaystyle \nabla f}$ ${\displaystyle c_{i}(x)}$

Пусть — направление поиска для итеративного обновления . Применяя метод Ньютона к (4) и (5), получаем уравнение для : ${\displaystyle (p_{x},p_{\lambda })}$ ${\displaystyle (x,\lambda )}$ ${\displaystyle (p_{x},p_{\lambda })}$

$${\displaystyle {\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-\nabla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}},}$$

где - матрица Гессе , - диагональная матрица , и - диагональная матрица . ${\displaystyle H}$ ${\displaystyle B(x,\mu )}$ ${\displaystyle \operatorname {diag} (\lambda )}$ ${\displaystyle \lambda }$ ${\displaystyle \operatorname {diag} (c(x))}$ ${\displaystyle c(x)}$

Ввиду (1), (4) условие

${\displaystyle \lambda \geq 0}$

должны соблюдаться на каждом этапе. Это можно сделать, выбрав подходящие : ${\displaystyle \alpha }$

${\displaystyle (x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}$

Траектория итераций x с использованием метода внутренней точки.

Типы выпуклых программ, решаемых методами внутренних точек

Вот некоторые частные случаи выпуклых программ, которые можно эффективно решить методами внутренних точек. ^{[3] : Раздел 10.}

Линейные программы

Рассмотрим линейную программу вида:

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b.\end{aligned}}.}$$

$${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x).}$$

Mmmn ²m ^3/2 n ^{2[ нужны разъяснения ]} ${\displaystyle b}$

Квадратичные программы с квадратичными ограничениями

Дана квадратичная программа с квадратичными ограничениями вида:

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &d^{\top }x\\{\text{subject to}}\quad &f_{j}(x):=x^{\top }A_{j}x+b_{j}^{\top }x+c_{j}\leq 0\quad {\text{ for all }}j=1,\dots ,m,\end{aligned}}}$$

Aj _{являются} положительно-полуопределенными

$${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).}$$

Mm(m+n)n ²m ^1/2n ² ${\displaystyle b}$

L p аппроксимация нормы

Рассмотрим задачу вида

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{\top }x|_{p}\end{aligned}},}$$

нормой L pMm(m+n)n ²m ^1/2n ² ${\displaystyle u_{j}}$ ${\displaystyle v_{j}}$ ${\displaystyle |\cdot |_{p}}$ ${\displaystyle 1<p<\infty .}$

Геометрические программы

Рассмотрите проблему

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f_{0}(x):=\sum _{i=1}^{k}c_{i0}\exp(a_{i}^{\top }x)\\{\text{subject to}}\quad &f_{j}(x):=\sum _{i=1}^{k}c_{ij}\exp(a_{i}^{\top }x)\leq d_{j}\quad {\text{ for all }}j=1,\dots ,m.\end{aligned}}}$$

Имеется самосогласованный барьер с параметром 2k + m . Метод следования по пути имеет ньютоновскую сложность O( mk ² + k ³ + n ³ ) и общую сложность O (( k+m ) ^1/2 [ mk ² + k ³ + n ³ ]).

Полуопределенные программы

Методы внутренних точек можно использовать для решения полуопределенных программ. ^{[3] : Раздел 11.}

Смотрите также

• Аффинное масштабирование
• Расширенный метод Лагранжа
• Алгоритм Шамболь-Пока
• Условия Каруша – Куна – Такера
• Метод штрафа

Рекомендации

1. Дикин, И.И. (1967). «Итеративное решение задач линейного и квадратичного программирования». Докл. Акад. Наук СССР . 174 (1): 747–748.
2. Кармаркар, Н. (1984). «Новый алгоритм линейного программирования с полиномиальным временем» (PDF) . Материалы шестнадцатого ежегодного симпозиума ACM по теории вычислений – STOC '84 . п. 302. дои : 10.1145/800057.808695 . ISBN 0-89791-133-4. Архивировано из оригинала (PDF) 28 декабря 2013 года.
3. Аркадий Немировский (2004). Полиномиальные методы внутренней точки в выпуклом программировании.
4. Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-83378-3. МР  2061575.
5. Райт, Маргарет Х. (2004). «Революция внутренней точки в оптимизации: история, последние события и долгосрочные последствия». Бюллетень Американского математического общества . 42 : 39–57. дои : 10.1090/S0273-0979-04-01040-7 . МР  2115066.
6. Потра, Флориан А.; Стивен Дж. Райт (2000). «Методы внутренних точек». Журнал вычислительной и прикладной математики . 124 (1–2): 281–302. дои : 10.1016/S0377-0427(00)00433-7 .
7. Ренегар, Джеймс (1 января 1988 г.). «Алгоритм с полиномиальным временем, основанный на методе Ньютона, для линейного программирования». Математическое программирование . 40 (1): 59–93. дои : 10.1007/BF01580724. ISSN  1436-4646.
8. Гонзага, Кловис К. (1989), Мегиддо, Нимрод (ред.), «Алгоритм решения задач линейного программирования в операциях O (n3L)», Прогресс в математическом программировании: внутренняя точка и связанные методы , Нью-Йорк, Нью-Йорк: Спрингер, стр. 1–28, номер документа : 10.1007/978-1-4613-9617-8_1, ISBN. 978-1-4613-9617-8, получено 22 ноября 2023 г.
9. Мехротра, Санджай (1992). «О реализации метода первично-двойственной внутренней точки». SIAM Journal по оптимизации . 2 (4): 575–601. дои : 10.1137/0802028.
10. Райт, Стивен (1997). Методы первично-двойственной внутренней точки . Филадельфия, Пенсильвания: СИАМ. ISBN 978-0-89871-382-4.

• Боннан, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастисабал, Клаудия А. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. дои : 10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. МР  2265882.
• Носедаль, Хорхе; Стивен Райт (1999). Численная оптимизация . Нью-Йорк, штат Нью-Йорк: Спрингер. ISBN 978-0-387-98793-4.
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 10.11. Линейное программирование: методы внутренних точек». Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.