Самосогласованная функция

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

Самосогласованные функции

Многомерная самосогласованная функция

Вот общее определение самосогласованной функции. ^[2]^{: По умолчанию 2.0.1}

Пусть C — выпуклое непустое открытое множество в R ^н. Пусть f — функция, трижды непрерывно дифференцируемая, определенная на C . Мы говорим, что f самосогласована на C, если она удовлетворяет следующим свойствам:

1. Барьерное свойство : на любой последовательности точек в C , которая сходится к граничной точке C , f сходится к ∞.

2. Дифференциальное неравенство : для каждой точки x в C и любого направления h в R ^н, пусть g _h будет функцией f, ограниченной направлением h , то есть: g _h ( t ) = f ( x +t* h ). Тогда одномерная функция должна _gh удовлетворять следующему дифференциальному неравенству:

$|g_{h}'''(x)|\leq 2g_{h}''(x)^{3/2}$ .

Эквивалентно: ^[3]

$\left.{\frac {d}{d\alpha }}\nabla ^{2}f(x+\alpha y)\right|_{\alpha =0}\preceq 2{\sqrt {y^{T}\nabla ^{2}f(x)\,y}}\,\nabla ^{2}f(x)$

Одномерная самосогласованная функция

Функция $f:\mathbb {R} \rightarrow \mathbb {R}$ является самосогласованным по $\mathbb {R}$ если:

|f'''(x)|\leq 2f''(x)^{3/2}

Эквивалентно: если где угодно $f''(x)>0$ он удовлетворяет:

\left|{\frac {d}{dx}}{\frac {1}{\sqrt {f''(x)}}}\right|\leq 1

