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

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

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

Методы внутренних точек (также называемые барьерными методами или 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]

Определения

Нам дана выпуклая программа вида: где f — выпуклая функция , а G — выпуклое множество . Без потери общности можно предположить, что целевое f — линейная функция . Обычно выпуклое множество G представляется набором выпуклых неравенств и линейных равенств; линейные равенства можно исключить с помощью линейной алгебры, поэтому для простоты мы предполагаем, что существуют только выпуклые неравенства, и программу можно описать следующим образом, где g _i — выпуклые функции: Мы предполагаем, что функции ограничений принадлежат некоторому семейству (например, квадратичным функциям), так что программу можно представить конечным вектором коэффициентов (например, коэффициентами квадратичных функций). Размерность этого вектора коэффициентов называется размером программы . Численный решатель для заданного семейства программ — это алгоритм, который по заданному вектору коэффициентов генерирует последовательность приближенных решений x _t для t = 1, 2,..., используя конечное число арифметических операций. Числовой решатель называется сходящимся , если для любой программы из семейства и любого положительного ε >0 существует некоторое T (которое может зависеть от программы и от ε ) такое, что для любого t > T приближенное решение x _t является ε-приближенным, то есть: где — оптимальное решение. Решатель называется полиномиальным, если общее число арифметических операций на первых T шагах не превышает $${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &x\in G.\end{aligned}}}$$ $${\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}}}$$ $${\displaystyle {\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad {\text{for}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}}$$ ${\displaystyle f^{*}}$

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

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

Типы

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

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

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

Идея

Учитывая выпуклую программу оптимизации (P) с ограничениями, мы можем преобразовать ее в программу без ограничений , добавив барьерную функцию . В частности, пусть b будет гладкой выпуклой функцией, определенной внутри допустимой области G , такой, что для любой последовательности { x _j in interior(G)}, предел которой находится на границе G : . Мы также предполагаем, что b невырождена, то есть: положительно определена для всех x in interior(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 ) и нахождения x _i , например, метод Ньютона . Обратите внимание, что мы можем использовать каждый x _i в качестве отправной точки для решения следующей задачи ( 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 , поэтому для добавления одной цифры точности достаточно умножить t _i на 2 (или любой другой постоянный множитель), что требует O(sqrt( m )) шагов Ньютона. Поскольку каждый шаг Ньютона занимает O( mn ² ) операций, общая сложность составляет O( m ^3/2 n ² ) операций для цифры точности.

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

Подробности

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

минимизировать 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 , обозначаемый как x _i . Приблизительный минимум выбирается так, чтобы удовлетворять следующему «условию близости» (где 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}}$

Принимая , число шагов Ньютона, необходимых для перехода от x _i к x _{i +1} , не превышает фиксированного числа, зависящего только от r и L. В частности, общее число шагов Ньютона, необходимых для нахождения ε -приближенного решения (т.е. нахождения x в G такого, что c ^T x - c* ≤ ε ), не превышает: ^{[3] : Теор.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] : Теор.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 определяется неравенствами g _i ( x ) ≤ 0, то нам нужен некоторый x , для которого g _i ( x ) < 0 для всех i из 1,..., m . Если у нас нет такой точки, нам нужно найти ее, используя так называемый метод фазы I. [ ^{4] : 11.4} Простой метод фазы I заключается в решении следующей выпуклой программы: Обозначим оптимальное решение через x*, s *. $${\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 *<0, то мы знаем, что x* является внутренней точкой исходной задачи и можем перейти к «фазе II», которая является решением исходной задачи.
• Если s *>0, то мы знаем, что исходная программа неосуществима — допустимая область пуста.
• Если s *=0 и достигается некоторым решением x*, то задача разрешима, но не имеет внутренней точки; если s *=0, то задача неразрешима.

Для этой программы легко получить внутреннюю точку: мы можем произвольно взять 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 — вектор в R ⁿ , L — линейное подпространство в R ⁿ (так что b + L — аффинная плоскость ), а K — замкнутый заостренный выпуклый конус с непустой внутренностью. Любая выпуклая программа может быть преобразована в коническую форму. Чтобы использовать метод потенциальной редукции (в частности, расширение алгоритма Кармаркара на выпуклое программирование), нам нужны следующие предположения: ^{[3] : Раздел 6}

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

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

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

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

v ( x ) = F ( x ) + M ln ( s ^T x )

где 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}

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

Рассмотрим линейную программу вида: Мы можем применить методы следования по пути с барьером Функция самосогласована с параметром M = m (число ограничений). Следовательно, число требуемых шагов Ньютона для метода следования по пути равно O( mn ² ), а общая сложность времени выполнения равна O( m ^3/2 n ² ). ^{[ необходимо пояснение ]} $${\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).}$$ ${\displaystyle b}$

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

