Проксималды градиент әдісі - Proximal gradient method

Бұл мақалада жалпы тізімі бар сілтемелер, бірақ бұл негізінен тексерілмеген болып қалады, өйткені ол сәйкесінше жетіспейді кірістірілген дәйексөздер. Көмектесіңізші жақсарту осы мақала таныстыру дәлірек дәйексөздер. (Қараша 2013) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

Проксималды градиент әдістері дифференциалданбайтын шешуге қолданылатын проекцияның жалпыланған түрі дөңес оңтайландыру мәселелер.

Көптеген қызықты есептер форманың дөңес оңтайландыру мәселелері ретінде тұжырымдалуы мүмкін:

${ displaystyle operatorname {min} limits _ {x in mathbb {R} ^ {N}} sum _ {i = 1} ^ {n} f_ {i} (x)}$

қайда ${ displaystyle f_ {i}, i = 1, dots, n}$ болып табылады дөңес функциялар бастап анықталды ${ displaystyle f: mathbb {R} ^ {N} rightarrow mathbb {R}}$кейбір функциялар дифференциалданбайтын болса, бұл әдеттегі тегіс оңтайландыру әдістерін жоққа шығарадыТік түсу әдісі, конъюгаттық градиент әдісі Оның орнына проксималды градиент әдістерін қолдануға болады. Бұл әдістер функцияларды бөлу арқылы бөлінеді ${ displaystyle f_ {1}, ..., f_ {n}}$ оңай алынатын етіп жеке қолданылады іске асырылатын алгоритм.Олар деп аталады проксимальды өйткені әрқайсысы жоқ тегіс функция арасында ${ displaystyle f_ {1}, ..., f_ {n}}$ оның операторы арқылы қатысады. Шөгудің итеративті алгоритмі,^[1] жобаланған Landweber, жобаланған, ауыспалы проекциялар, көбейткіштердің ауыспалы-бағытты әдісі, ауыспалы плит Брегман проксимальды алгоритмдердің ерекше даналары.^[2] Жақын градиент әдістері теориясы үшін және қолдану тұрғысынан статистикалық оқыту теориясы, қараңыз оқудың проксималды градиенттік әдістері.

Белгілеулер және терминология

Келіңіздер ${ displaystyle mathbb {R} ^ {N}}$, ${ displaystyle N}$-өлшемді Евклид кеңістігі, функцияның домені болыңыз${ displaystyle f: mathbb {R} ^ {N} rightarrow (- infty, + infty]}$. Айталық ${ displaystyle C}$ - бос емес дөңес ішкі жиын ${ displaystyle mathbb {R} ^ {N}}$. Содан кейін, индикатор функциясы ${ displaystyle C}$ ретінде анықталады

${ displaystyle iota _ {C}: x mapsto { begin {case} 0 & { text {if}} x in C + infty & { text {if}} x notin C end {істер}}}$

${ displaystyle p}$-norm ретінде анықталады ( ${ displaystyle | cdot | _ {p}}$ )

${ displaystyle | x | _ {p} = (| x_ {1} | ^ {p} + | x_ {2} | ^ {p} + cdots + | x_ {N} | ^ {p}) ^ {1 / p}}$

Арақашықтық ${ displaystyle x in mathbb {R} ^ {N}}$ дейін ${ displaystyle C}$ ретінде анықталады

${ displaystyle D_ {C} (x) = min _ {y in C} | x-y | _ {2}}$

Егер ${ displaystyle C}$ жабық және дөңес, проекциясы ${ displaystyle x in mathbb {R} ^ {N}}$ үстінде ${ displaystyle C}$ ерекше нүкте${ displaystyle P_ {C} x in C}$ осындай ${ displaystyle D_ {C} (x) = | x-P_ {C} x | _ {2}}$.

The субдифференциалды туралы ${ displaystyle f}$ кезінде ${ displaystyle x}$ арқылы беріледі

${ displaystyle жарым-жартылай f (x) = {u in mathbb {R} ^ {N} mid forall y in mathbb {R} ^ {N}, (yx) ^ { mathrm {T }} u + f (x) leq f (y). }}$

Дөңес жиынтықтарға проекция (POCS)