и удовлетворяет $f'''(x)=0$ в другом месте.

Примеры

Линейные и выпуклые квадратичные функции самосогласованы, поскольку их третья производная равна нулю.
Любая функция $f(x)=-\log(-g(x))-\log x$ $f(x)=-\log(-g(x))-\log x$ где $g(x)$ ${\ displaystyle g (x)}$ определена и выпукла для всех $x>0$ $x>0$ и проверяет $|g'''(x)|\leq 3g''(x)/x$ $|g'''(x)|\leq 3g''(x)/x$ , является самосогласованным в своей области, которая $\{x\mid x>0,g(x)<0\}$ $\{x\mid x>0,g (x)<0\}$ . Некоторые примеры:
- $g(x)=-x^{p}$ для $0<p\leq 1$
- $g(x)=-\log x$
- $g(x)=x^{p}$ для $-1\leq p\leq 0$
- $g(x)=(ax+b)^{2}/x$
- для любой функции $g$ удовлетворяющая условиям, функция $g(x)+ax^{2}+bx+c$ с $a\geq 0$ также удовлетворяет условиям.

Некоторые функции, которые не являются самосогласованными:

$f(x)=e^{x}$
$f(x)={\frac {1}{x^{p}}},x>0,p>0$
$f(x)=|x^{p}|,p>2$

Самосогласованные барьеры

Вот общее определение самосогласованного барьера (SCB). ^[2]^{: По умолчанию 3.1.1}

Пусть C — выпуклое замкнутое множество в R ^н с непустым салоном. Пусть f — функция из внутреннего пространства ( C ) в R. Пусть M >0 — действительный параметр. Мы говорим, что f является M -самосогласованным барьером для C, если он удовлетворяет следующему:

1. f — самосогласованная функция внутри ( C ).

2. Для каждой точки x внутри ( C ) и любого направления h в R ^н, пусть g _h будет функцией f, ограниченной направлением h , то есть: g _h ( t ) = f ( x +t* h ). Тогда одномерная функция должна _gh удовлетворять следующему дифференциальному неравенству:

$|g_{h}'(x)|\leq M^{1/2}\cdot g_{h}''(x)^{1/2}$ .

Создание SCB

Из-за важности SCB в методах внутренних точек важно знать, как создавать SCB для различных областей.

Теоретически можно доказать, что каждая замкнутая выпуклая область в R ^н имеет самосогласованный барьер с параметром O( n ). Но этот «универсальный барьер» задается некоторыми многомерными интегралами и слишком сложен для реальных вычислений. Следовательно, основная цель — построить эффективно вычислимые SCB. ^[4]^{: Раздел 9.2.3.3}

SCB могут быть построены из некоторых базовых SCB , которые объединяются для создания SCB для более сложных доменов, используя несколько правил комбинирования .

Базовые SCB

Каждая константа является самосогласованным барьером для всех R ^н, с параметром М=0. Это единственный самосогласованный барьер для всего пространства и единственный самосогласованный барьер с M < 1. ^[2]^{: Пример 3.1.1} [Обратите внимание, что линейные и квадратичные функции являются самосогласованными функциями, но не являются самосогласованными барьерами].

Для положительной полуоси $\mathbb {R} _{+}$ ( $x>0$ ), $f(x)=-\ln x$ является самосогласованным барьером с параметром $M=1$ . Это можно доказать непосредственно из определения.

Правило замены

Пусть G — замкнутая выпуклая область в R ^ни g M - SCB для G . Пусть x = Ay + b — аффинное отображение из R ^к в Р ^н с его изображением, пересекающим внутреннюю часть G . Пусть H — прообраз G при отображении: H = { y в R ^к | Ay+b в G }. Пусть h — сложная функция h ( y ) := g( Ay + b ). Тогда h является M для H. - SCB ^[2]^{: Предложение 3.1.1}

Например, возьмем n = 1, G — положительную полупрямую и $g(x)=-\ln x$ . Для любого k пусть a будет k -элементным вектором, а b - скаляром. Пусть H = { y в R ^к | а ^Тy+b ≥ 0} = k -мерное полупространство. По правилу замены $h(y)=-\ln(a^{T}y+b)$ является 1-SCB для H . Более распространенный формат: H = { x в R ^к | а ^Тx ≤ b}, для которого SCB $h(y)=-\ln(b-a^{T}y)$ .

Правило подстановки может быть распространено с аффинных отображений на некоторый класс «подходящих» отображений: ^[2]^{: Thm.9.1.1} и квадратичным отображениям. ^[2]^{: Под.9.3}

Правило декартова произведения

Для всех i из 1,..., m пусть G _i — замкнутая выпуклая область в R ^в, и g _i будет Mi _-SCB для Gi _пусть . Пусть G — декартово произведение всех G _i . Пусть g(x ₁ ,...,x _m ) := sum _i g _i ( x _i ). Тогда g является SCB для G с суммой параметров _i M _i . ^[2]^{: Предложение 3.1.1}

Например, возьмем все G _i как положительную полупрямую, так что G будет положительным ортантом. $\mathbb {R} _{+}^{m}$ . Позволять $g(x)=-\sum _{i=1}^{m}\ln x_{i}$ является m -SCB для G.

Теперь мы можем применить правило замены. Получаем, что для многогранника, определенного линейными неравенствами a _j^Тx ≤ b _j для j в 1,..., m , если он удовлетворяет условию Слейтера , то $f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)$ представляет собой м -SCB. Линейные функции $b_{j}-a_{j}^{T}x$ можно заменить квадратичными функциями .

Правило пересечения

Пусть G ₁ ,..., G _m — замкнутые выпуклые области в R ^н. Для каждого i из 1,..., m пусть g _i будет Mi _-SCB для Gi _, а r _i - вещественное число. Пусть G — пересечение всех G _i и предположим, что его внутренность непуста. Пусть g := sum _i r _i *g _i . Тогда g является SCB для G с суммой параметров _i r _i *M _i . ^[2]^{: Предложение 3.1.1}

Следовательно, если G определяется списком ограничений, мы можем найти SCB для каждого ограничения отдельно, а затем просто суммировать их, чтобы получить SCB G. для

Например, предположим, что область определяется m линейными ограничениями вида a _j^Тx ≤ b _j , для j в 1,..., m . Затем мы можем использовать правило пересечения для построения m -SCB. $f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)$ (тот самый, который мы ранее вычислили с помощью правила декартова произведения).

СКБ для эпиграфов

Надграфиком функции f x ( есть ) называется область над графиком функции, то $\{(x,t)\in \mathbb {R} ^{2}:t\geq f(x)\}$ . Надграфик функции f является выпуклым множеством тогда и только тогда, когда f — выпуклая функция . Следующие теоремы представляют некоторые функции f , для которых надграфик имеет SCB.

Пусть g ( t ) — 3-кратно непрерывно дифференцируемая вогнутая функция по t > 0 такая, что $t\cdot |g'''(t)|/|g''(t)|$ ограничено константой (обозначенной 3* b ) для всех t >0. Пусть G — двумерная выпуклая область: $G={\text{closure}}(\{(x,t)\in \mathbb {R} ^{2}:t>0,x\leq g(t)\}).$ Тогда функция f ( x , t ) = -ln(f(t)-x) - max[1,b ²]*ln(t) — самосогласованный барьер для G с параметром (1+max[1,b ²]). ^[2]^{: Предложение 9.2.1}

