Алгоритм Шамболя-Пока
Оптимизация алгоритма Primal-Dual для выпуклых задач

В математике алгоритм Шамболь-Пока — это алгоритм , используемый для решения задач выпуклой оптимизации . Он был представлен Антонином Шамболем и Томасом Поком [1] в 2011 году и с тех пор стал широко используемым методом в различных областях, включая обработку изображений , [2] [3] [4] компьютерное зрение , [5] и обработку сигналов . [6]

Алгоритм Шамболя-Пока специально разработан для эффективного решения задач выпуклой оптимизации, которые включают минимизацию негладкой функции стоимости, состоящей из члена точности данных и члена регуляризации. [1] Это типичная конфигурация, которая часто возникает в некорректных обратных задачах визуализации, таких как реконструкция изображений , [2] шумоподавление [3] и инрисовка . [4]

Алгоритм основан на прямо-двойственной формулировке, которая позволяет одновременно обновлять прямые и двойственные переменные. Используя проксимальный оператор , алгоритм Шамболя-Пока эффективно обрабатывает негладкие и невыпуклые термины регуляризации, такие как полная вариация , характерные для фреймворка визуализации. [1]

Постановка проблемы

Пусть будут два действительных векторных пространства, снабженных скалярным произведением и нормой . До сих пор функция называется простой , если ее проксимальный оператор имеет замкнутое представление или может быть точно вычислен, для , [1] где упоминается Х , И {\displaystyle {\mathcal {X}},{\mathcal {Y}}} ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot,\cdot \rangle} ‖ ⋅ ‖ = ⟨ ⋅ , ⋅ ⟩ 1 2 {\displaystyle \lVert \,\cdot \,\rVert =\langle \cdot,\cdot \rangle ^{\frac {1}{2}}} Ф {\displaystyle F} прокси τ Ф {\displaystyle {\text{prox}}_{\tau F}} τ > 0 {\displaystyle \тау >0} прокси τ Ф {\displaystyle {\text{prox}}_{\tau F}}