Кеңінен қолданылатын дөңес оңтайландыру алгоритмдерінің бірі болып табылады дөңес жиынтықтарға проекциялар (POCS). Бұл алгоритм бірнеше дөңес шектеулерді қанағаттандыратын сигналды қалпына келтіру / синтездеу үшін қолданылады. Келіңіздер ${ displaystyle f_ {i}}$ бос емес жабық дөңес жиынтықтың индикаторлық функциясы болуы керек ${ displaystyle C_ {i}}$ шектеуді модельдеу. Бұл дөңес техникалық-экономикалық проблемаға дейін азаяды, бұл бізге барлық дөңес жиындардың қиылысында болатындай шешім табуды қажет етеді ${ displaystyle C_ {i}}$. POCS әдісінде әр жиын ${ displaystyle C_ {i}}$ оның құрамына кіреді проекциялау операторы ${ displaystyle P_ {C_ {i}}}$. Сондықтан әрқайсысында қайталану ${ displaystyle x}$ ретінде жаңартылады

${ displaystyle x_ {k + 1} = P_ {C_ {1}} P_ {C_ {2}} cdots P_ {C_ {n}} x_ {k}}$

Алайда мұндай проблемалардан тыс проекциялау операторлары сәйкес емес және олармен күресу үшін жалпы операторлар қажет. Дөңес проекциялау операторы туралы әртүрлі жалпылаудың ішінде жақындық операторлары басқа мақсаттарға ең қолайлы.

Анықтама

The жақындық операторы дөңес функцияның ${ displaystyle f}$ кезінде ${ displaystyle x}$ бірегей шешімі ретінде анықталады

${ Displaystyle operatorname {argmin} limits _ {y} { bigg (} f (y) + { frac {1} {2}} left | xy right | _ {2} ^ {2 } { bigg)}}$

және белгіленеді ${ displaystyle operatorname {prox} _ {f} (x)}$.

${ displaystyle operatorname {prox} _ {f} (x): mathbb {R} ^ {N} rightarrow mathbb {R} ^ {N}}$

Нақты жағдайда қай жерде екенін ескеріңіз ${ displaystyle f}$ индикатор функциясы болып табылады ${ displaystyle iota _ {C}}$ кейбір дөңес жиынтықтың ${ displaystyle C}$

${ displaystyle { begin {aligned} operatorname {prox} _ { iota _ {C}} (x) & = operatorname {argmin} limits _ {y} { begin {case} { frac {1 } {2}} left | xy right | _ {2} ^ {2} & { text {if}} y in C + infty & { text {if}} y notin C end {case}} & = operatorname {argmin} limits _ {y in C} { frac {1} {2}} left | xy right | _ {2} ^ { 2} & = P_ {C} (x) end {aligned}}}$

жақындау операторы шынымен проекциялау операторының қорытуы екенін көрсетеді.

Жақындық операторы ${ displaystyle f}$ қосуымен сипатталады

${ displaystyle p = operatorname {prox} _ {f} (x) Leftrightarrow xp in ішінара f (p) qquad ( forall (x, p) in mathbb {R} ^ {N} times mathbb {R} ^ {N})}$

Егер ${ displaystyle f}$ дифференциалданатын болса, жоғарыдағы теңдеу төмендейді

${ displaystyle p = operatorname {prox} _ {f} (x) Leftrightarrow xp = nabla f (p) quad ( forall (x, p) in mathbb {R} ^ {N} times) mathbb {R} ^ {N})}$

Мысалдар

Жақын градиент әдістерінің ерекше жағдайлары болып табылады

• Жоспарланған Landweber
• Айнымалы проекция
• Көбейткіштердің ауыспалы-бағытты әдісі

Сондай-ақ қараңыз

• Айнымалы проекция
• Дөңес оңтайландыру
• Frank-Wolfe алгоритмі
• Жақын оператор
• Оқытуға арналған градиенттің проксималды әдістері

Ескертулер

Әдебиеттер тізімі

• Рокафеллар, Р. (1970). Дөңес талдау. Принстон: Принстон университетінің баспасы.
• Комбеттер, Патрик Л.; Пескет, Жан-Кристоф (2011). Шпрингердің ғылым мен техникадағы кері есептерге арналған тұрақты алгоритмдері. 49. 185–212 бб.

Сыртқы сілтемелер

• Стивен Бойд пен Ливен Ванденбергтің кітабы, Дөңес оңтайландыру
• EE364a: дөңес оңтайландыру I және EE364b: Дөңес оңтайландыру II, Стэнфорд курсының басты беттері
• EE227A: Lieven Vandenberghe ноталары Дәріс 18
• ProximalOperators.jl: а Джулия жақын операторларды іске асыратын пакет.
• ProximalAlgorithms.jl: а Джулия проксималды градиент әдісін қоса проксималды операторға негізделген алгоритмдерді іске асыратын пакет.
• Proximity Operator репозиторийі: іске асырылған жақындық операторларының жиынтығы Matlab және Python.