Примеры:

Пусть г ( т ) = т ^{1/ п}, для некоторого p ≥1 и b =(2 p -1)/(3 p ). Затем $G_{1}=\{(x,t)\in \mathbb {R} ^{2}:(x_{+})^{p}\leq t\}$ имеет 2-SCB. Сходным образом, $G_{2}=\{(x,t)\in \mathbb {R} ^{2}:([-x]_{+})^{p}\leq t\}$ имеет 2-SCB. Используя правило пересечения, мы получаем, что $G=G_{1}\cap G_{2}=\{(x,t)\in \mathbb {R} ^{2}:|x|^{p}\leq t\}$ имеет 4-СКБ.
Пусть g ( t )=ln( t ) и b =2/3. Затем $G=\{(x,t)\in \mathbb {R} ^{2}:e^{x}\leq t\}$ имеет 2-SCB.

Теперь мы можем построить SCB для задачи минимизации p -нормы: $\min _{x}\sum _{j=1}^{n}|v_{j}-x^{T}u_{j}|^{p}$ , где v _j — постоянные скаляры, u _j — постоянные векторы, а p > 0 — константа. Сначала мы преобразуем это в минимизацию линейной цели: $\min _{x}\sum _{j=1}^{n}t_{j}$ , с ограничениями: $t_{j}\geq |v_{j}-x^{T}u_{j}|^{p}$ для всех j в [ м ]. Для каждого ограничения у нас есть 4-SCB по правилу аффинной замены. Используя правило пересечения, мы получаем (4 n )-SCB для всей допустимой области.

