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

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

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

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

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

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

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

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

| г час ‴ ( х ) | ≤ 2 г час ″ ( х ) 3 / 2 {\displaystyle |g_{h}'''(x)|\leq 2g_{h}''(x)^{3/2}} .

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

г г α ∇ 2 ф ( х + α у ) | α = 0 ⪯ 2 у Т ∇ 2 ф ( х ) у ∇ 2 ф ( х ) {\displaystyle \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)}

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

Функция является самосогласованной, если : ф : Р → Р {\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} } Р {\displaystyle \mathbb {R} }

| ф ‴ ( х ) | ≤ 2 ф ″ ( х ) 3 / 2 {\displaystyle |f'''(x)|\leq 2f''(x)^{3/2}}

Эквивалентно: если где-либо выполняется: ф ″ ( х ) > 0 {\displaystyle f''(x)>0}

| г г х 1 ф ″ ( х ) | ≤ 1 {\displaystyle \left|{\frac {d}{dx}}{\frac {1}{\sqrt {f''(x)}}}\right|\leq 1}

и удовлетворяет в другом месте. ф ‴ ( х ) = 0 {\displaystyle f'''(x)=0}

Примеры

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

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

  • ф ( х ) = е х {\displaystyle f(x)=e^{x}}
  • ф ( х ) = 1 х п , х > 0 , п > 0 {\displaystyle f(x)={\frac {1}{x^{p}}},x>0,p>0}
  • ф ( х ) = | х п | , п > 2 {\displaystyle f(x)=|x^{p}|,p>2}

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

Вот общее определение самосогласованного барьера (SCB). [2] : Опр.3.1.1 

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

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

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

| г час ′ ( х ) | ≤ М 1 / 2 ⋅ г час ″ ( х ) 1 / 2 {\displaystyle |g_{h}'(x)|\leq M^{1/2}\cdot g_{h}''(x)^{1/2}} .

Строительство SCB

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

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

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

Базовые SCB

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

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

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

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

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

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

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

Для всех i из 1,..., m пусть G i будет замкнутой выпуклой областью в R ni , и пусть g i будет M i -SCB для G i . Пусть G будет декартовым произведением всех G i . Пусть g(x 1 ,...,x m )  := sum i g i ( x i ). Тогда g является SCB для G с параметром sum i M i . [2] : Предл. 3.1.1 

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

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

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

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

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

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

SCB для эпиграфов

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

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

Примеры:

  • Пусть g ( t ) = t 1/ p , для некоторого p ≥1, и b =(2 p -1)/(3 p ). Тогда имеет 2-SCB. Аналогично имеет 2-SCB. Используя правило пересечения, получаем, что имеет 4-SCB. G 1 = { ( x , t ) ∈ R 2 : ( x + ) p ≤ t } {\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:(x_{+})^{p}\leq t\}} G 2 = { ( x , t ) ∈ R 2 : ( [ − x ] + ) p ≤ t } {\displaystyle G_{2}=\{(x,t)\in \mathbb {R} ^{2}:([-x]_{+})^{p}\leq t\}} G = G 1 ∩ G 2 = { ( x , t ) ∈ R 2 : | x | p ≤ t } {\displaystyle G=G_{1}\cap G_{2}=\{(x,t)\in \mathbb {R} ^{2}:|x|^{p}\leq t\}}
  • Пусть g ( t )=ln( t ) и b =2/3. Тогда имеет 2-SCB. G = { ( x , t ) ∈ R 2 : e x ≤ t } {\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:e^{x}\leq t\}}

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

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

Примеры:

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

SCB для конусов

  • Для конуса второго порядка функция является самосогласованным барьером. { ( x , y ) ∈ R n − 1 × R ∣ ‖ x ‖ ≤ y } {\displaystyle \{(x,y)\in \mathbb {R} ^{n-1}\times \mathbb {R} \mid \|x\|\leq y\}} f ( x , y ) = − log ⁡ ( y 2 − x T x ) {\displaystyle f(x,y)=-\log(y^{2}-x^{T}x)}
  • Для конуса положительно полуопределенных симметричных матриц размера m*m функция является самосогласованным барьером. f ( A ) = − log ⁡ det A {\displaystyle f(A)=-\log \det A}
  • Для квадратичной области, определяемой соотношением , где — положительно полуопределенная симметричная матрица, логарифмический барьер согласуется с ϕ ( x ) > 0 {\displaystyle \phi (x)>0} ϕ ( x ) = α + ⟨ a , x ⟩ − 1 2 ⟨ A x , x ⟩ {\displaystyle \phi (x)=\alpha +\langle a,x\rangle -{\frac {1}{2}}\langle Ax,x\rangle } A = A T ≥ 0 {\displaystyle A=A^{T}\geq 0} f ( x ) = − log ⁡ ϕ ( x ) {\displaystyle f(x)=-\log \phi (x)} M = 2 {\displaystyle M=2}
  • Для экспоненциального конуса функция является самосогласованным барьером. { ( x , y , z ) ∈ R 3 ∣ y e x / y ≤ z , y > 0 } {\displaystyle \{(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 {\displaystyle f(x,y,z)=-\log(y\log(z/y)-x)-\log z-\log y}
  • Для конуса мощности функция представляет собой самосогласованный барьер. { ( x 1 , x 2 , y ) ∈ R + 2 × R ∣ | y | ≤ x 1 α x 2 1 − α } {\displaystyle \{(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 α x 2 2 ( 1 − α ) − y 2 ) − log ⁡ x 1 − log ⁡ x 2 {\displaystyle 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 ) {\displaystyle f(x)} x k + 1 = x k − [ f ″ ( x k ) ] − 1 f ′ ( x k ) {\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})} ϕ ( y ) = f ( A y ) {\displaystyle \phi (y)=f(Ay)} A {\displaystyle A} y 0 = A − 1 x 0 {\displaystyle y_{0}=A^{-1}x_{0}} y k = A − 1 x k {\displaystyle y_{k}=A^{-1}x_{k}}

y k + 1 = y k − [ ϕ ″ ( y k ) ] − 1 ϕ ′ ( y k ) = y k − [ A T f ″ ( A y k ) A ] − 1 A T f ′ ( A y k ) = A − 1 x k − A − 1 [ f ″ ( x k ) ] − 1 f ′ ( x k ) = A − 1 x k + 1 {\displaystyle 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}} .

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

| ⟨ f ‴ ( x ) [ u ] v , v ⟩ | ≤ M ‖ u ‖ ‖ v ‖ 2 {\displaystyle |\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}} для всех u , v ∈ R n {\displaystyle u,v\in \mathbb {R} ^{n}}

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

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

| ⟨ f ‴ ( x ) [ u ] u , u ⟩ | ≤ M ⟨ f ″ ( x ) u , u ⟩ 3 / 2 {\displaystyle |\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}} .

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

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

Если и согласованы с константами и и , то согласовано с константой . f 1 {\displaystyle f_{1}} f 2 {\displaystyle f_{2}} M 1 {\displaystyle M_{1}} M 2 {\displaystyle M_{2}} α , β > 0 {\displaystyle \alpha ,\beta >0} α f 1 + β f 2 {\displaystyle \alpha f_{1}+\beta f_{2}} max ( α − 1 / 2 M 1 , β − 1 / 2 M 2 ) {\displaystyle \max(\alpha ^{-1/2}M_{1},\beta ^{-1/2}M_{2})}

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

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

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

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

Несингулярный гессиан

Если является самосогласованным и область определения не содержит прямых линий (бесконечна в обоих направлениях), то является невырожденной. f {\displaystyle f} f {\displaystyle f} f ″ {\displaystyle f''}

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

Приложения

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

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

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

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

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

Мы определяем декремент Ньютона для at как размер шага Ньютона в локальной норме, определяемой гессианом для at λ f ( x ) {\displaystyle \lambda _{f}(x)} f {\displaystyle f} x {\displaystyle x} [ f ″ ( x ) ] − 1 f ′ ( x ) {\displaystyle [f''(x)]^{-1}f'(x)} f {\displaystyle f} x {\displaystyle x}

λ f ( x ) = ⟨ f ″ ( x ) [ f ″ ( x ) ] − 1 f ′ ( x ) , [ f ″ ( x ) ] − 1 f ′ ( x ) ⟩ 1 / 2 = ⟨ [ f ″ ( x ) ] − 1 f ′ ( x ) , f ′ ( x ) ⟩ 1 / 2 {\displaystyle \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 {\displaystyle x} f {\displaystyle f} λ f ( x ) < 1 {\displaystyle \lambda _{f}(x)<1}

x + = x − [ f ″ ( x ) ] − 1 f ′ ( x ) {\displaystyle x_{+}=x-[f''(x)]^{-1}f'(x)}

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

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

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

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

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

ω ( λ f ( x ) ) ≤ f ( x ) − f ( x ∗ ) ≤ ω ∗ ( λ f ( x ) ) {\displaystyle \omega (\lambda _{f}(x))\leq f(x)-f(x^{*})\leq \omega _{*}(\lambda _{f}(x))}
ω ′ ( λ f ( x ) ) ≤ ‖ x − x ∗ ‖ x ≤ ω ∗ ′ ( λ f ( x ) ) {\displaystyle \omega '(\lambda _{f}(x))\leq \|x-x^{*}\|_{x}\leq \omega _{*}'(\lambda _{f}(x))}

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

ω ( t ) = t − log ⁡ ( 1 + t ) {\displaystyle \omega (t)=t-\log(1+t)}
ω ∗ ( t ) = − t − log ⁡ ( 1 − t ) {\displaystyle \omega _{*}(t)=-t-\log(1-t)}
‖ u ‖ x = ⟨ f ″ ( x ) u , u ⟩ 1 / 2 {\displaystyle \|u\|_{x}=\langle f''(x)u,u\rangle ^{1/2}}

Если мы начнем с метода Ньютона , то нам придется начать с использования затухающего метода Ньютона, определяемого как x 0 {\displaystyle x_{0}} λ f ( x 0 ) ≥ λ ¯ {\displaystyle \lambda _{f}(x_{0})\geq {\bar {\lambda }}}

x k + 1 = x k − 1 1 + λ f ( x k ) [ f ″ ( x k ) ] − 1 f ′ ( x k ) {\displaystyle x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})}

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

Ссылки

  1. ^ Немировски и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .
  2. ^ abcdefghij Аркадий Немировский (2004). «Методы полиномиального времени внутренних точек в выпуклом программировании».
  3. ^ Бойд, Стивен П.; Ванденберг, Ливен (2004). Выпуклая оптимизация (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Получено 15 октября 2011 г. .
  4. ^ Немировски и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .
  5. ^ Нестеров, Юрий; Немировский, Аркадий (январь 1994). Полиномиальные алгоритмы внутренних точек в выпуклом программировании (библиографические комментарии). Общество промышленной и прикладной математики. doi :10.1137/1.9781611970791.bm. ISBN 978-0-89871-319-0.
  6. ^ ab Нестеров, Юрий; Немировский, Аркадий (1994). Полиномиальные алгоритмы внутренних точек в выпуклом программировании . Исследования по прикладной и численной математике. Том 13. doi :10.1137/1.9781611970791. ISBN 978-0-89871-319-0. OCLC  29310677.[ нужна страница ]
  7. ^ Ю. НЕСТЕРОВ Е., Полиномиальные методы в линейном и квадратичном программировании, Известия АН СССР, Техническая кибернетика, № 3, 1988, стр. 324-326. (На русском языке.)
  8. ↑ Ю. Е. НЕСТЕРОВ, Полиномиальные итерационные методы в линейном и квадратичном программировании, Вопросы кибернетики, М., 1988, с. 102-125.
  9. ^ Ю.Е. Нестеров и А.С. Немировский, Самосогласованные функции и полиномиальные методы в выпуклом программировании, Технический отчет, Центральный экономико-математический институт АН СССР, Москва, СССР, 1989.
  10. ^ Нестеров, И︠Ю︡. Э. (декабрь 2013). Вводные лекции по выпуклой оптимизации: базовый курс. Бостон. ISBN 978-1-4419-8853-9. OCLC  883391994.{{cite book}}: CS1 maint: location missing publisher (link)
  11. ^ Сан, Тяньсяо; Тран-Динь, Куок (2018). «Обобщенные самосогласованные функции: рецепт для методов типа Ньютона». Математическое программирование : Предложение 6. arXiv : 1703.04599 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Self-concordant_function&oldid=1270459173#barrier"