Дана квадратично ограниченная квадратичная программа вида: где все матрицы A _j являются положительно-полуопределенными матрицами . Мы можем применить методы следования по пути с барьером Функция является самосогласованным барьером с параметром M = m . Сложность Ньютона составляет O( (m+n)n ² ), а общая сложность времени выполнения составляет O( m ^1/2 (m+n) n ² ). $${\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}}}$$ $${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).}$$ ${\displaystyle b}$

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

Рассмотрим задачу вида , где каждый является вектором, каждый является скаляром и является нормой L p с После преобразования в стандартную форму мы можем применить методы следования по пути с самосогласованным барьером с параметром M =4 m . Сложность Ньютона составляет O( (m+n)n ² ), а общая сложность времени выполнения составляет O( m ^1/2 (m+n) n ² ). $${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{\top }x|_{p}\end{aligned}},}$$ ${\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}}}$$

Существует самосогласованный барьер с параметром 2 k + 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. doi : 10.1145/800057.808695 . ISBN 0-89791-133-4. Архивировано из оригинала (PDF) 28 декабря 2013 года.
3. Аркадий Немировский (2004). Полиномиальные методы внутренней точки в выпуклом программировании.
4. Бойд, Стивен; Ванденберг, Ливен (2004). Выпуклая оптимизация . Кембридж: Cambridge University Press . ISBN 978-0-521-83378-3. МР  2061575.
5. Райт, Маргарет Х. (2004). «Революция внутренней точки в оптимизации: история, последние разработки и долгосрочные последствия». Бюллетень Американского математического общества . 42 : 39–57. doi : 10.1090/S0273-0979-04-01040-7 . MR  2115066.
6. Potra, Florian A.; Stephen J. Wright (2000). «Методы внутренних точек». Журнал вычислительной и прикладной математики . 124 (1–2): 281–302. doi : 10.1016/S0377-0427(00)00433-7 .
7. Renegar, James (1 января 1988 г.). «Алгоритм полиномиального времени, основанный на методе Ньютона, для линейного программирования». Математическое программирование . 40 (1): 59–93. doi :10.1007/BF01580724. ISSN  1436-4646.
8. Gonzaga, Clovis C. (1989), Megiddo, Nimrod (ред.), "Алгоритм решения задач линейного программирования за O(n3L) операций", Progress in Mathematical Programming: Interior-Point and Related Methods , New York, NY: Springer, стр. 1–28, doi :10.1007/978-1-4613-9617-8_1, ISBN 978-1-4613-9617-8, получено 22 ноября 2023 г.
9. Мехротра, Санджай (1992). «О реализации метода первично-двойственной внутренней точки». Журнал SIAM по оптимизации . 2 (4): 575–601. doi :10.1137/0802028.
10. Райт, Стивен (1997). Методы первично-двойной внутренней точки . Филадельфия, Пенсильвания: SIAM. ISBN 978-0-89871-382-4.

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе пересмотренное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. МР  2265882.
• Нокедаль, Хорхе; Стивен Райт (1999). Численная оптимизация . Нью-Йорк, Нью-Йорк: Springer. ISBN 978-0-387-98793-4.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 10.11. Линейное программирование: методы внутренних точек". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8. Архивировано из оригинала 11 августа 2011 . Получено 12 августа 2011 .