Bregman method (original) (raw)
The Bregman method is an iterative algorithm to solve certain convex optimization problems involving regularization. The original version is due to Lev M. Bregman, who published it in 1967. The algorithm is a accessing constraint functions one by one and the method is particularly suited for large optimization problems where constraints can be efficiently enumerated. The algorithm works particularly well for regularizers such as the norm, where it converges very quickly because of an error cancellation effect.
| Property | Value |
|---|---|
| dbo:abstract | The Bregman method is an iterative algorithm to solve certain convex optimization problems involving regularization. The original version is due to Lev M. Bregman, who published it in 1967. The algorithm is a accessing constraint functions one by one and the method is particularly suited for large optimization problems where constraints can be efficiently enumerated. The algorithm works particularly well for regularizers such as the norm, where it converges very quickly because of an error cancellation effect. (en) Метод Брэгмана — это итеративный алгоритм решения некоторых задач выпуклого программирования. Алгоритм поочерёдно просматривает одну за другой и метод особенно подходит для задач оптимизации большого размера, в которых можно эффективно перенумеровать ограничения. Исходная версия алгоритма принадлежит Льву Мееровичу Брэгману. Алгоритм начинает с пары наборов переменных прямой и двойственной задач. Затем для каждого ограничения находится в множество допустимых решений, обновляя двойственные переменные ограничений и все переменные прямой задачи, для которых есть ненулевые коэффициенты в градиенте функций ограничений. В случае, когда целевая функция строго выпукла и все функции ограничений выпуклы, итеративные проекции сходятся к оптимальной паре переменных прямой и двойственной задач. Метод имеет связь с методом множителей Лагранжа и двойственным методом наискорейшего подъёма (англ. dual ascent). Существует множество обобщений метода. Одним из недостатков метода является то, что метод доказуемо сходится только если целевая функция строго выпукла. Если это нельзя гарантировать, как в случае задач линейного программирования или для нестрого выпуклых задач квадратичного программирования, нужно разрабатывать дополнительные методы, такие как метод проксимального градиента. (ru) |
| dbo:wikiPageID | 21410975 (xsd:integer) |
| dbo:wikiPageLength | 11520 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121553578 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Radar dbr:Lev_M._Bregman dbr:Limited-memory_BFGS dbr:Complex_number dbr:Convex_optimization dbr:Wirtinger_derivatives dbr:Gradient_descent dbr:Subderivative dbr:Basis_pursuit dbr:Magnetic_resonance_imaging dbr:Structural_risk_minimization dbr:Compressed_sensing dbr:Matrix_completion dbc:Optimization_algorithms_and_methods dbr:Least_absolute_deviations dbc:Convex_optimization dbr:Bregman_divergence dbr:Regularization_(mathematics) dbr:Image_denoising dbr:Total_variation_denoising dbr:Proximal_gradient_method dbr:Iterative_algorithm dbr:Linear_program dbr:Hyperspectral_image dbr:Constraint_function dbr:Image_deblurring dbr:Barzilai-Borwein dbr:Dual_ascent_method dbr:Method_of_multipliers dbr:Nesterov_method dbr:Row-action_method |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Clarify dbt:More_citations_needed dbt:Multiple_issues dbt:Reflist dbt:Technical |
| dct:subject | dbc:Optimization_algorithms_and_methods dbc:Convex_optimization |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software |
| rdfs:comment | The Bregman method is an iterative algorithm to solve certain convex optimization problems involving regularization. The original version is due to Lev M. Bregman, who published it in 1967. The algorithm is a accessing constraint functions one by one and the method is particularly suited for large optimization problems where constraints can be efficiently enumerated. The algorithm works particularly well for regularizers such as the norm, where it converges very quickly because of an error cancellation effect. (en) Метод Брэгмана — это итеративный алгоритм решения некоторых задач выпуклого программирования. Алгоритм поочерёдно просматривает одну за другой и метод особенно подходит для задач оптимизации большого размера, в которых можно эффективно перенумеровать ограничения. Исходная версия алгоритма принадлежит Льву Мееровичу Брэгману. Метод имеет связь с методом множителей Лагранжа и двойственным методом наискорейшего подъёма (англ. dual ascent). Существует множество обобщений метода. (ru) |
| rdfs:label | Bregman method (en) Метод Брэгмана (ru) |
| owl:sameAs | freebase:Bregman method wikidata:Bregman method dbpedia-ru:Bregman method https://global.dbpedia.org/id/4bY7i |
| prov:wasDerivedFrom | wikipedia-en:Bregman_method?oldid=1121553578&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Bregman_method |
| is dbo:wikiPageDisambiguates of | dbr:Bregman |
| is dbo:wikiPageWikiLink of | dbr:Bregman_Lagrangian dbr:List_of_numerical_analysis_topics dbr:Stanley_Osher dbr:Bregman dbr:Sequential_minimal_optimization dbr:Total_variation_denoising dbr:Proximal_gradient_method |
| is foaf:primaryTopic of | wikipedia-en:Bregman_method |