Аналогично, пусть g — 3-кратно непрерывно дифференцируемая выпуклая функция на луче x > 0 такая, что: $x\cdot |g'''(x)|/|g''(x)|\leq 3b$ для всех х >0. Пусть G — двумерная выпуклая область: замыкание({ ( t,x ) в R ²: x>0, t ≥ g ( x ) }). Тогда функция f ( x , t ) = -ln(tf(x)) - max[1,b ²]*ln(x) — самосогласованный барьер для G с параметром (1+max[1,b ²]). ^[2]^{: Предложение 9.2.2}

Примеры:

Пусть g ( x ) = x ^{- п}, для некоторого p > 0 и b=(2+ p )/3. Затем $G_{1}=\{(x,t)\in \mathbb {R} ^{2}:x^{-p}\leq t,x\geq 0\}$ имеет 2-SCB.
Пусть g ( x ) = x ln ( x ) и b = 1/3. Затем $G=\{(x,t)\in \mathbb {R} ^{2}:x\ln x\leq t,x\geq 0\}$ имеет 2-SCB.

SCB для конусов

Для конуса второго порядка $\{(x,y)\in \mathbb {R} ^{n-1}\times \mathbb {R} \mid \|x\|\leq y\}$ , функция $f(x,y)=-\log(y^{2}-x^{T}x)$ является самосогласованным барьером.
Для конуса положительно полуопределенных m*m симметричных матриц функция $f(A)=-\log \det A$ является самосогласованным барьером.
Для квадратичной области, определяемой $\phi (x)>0$ где $\phi (x)=\alpha +\langle a,x\rangle -{\frac {1}{2}}\langle Ax,x\rangle$ где $A=A^{T}\geq 0$ — положительная полуопределенная симметричная матрица, логарифмический барьер $f(x)=-\log \phi (x)$ согласуется с $M=2$
Для экспоненциального конуса $\{(x,y,z)\in \mathbb {R} ^{3}\mid ye^{x/y}\leq z,y>0\}$ , функция $f(x,y,z)=-\log(y\log(z/y)-x)-\log z-\log y$ является самосогласованным барьером.
Для силового конуса $\{(x_{1},x_{2},y)\in \mathbb {R} _{+}^{2}\times \mathbb {R} \mid |y|\leq x_{1}^{\alpha }x_{2}^{1-\alpha }\}$ , функция $f(x_{1},x_{2},y)=-\log(x_{1}^{2\alpha }x_{2}^{2(1-\alpha )}-y^{2})-\log x_{1}-\log x_{2}$ является самосогласованным барьером.

История

Как упоминалось в «Комментариях к библиографии». ^[5] из их книги 1994 года, ^[6] самосогласованные функции были введены в 1988 году Юрием Нестеровым. ^[7]^[8] и далее развивался вместе с Аркадием Немировским . ^[9] Как поясняется в ^[10] их основное наблюдение заключалось в том, что метод Ньютона является аффинно-инвариантным в том смысле, что если для функции $f(x)$ у нас есть шаги Ньютона $x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})$ тогда для функции $\phi (y)=f(Ay)$ где $A$ является невырожденным линейным преобразованием, начиная с $y_{0}=A^{-1}x_{0}$ у нас есть шаги Ньютона $y_{k}=A^{-1}x_{k}$ который можно показать рекурсивно

y_{k+1}=y_{k}-[\phi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1}A^{T}f'(Ay_{k})=A^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f'(x_{k})=A^{-1}x_{k+1}

.

Однако стандартный анализ метода Ньютона предполагает, что гессиан $f$ является липшицевым непрерывным , т.е. $\|f''(x)-f''(y)\|\leq M\|x-y\|$ для некоторой константы $M$ . Если мы предположим, что $f$ 3 раза непрерывно дифференцируемо, то это эквивалентно

|\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}

для всех

u,v\in \mathbb {R} ^{n}

где $f'''(x)[u]=\lim _{\alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]$ . Тогда левая часть приведенного выше неравенства инвариантна относительно аффинного преобразования $f(x)\to \phi (y)=f(Ay),u\to A^{-1}u,v\to A^{-1}v$ , однако правая часть - нет.

Авторы отмечают, что правую часть можно сделать также инвариантной, если заменить евклидову метрику скалярным произведением, определяемым гессианом $f$ определяется как $\|w\|_{f''(x)}=\langle f''(x)w,w\rangle ^{1/2}$ для $w\in \mathbb {R} ^{n}$ . Затем они приходят к определению самосогласованной функции как

|\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}

.

Характеристики

Линейная комбинация

Если $f_{1}$ и $f_{2}$ согласуются с константами $M_{1}$ и $M_{2}$ и $\alpha ,\beta >0$ , затем $\alpha f_{1}+\beta f_{2}$ согласуется с константой $\max(\alpha ^{-1/2}M_{1},\beta ^{-1/2}M_{2})$ .

Аффинное преобразование

Если $f$ согласуется с константой $M$ и $Ax+b$ представляет собой аффинное преобразование $\mathbb {R} ^{n}$ , затем $\phi (x)=f(Ax+b)$ также согласуется с параметром $M$ .

Выпуклое сопряжение

Если $f$ самосогласован, то его выпуклое сопряжение $f^{*}$ также является самосогласованным. ^[11]^[12]

Неединственный гессиан

Если $f$ является самосогласованным и является областью $f$ не содержит прямых (бесконечен в обоих направлениях), то $f''$ не является особенным.

И наоборот, если для некоторого $x$ в области $f$ и $u\in \mathbb {R} ^{n},u\neq 0$ у нас есть $\langle f''(x)u,u\rangle =0$ , затем $\langle f''(x+\alpha u)u,u\rangle =0$ для всех $\alpha$ для чего $x+\alpha u$ находится в области $f$ а потом $f(x+\alpha u)$ является линейным и не может иметь максимума, поэтому все $x+\alpha u,\alpha \in \mathbb {R}$ находится в области $f$ . Отметим также, что $f$ не может иметь минимум внутри своей области.