х = прокси τ Ф ( х ~ ) = арг  мин х ′ ∈ Х { ‖ х ′ − х ~ ‖ 2 2 τ + Ф ( х ′ ) } {\displaystyle x={\text{prox}}_{\tau F}({\tilde {x}})={\text{arg }}\min _{x'\in {\mathcal {X}}}\left\{{\frac {\lVert x'-{\tilde {x}}\rVert ^{2}}{2\tau }}+F(x')\right\}}

Рассмотрим следующую ограниченную прямую задачу: [1]

мин х ∈ Х Ф ( К х ) + Г ( х ) {\displaystyle \min _{x\in {\mathcal {X}}}F(Kx)+G(x)}

где — ограниченный линейный оператор , являются выпуклыми , полунепрерывными снизу и простыми. [1] К : Х → И {\displaystyle K:{\mathcal {X}}\rightarrow {\mathcal {Y}}} Ф : И → [ 0 , + ∞ ) , Г : Х → [ 0 , + ∞ ) {\displaystyle F:{\mathcal {Y}}\rightarrow [0,+\infty ),G:{\mathcal {X}}\rightarrow [0,+\infty )}

Задача минимизации имеет свою двойственную соответствующую задачу [1]

макс у ∈ И − ( Г ∗ ( − К ∗ у ) + Ф ∗ ( у ) ) {\displaystyle \max _{y\in {\mathcal {Y}}}-\left(G^{*}(-K^{*}y)+F^{*}(y)\right)}

где и являются двойственным отображением и , соответственно. [1] Ф ∗ , Г ∗ {\displaystyle F^{*},G^{*}} К ∗ {\displaystyle К^{*}} Ф , Г {\displaystyle F,G} К {\displaystyle К}

Предположим, что основная и двойственная задачи имеют по крайней мере решение , это означает, что они удовлетворяют [7] ( х ^ , у ^ ) ∈ Х × И {\displaystyle ({\hat {x}},{\hat {y}})\in {\mathcal {X}}\times {\mathcal {Y}}}

К х ^ ∈ ∂ Ф ∗ ( у ^ ) − ( К ∗ у ^ ) ∈ ∂ Г ( х ^ ) {\displaystyle {\begin{align}K{\hat {x}}&\in \partial F^{*}({\hat {y}})\\-(K^{*}{\hat {y}})&\in \partial G({\hat {x}})\end{align}}}

где и — субградиенты выпуклых функций и соответственно. [7] ∂ Ф ∗ {\displaystyle \partial F^{*}} ∂ Г {\displaystyle \partial G} Ф ∗ {\displaystyle F^{*}} Г {\displaystyle G}

Алгоритм Шамболя-Пока решает так называемую задачу седловой точки [1]

мин х ∈ Х макс у ∈ И ⟨ К х , у ⟩ + Г ( х ) − Ф ∗ ( у ) {\displaystyle \min _{x\in {\mathcal {X}}} \max _{y\in {\mathcal {Y}}}\langle Kx,y\rangle +G(x)-F^{* }(у)}

что является прямо-двойственной формулировкой нелинейных прямой и двойственной проблем, указанных ранее. [1]

Алгоритм

Алгоритм Шамболя-Пока в первую очередь включает в себя итеративное чередование между возрастанием в двойственной переменной и убыванием в основной переменной с использованием градиентного подхода с размерами шагов и соответственно, чтобы одновременно решить основную и двойственную задачу. [2] Кроме того, для основной переменной с параметром используется метод сверхрелаксации . [1] у {\displaystyle у} х {\displaystyle x} σ {\displaystyle \сигма} τ {\displaystyle \тау} θ {\displaystyle \тета} 

Алгоритм Алгоритм Шамболя-Пока Входные данные: и набор ,     Ф , Г , К , τ , σ > 0 ,  θ ∈ [ 0 , 1 ] ,  (  х  0   ,  у  0   ) ∈   Х   ×   И     {\displaystyle F,G,K,\tau ,\sigma >0,\,\theta \in [0,1],\,(x^{0},y^{0})\in {\mathcal {X}}\times {\mathcal {Y}}}        х ¯    0   =  х  0     {\displaystyle {\overline {x}}^{0}=x^{0}}  критерий останова .
    к ← 0   {\displaystyle k\leftarrow 0} делать пока  критерий остановки  не удовлетворен  конец делать     у  н + 1   ←   прокси   σ  Ф  ∗      (   у  н   + σ К    х ¯    н    )    {\displaystyle y^{n+1}\leftarrow {\text{prox}}_{\sigma F^{*}}\left(y^{n}+\sigma K{\overline {x}}^{n}\right)}       х  н + 1   ←   прокси   τ Г    (   х  н   − τ  К  ∗    у  н + 1    )    {\displaystyle x^{n+1}\leftarrow {\text{prox}}_{\tau G}\left(x^{n}-\tau K^{*}y^{n+1}\right)}         х ¯    н + 1   ←  х  н + 1   + θ  (   х  н + 1   −  х  н    )    {\displaystyle {\overline {x}}^{n+1}\leftarrow x^{n+1}+\theta \left(x^{n+1}-x^{n}\right)}      к ← к + 1   {\displaystyle k\leftarrow k+1}
  • "←" обозначает назначение . Например, " largest ← item " означает, что значение largest изменяется на значение item .
  • « return » завершает алгоритм и выводит следующее значение.

Шамболь и Пок доказали [1] , что алгоритм сходится, если и , последовательно и с как скоростью сходимости для прямо-двойственного зазора. Это было расширено С. Банертом и др. [8] для выполнения, когда и . θ = 1 {\displaystyle \тета =1} τ σ ‖ К ‖ 2 ≤ 1 {\displaystyle \tau \sigma \lВерт К\rВерт ^{2}\leq 1} О ( 1 / Н ) {\displaystyle {\mathcal {O}}(1/N)} θ > 1 / 2 {\displaystyle \тета >1/2} τ σ ‖ К ‖ 2 < 4 / ( 1 + 2 θ ) {\displaystyle \tau \sigma \lВерт К\rВерт ^{2}<4/(1+2\theta )}

Полунеявный метод Эрроу-Гурвица [9] совпадает с частным выбором в алгоритме Шамболя-Пока. [1] θ = 0 {\displaystyle \тета =0}

Ускорение

Существуют особые случаи, в которых скорость сходимости имеет теоретическую скорость. [1] Фактически, если , соответственно , равномерно выпукло, то , соответственно , имеет непрерывный по Липшицу градиент. Тогда скорость сходимости можно улучшить до , внеся небольшие изменения в алгоритм Шамболя-Пока. Это приводит к ускоренной версии метода и заключается в итеративном выборе , а также , вместо фиксации этих значений. [1] Г {\displaystyle G} Ф ∗ {\displaystyle F^{*}} Г ∗ {\displaystyle G^{*}} Ф {\displaystyle F} О ( 1 / Н 2 ) {\displaystyle {\mathcal {O}}(1/N^{2})} τ н , σ н {\displaystyle \тау _{n},\сигма _{n}} θ н {\displaystyle \theta _{n}}

В случае равномерной выпуклости с константой равномерной выпуклости модифицированный алгоритм принимает вид [1] Г {\displaystyle G} γ > 0 {\displaystyle \гамма >0} 

Алгоритм Ускоренный алгоритм Шамболя-Пока Входные данные: такой, что и задано ,     Ф , Г ,  τ  0   ,  σ  0   > 0   {\displaystyle F,G,\tau _{0},\sigma _{0}>0}      τ  0    σ  0    Л  2   ≤ 1 ,  (  х  0   ,  у  0   ) ∈   Х   ×   И     {\displaystyle \tau _{0}\sigma _{0}L^{2}\leq 1,\,(x^{0},y^{0})\in {\mathcal {X}}\times {\mathcal {Y}}}        х ¯    0   =  х  0   .   {\displaystyle {\overline {x}}^{0}=x^{0}.}  критерий останова .
    к ← 0   {\displaystyle k\leftarrow 0} делать пока  критерий остановки  не удовлетворен  конец делать     у  н + 1   ←   прокси    σ  н    Ф  ∗      (   у  н   +  σ  н   К    х ¯    н    )    {\displaystyle y^{n+1}\leftarrow {\text{prox}}_{\sigma _{n}F^{*}}\left(y^{n}+\sigma _{n}K{\overline {x}}^{n}\right)}       х  н + 1   ←   прокси    τ  н   Г    (   х  н   −  τ  н    К  ∗    у  н + 1    )    {\displaystyle x^{n+1}\leftarrow {\text{prox}}_{\tau _{n}G}\left(x^{n}-\tau _{n}K^{*}y^{n+1}\right)}       θ  н   ←   1  1 + 2 γ  τ  н        {\displaystyle \theta _{n}\leftarrow {\frac {1}{\sqrt {1+2\gamma \tau _{n}}}}}       τ  n + 1   ←  θ  n    τ  n     {\displaystyle \tau _{n+1}\leftarrow \theta _{n}\tau _{n}}       σ  n + 1   ←    σ  n    θ  n       {\displaystyle \sigma _{n+1}\leftarrow {\frac {\sigma _{n}}{\theta _{n}}}}         x ¯    n + 1   ←  x  n + 1   +  θ  n    (   x  n + 1   −  x  n    )    {\displaystyle {\overline {x}}^{n+1}\leftarrow x^{n+1}+\theta _{n}\left(x^{n+1}-x^{n}\right)}      k ← k + 1   {\displaystyle k\leftarrow k+1}
  • "←" обозначает назначение . Например, " largest ← item " означает, что значение largest изменяется на значение item .
  • « return » завершает алгоритм и выводит следующее значение.

Более того, сходимость алгоритма замедляется, когда , норма оператора , не может быть легко оценена или может быть очень большой. Выбирая соответствующие предобуславливатели и , модифицируя проксимальный оператор с введением индуцированной нормы через операторы и , сходимость предлагаемого предобуславливающего алгоритма будет обеспечена. [10] L {\displaystyle L} K {\displaystyle K} T {\displaystyle T} Σ {\displaystyle \Sigma } T {\displaystyle T} Σ {\displaystyle \Sigma }

Приложение

Пример шумоподавления

Типичное применение этого алгоритма — в структуре шумоподавления изображений , основанной на общей вариации. [3] Он работает на концепции, что сигналы, содержащие избыточные и потенциально ошибочные детали, демонстрируют высокую общую вариацию, которая представляет собой интеграл градиента абсолютного значения изображения. [3] Придерживаясь этого принципа, процесс направлен на уменьшение общей вариации сигнала, сохраняя его сходство с исходным сигналом, эффективно устраняя нежелательные детали, сохраняя при этом такие важные особенности, как края. В классической двумерной дискретной настройке [11] рассмотрим , где элемент представляет собой изображение со значениями пикселей, размещенными в декартовой сетке . [1] X = R N M {\displaystyle {\mathcal {X}}=\mathbb {R} ^{NM}} u ∈ X {\displaystyle u\in {\mathcal {X}}} N × M {\displaystyle N\times M}

Определим скалярное произведение как [1] X {\displaystyle {\mathcal {X}}}

⟨ u , v ⟩ X = ∑ i , j u i , j v i , j , u , v ∈ X {\displaystyle \langle u,v\rangle _{\mathcal {X}}=\sum _{i,j}u_{i,j}v_{i,j},\quad u,v\in {\mathcal {X}}}

что индуцирует норму на , обозначаемую как . [1] L 2 {\displaystyle L^{2}} X {\displaystyle {\mathcal {X}}} ‖ ⋅ ‖ 2 {\displaystyle \lVert \,\cdot \,\rVert _{2}}

Следовательно, градиент вычисляется с помощью стандартных конечных разностей , u {\displaystyle u}

( ∇ u ) i , j = ( ( ∇ u ) i , j 1 ( ∇ u ) i , j 2 ) {\displaystyle \left(\nabla u\right)_{i,j}=\left({\begin{aligned}\left(\nabla u\right)_{i,j}^{1}\\\left(\nabla u\right)_{i,j}^{2}\end{aligned}}\right)}

который является элементом пространства , где [1] Y = X × X {\displaystyle {\mathcal {Y}}={\mathcal {X}}\times {\mathcal {X}}}

( ∇ u ) i , j 1 = { u i + 1 , j − u i , j h  if  i < M 0  if  i = M , ( ∇ u ) i , j 2 = { u i , j + 1 − u i , j h  if  j < N 0  if  j = N {\displaystyle {\begin{aligned}&\left(\nabla u\right)_{i,j}^{1}=\left\{{\begin{aligned}&{\frac {u_{i+1,j}-u_{i,j}}{h}}&{\text{ if }}i<M\\&0&{\text{ if }}i=M\end{aligned}}\right.,\\&\left(\nabla u\right)_{i,j}^{2}=\left\{{\begin{aligned}&{\frac {u_{i,j+1}-u_{i,j}}{h}}&{\text{ if }}j<N\\&0&{\text{ if }}j=N\end{aligned}}\right.\end{aligned}}}

На основе нормы определяется следующее [1]: Y {\displaystyle {\mathcal {Y}}} L 1 − {\displaystyle L^{1}-}

‖ p ‖ 1 = ∑ i , j ( p i , j 1 ) 2 + ( p i , j 2 ) 2 , p ∈ Y . {\displaystyle \lVert p\rVert _{1}=\sum _{i,j}{\sqrt {\left(p_{i,j}^{1}\right)^{2}+\left(p_{i,j}^{2}\right)^{2}}},\quad p\in {\mathcal {Y}}.}

Тогда основная задача модели ROF , предложенной Рудином, Ошером и Фатеми [12] , задается формулой [1]

h 2 min u ∈ X ‖ ∇ u ‖ 1 + λ 2 ‖ u − g ‖ 2 2 {\displaystyle h^{2}\min _{u\in {\mathcal {X}}}\lVert \nabla u\rVert _{1}+{\frac {\lambda }{2}}\lVert u-g\rVert _{2}^{2}}

где — неизвестное решение и заданные зашумленные данные, вместо этого описывает компромисс между регуляризацией и подгонкой данных. [1] u ∈ X {\displaystyle u\in {\mathcal {X}}} g ∈ X {\displaystyle g\in {\mathcal {X}}} λ {\displaystyle \lambda }

Прямо-двойственная формулировка задачи ROF формулируется следующим образом [1]

min u ∈ X max p ∈ Y − ⟨ u , div p ⟩ X + λ 2 ‖ u − g ‖ 2 2 − δ P ( p ) {\displaystyle \min _{u\in {\mathcal {X}}}\max _{p\in {\mathcal {Y}}}-\langle u,{\text{div}}\,p\rangle _{\mathcal {X}}+{\frac {\lambda }{2}}\lVert u-g\rVert _{2}^{2}-\delta _{P}(p)}

где индикаторная функция определяется как [1]

δ P ( p ) = { 0 , if  p ∈ P + ∞ , if  p ∉ P {\displaystyle \delta _{P}(p)=\left\{{\begin{aligned}&0,&{\text{if }}p\in P\\&+\infty ,&{\text{if }}p\notin P\end{aligned}}\right.}

на выпуклом множестве , которое можно рассматривать как унитарные шары относительно определенной нормы на . [1] P = { p ∈ Y : max i , j ( p i , j 1 ) 2 + ( p i , j 2 ) 2 ≤ 1 } , {\displaystyle P=\left\{p\in {\mathcal {Y}}\,:\,\max _{i,j}{\sqrt {\left(p_{i,j}^{1}\right)^{2}+\left(p_{i,j}^{2}\right)^{2}}}\leq 1\right\},} L ∞ {\displaystyle L^{\infty }} Y {\displaystyle {\mathcal {Y}}}


Обратите внимание, что функции, задействованные в указанной прямо-двойственной формулировке, просты, поскольку их проксимальный оператор может быть легко вычислен [1]. Проблема шумоподавления полной дисперсии изображения может быть также решена с помощью других алгоритмов [13], таких как метод переменного направления множителей (ADMM), [14] проецируемый (суб)градиент [15] или быстрое итеративное пороговое сжатие. [16] p = prox σ F ∗ ( p ~ ) ⟺ p i , j = p ~ i , j max { 1 , | p ~ i , j | } u = prox τ G ( u ~ ) ⟺ u i , j = u ~ i , j + τ λ g i , j 1 + τ λ {\displaystyle {\begin{aligned}p&={\text{prox}}_{\sigma F^{*}}({\tilde {p}})&\iff p_{i,j}&={\frac {{\tilde {p}}_{i,j}}{\max\{1,|{\tilde {p}}_{i,j}|\}}}\\u&={\text{prox}}_{\tau G}({\tilde {u}})&\iff u_{i,j}&={\frac {{\tilde {u}}_{i,j}+\tau \lambda g_{i,j}}{1+\tau \lambda }}\end{aligned}}}

Выполнение

  • Пакет Manopt.jl [17] реализует алгоритм на языке Julia
  • Габриэль Пейре реализует алгоритм в MATLAB , [примечание 1] Julia, R и Python [18]
  • В библиотеке операторной дискретизации (ODL) [19] , представляющей собой библиотеку Python для обратных задач, chambolle_pock_solverреализован этот метод.

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

Примечания

  1. ^ Эти коды были использованы для получения изображений в статье.

Ссылки

  1. ^ abcdefghijklmnopqrstu vwxyz aa Шамболь, Антонин; Пок, Томас (2011-05-01). "Первоочередной прямо-двойственный алгоритм для выпуклых задач с приложениями к визуализации". Журнал математической визуализации и визуализации . 40 (1): 120–145. doi :10.1007/s10851-010-0251-1. ISSN  1573-7683. S2CID  207175707.
  2. ^ abc Sidky, Emil Y; Jørgensen, Jakob H; Pan, Xiaochuan (2012-05-21). "Прототипирование задачи выпуклой оптимизации для реконструкции изображений в компьютерной томографии с помощью алгоритма Шамболя–Пока". Physics in Medicine and Biology . 57 (10): 3065–3091. arXiv : 1111.5632 . Bibcode :2012PMB....57.3065S. doi :10.1088/0031-9155/57/10/3065. ISSN  0031-9155. PMC 3370658 . PMID  22538474. 
  3. ^ abcd Fang, Faming; Li, Fang; Zeng, Tieyong (2014-03-13). «Очистка и шумоподавление отдельных изображений: быстрый вариационный подход». SIAM Journal on Imaging Sciences . 7 (2): 969–996. doi :10.1137/130919696. ISSN  1936-4954.
  4. ^ ab Allag, A.; Benammar, A.; Drai, R.; Boutkedjirt, T. (2019-07-01). «Реконструкция томографического изображения в случае ограниченного числа рентгеновских проекций с использованием синограммной инкартировки». Российский журнал неразрушающего контроля . 55 (7): 542–548. doi :10.1134/S1061830919070027. ISSN  1608-3385. S2CID  203437503.
  5. ^ Pock, Thomas; Cremers, Daniel; Bischof, Horst; Chambolle, Antonin (2009). "Алгоритм минимизации функционала Мамфорда-Шаха". 2009 IEEE 12-я Международная конференция по компьютерному зрению . С. 1133–1140. doi :10.1109/ICCV.2009.5459348. ISBN 978-1-4244-4420-5. S2CID  15991312.
  6. ^ "A Generic Proximal Algorithm for Convex Optimization—Application to Total Variation Minimization". IEEE Signal Processing Letters . 21 (8): 985–989. 2014. Bibcode :2014ISPL...21..985.. doi :10.1109/LSP.2014.2322123. ISSN  1070-9908. S2CID  8976837.
  7. ^ ab Ekeland, Ivar; Témam, Roger (1999). Выпуклый анализ и вариационные задачи. Общество промышленной и прикладной математики. стр. 61. doi :10.1137/1.9781611971088. ISBN 978-0-89871-450-0.
  8. ^ Банерт, Себастьян; Упадхьяя, Ману; Гисельссон, Понтус (2023). «Метод Шамболя-Пока сходится слабо с и ». arXiv : 2309.03998 [math.OC]. θ > 1 / 2 {\displaystyle \theta >1/2} τ σ ‖ L ‖ 2 < 4 / ( 1 + 2 θ ) {\displaystyle \tau \sigma \lVert L\rVert ^{2}<4/(1+2\theta )}
  9. ^ Uzawa, H. (1958). "Итеративные методы вогнутого программирования". В Arrow, KJ; Hurwicz, L.; Uzawa, H. (ред.). Исследования по линейному и нелинейному программированию . Stanford University Press.
  10. ^ Pock, Thomas; Chambolle, Antonin (2011-11-06). "Диагональное предварительное обуславливание для прямо-двойственных алгоритмов первого порядка в выпуклой оптимизации". Международная конференция по компьютерному зрению 2011 г. . стр. 1762–1769. doi :10.1109/ICCV.2011.6126441. ISBN 978-1-4577-1102-2. S2CID  17485166.
  11. ^ Шамболь, Антонин (2004-01-01). «Алгоритм для минимизации общей вариации и его применение». Журнал математической визуализации и зрения . 20 (1): 89–97. doi :10.1023/B:JMIV.0000011325.36760.1e. ISSN  1573-7683. S2CID  207622122.
  12. ^ Гетройер, Паскаль (2012). «Полное вариационное шумоподавление Рудина–Ошера–Фатеми с использованием расщепленного Брегмана» (PDF) .
  13. ^ Эссер, Эрни; Чжан, Сяоцюнь; Чан, Тони Ф. (2010). «Общая структура для класса первично-двойственных алгоритмов первого порядка для выпуклой оптимизации в науке о визуализации». Журнал SIAM по наукам о визуализации . 3 (4): 1015–1046. doi :10.1137/09076934X. ISSN  1936-4954.
  14. ^ Lions, PL; Mercier, B. (1979). «Алгоритмы разделения для суммы двух нелинейных операторов». Журнал SIAM по численному анализу . 16 (6): 964–979. Bibcode : 1979SJNA...16..964L. doi : 10.1137/0716071. ISSN  0036-1429. JSTOR  2156649.
  15. ^ Бек, Амир; Тебулл, Марк (2009). «Быстрый итеративный алгоритм порогового сжатия для линейных обратных задач». Журнал SIAM по наукам о визуализации . 2 (1): 183–202. doi :10.1137/080716542. ISSN  1936-4954. S2CID  3072879.
  16. ^ Несторов, Ю.Е. "Метод решения задачи выпуклого программирования со скоростью сходимости O ( 1 k 2 ) {\displaystyle O{\bigl (}{\frac {1}{k^{2}}}{\bigr )}} ". Докл. АН СССР . 269 (3): 543–547.
  17. ^ "Chambolle-Pock · Manopt.jl". docs.juliahub.com . Получено 2023-07-07 .
  18. ^ «Численные туры — числовой тур по науке о данных». www.numerical-tours.com . Получено 07.07.2023 .
  19. ^ "Решатель Шамболь-Пока — документация odl 0.6.1.dev0". odl.readthedocs.io . Получено 2023-07-07 .

Дальнейшее чтение

  • Бойд, Стивен; Ванденберг, Ливен (2004). Выпуклая оптимизация (PDF) . Cambridge University Press.
  • Райт, Стивен (1997). Методы первично-двойной внутренней точки . Филадельфия, Пенсильвания: SIAM. ISBN 978-0-89871-382-4.
  • Нокедаль, Хорхе; Стивен Райт (1999). Численная оптимизация . Нью-Йорк, Нью-Йорк: Springer. ISBN 978-0-387-98793-4.
  • EE364b, домашняя страница курса Стэнфорда.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Chambolle-Pock_algorithm&oldid=1188081309"