Приложения

Помимо прочего, самосогласованные функции полезны при анализе метода Ньютона . Самосогласованные барьерные функции используются для разработки барьерных функций, используемых в методах внутренних точек для выпуклой и нелинейной оптимизации. Обычный анализ метода Ньютона не работает для барьерных функций, поскольку их вторая производная не может быть липшицевой, иначе они были бы ограничены на любом компактном подмножестве $\mathbb {R} ^{n}$ .

Самосогласованные барьерные функции

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

Минимизация самосогласованной функции

Самосогласованную функцию можно минимизировать с помощью модифицированного метода Ньютона, где у нас есть ограничение на количество шагов, необходимых для сходимости. Мы предполагаем здесь, что $f$ является стандартной самосогласованной функцией, то есть самосогласованной с параметром $M=2$ .

Определим декремент Ньютона $\lambda _{f}(x)$ из $f$ в $x$ как размер шага Ньютона $[f''(x)]^{-1}f'(x)$ в локальной норме, определяемой гессианом $f$ в $x$

\lambda _{f}(x)=\langle f''(x)[f''(x)]^{-1}f'(x),[f''(x)]^{-1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1}f'(x),f'(x)\rangle ^{1/2}

Тогда для $x$ в области $f$ , если $\lambda _{f}(x)<1$ тогда можно доказать, что итерация Ньютона

x_{+}=x-[f''(x)]^{-1}f'(x)

также будет находиться в области $f$ . Это происходит потому, что на основе самосогласования $f$ , можно дать некоторые конечные оценки значения $f(x_{+})$ . У нас далее есть

\lambda _{f}(x_{+})\leq {\Bigg (}{\frac {\lambda _{f}(x)}{1-\lambda _{f}(x)}}{\Bigg )}^{2}

Тогда, если у нас есть

\lambda _{f}(x)<{\bar {\lambda }}={\frac {3-{\sqrt {5}}}{2}}

то также гарантируется, что $\lambda _{f}(x_{+})<\lambda _{f}(x)$ , чтобы мы могли продолжать использовать метод Ньютона до сходимости. Обратите внимание, что для $\lambda _{f}(x_{+})<\beta$ для некоторых $\beta \in (0,{\bar {\lambda }})$ мы имеем квадратичную сходимость $\lambda _{f}$ до 0 как $\lambda _{f}(x_{+})\leq (1-\beta )^{-2}\lambda _{f}(x)^{2}$ . Тогда это дает квадратичную сходимость $f(x_{k})$ к $f(x^{*})$ и из $x$ к $x^{*}$ , где $x^{*}=\arg \min f(x)$ , по следующей теореме. Если $\lambda _{f}(x)<1$ затем

\omega (\lambda _{f}(x))\leq f(x)-f(x^{*})\leq \omega _{*}(\lambda _{f}(x))

\omega '(\lambda _{f}(x))\leq \|x-x^{*}\|_{x}\leq \omega _{*}'(\lambda _{f}(x))

со следующими определениями

\omega (t)=t-\log(1+t)

\omega _{*}(t)=-t-\log(1-t)

\|u\|_{x}=\langle f''(x)u,u\rangle ^{1/2}

Если мы начнем метод Ньютона с некоторого $x_{0}$ с $\lambda _{f}(x_{0})\geq {\bar {\lambda }}$ тогда нам придется начать с использования демпфированного метода Ньютона, определенного формулой

x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})

Для этого можно показать, что $f(x_{k+1})\leq f(x_{k})-\omega (\lambda _{f}(x_{k}))$ с $\omega$ как определено ранее. Обратите внимание, что $\omega (t)$ является возрастающей функцией для $t>0$ так что $\omega (t)\geq \omega ({\bar {\lambda }})$ для любого $t\geq {\bar {\lambda }}$ , поэтому значение $f$ гарантированно уменьшается на определенную величину на каждой итерации, что также доказывает, что $x_{k+1}$ находится в области $f$ .

Ссылки

^ Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Аркадий Немировский (2004). «Методы полиномиального времени внутренней точки в выпуклом программировании» .
^ Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 15 октября 2011 г.
^ Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .
^ Нестеров Юрий; Немировский, Аркадий (январь 1994 г.). Полиномиальные алгоритмы внутренней точки в выпуклом программировании (библиографические комментарии) . Общество промышленной и прикладной математики. дои : 10.1137/1.9781611970791.bm . ISBN 978-0-89871-319-0 .
^ Нестеров, И︠У︡. Э. (1994). Полиномиальные алгоритмы внутренней точки в выпуклом программировании . Немировский Аркадий Семенович. Филадельфия: Общество промышленной и прикладной математики. ISBN 0-89871-319-6 . ОСЛК 29310677 .
^ Yu. E. NESTEROV, Polynomial time methods in linear and quadratic programming, Izvestija AN SSSR, Tekhnitcheskaya kibernetika, No. 3, 1988, pp. 324-326. (In Russian.)
^ Ю. НЕСТЕРОВ Е., Полиномиальные итерационные методы в линейном и квадратичном программировании, Вопросы кибернетики, Москва, 1988, стр. 102-125. (На русском языке.)
^ Ю. Е. Нестеров и А. С. Немировский, Самосогласованные функции и полиномиально-временные методы в выпуклом программировании, Технический отчет, Центральный экономико-математический институт АН СССР, Москва, СССР, 1989.
^ Нестеров, И︠У︡. Е. Вводные лекции по выпуклой оптимизации: базовый курс . Бостон. ISBN 978-1-4419-8853-9 . ОСЛК 883391994 .
^ Нестеров Юрий; Немировский, Аркадий (1994). «Полиномиальные алгоритмы внутренней точки в выпуклом программировании» . Исследования в области прикладной и вычислительной математики . дои : 10.1137/1.9781611970791 . ISBN 978-0-89871-319-0 .
^ Сунь, Тяньсяо; Тран-Динь, Куок (2018). «Обобщенные самосогласованные функции: рецепт методов типа Ньютона». Математическое программирование : Предложение 6. arXiv : 1703.04599 .

[:0-1] Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

[:1-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Аркадий Немировский (2004). «Методы полиномиального времени внутренней точки в выпуклом программировании» .

[3] Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 15 октября 2011 г.

[:02-4] Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

[5] Нестеров Юрий; Немировский, Аркадий (январь 1994 г.). Полиномиальные алгоритмы внутренней точки в выпуклом программировании (библиографические комментарии) . Общество промышленной и прикладной математики. дои : 10.1137/1.9781611970791.bm . ISBN 978-0-89871-319-0 .

[6] Нестеров, И︠У︡. Э. (1994). Полиномиальные алгоритмы внутренней точки в выпуклом программировании . Немировский Аркадий Семенович. Филадельфия: Общество промышленной и прикладной математики. ISBN 0-89871-319-6 . ОСЛК 29310677 .

[7] Yu. E. NESTEROV, Polynomial time methods in linear and quadratic programming, Izvestija AN SSSR, Tekhnitcheskaya kibernetika, No. 3, 1988, pp. 324-326. (In Russian.)

[8] Ю. НЕСТЕРОВ Е., Полиномиальные итерационные методы в линейном и квадратичном программировании, Вопросы кибернетики, Москва, 1988, стр. 102-125. (На русском языке.)

[9] Ю. Е. Нестеров и А. С. Немировский, Самосогласованные функции и полиномиально-временные методы в выпуклом программировании, Технический отчет, Центральный экономико-математический институт АН СССР, Москва, СССР, 1989.

[10] Нестеров, И︠У︡. Е. Вводные лекции по выпуклой оптимизации: базовый курс . Бостон. ISBN 978-1-4419-8853-9 . ОСЛК 883391994 .

[11] Нестеров Юрий; Немировский, Аркадий (1994). «Полиномиальные алгоритмы внутренней точки в выпуклом программировании» . Исследования в области прикладной и вычислительной математики . дои : 10.1137/1.9781611970791 . ISBN 978-0-89871-319-0 .

[12] Сунь, Тяньсяо; Тран-Динь, Куок (2018). «Обобщенные самосогласованные функции: рецепт методов типа Ньютона». Математическое программирование : Предложение 6. arXiv : 1703.04599 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]