Fetching the paper…

Reading the bibliography…

2019

Relative Interior Rule in Block-Coordinate Minimization

Werner, Tomáš, Průša, Daniel

Original
PDF
Post on X

Understand

(Block-)coordinate minimization is an iterative optimization method which in every iteration finds a global minimum of the objective over a variable or a subset of variables, while keeping the remaining variables constant.

While for some problems, coordinate minimization converges to a global minimum (e.g., convex differentiable objective), for general (non-differentiable) convex problems this may not be the case.
Despite this drawback, (block-)coordinate minimization can be an acceptable option for large-scale non-differentiable convex problems; an example is methods to solve the linear programming relaxation of the discrete energy minimization problem (MAP inference in graphical models).
When block-coordinate minimization is applied to a general convex problem, in every iteration the minimizer over the current coordinate block need not be unique and therefore a single minimizer must be chosen.

Relative Interior Rule in Block-Coordinate Minimization · Around

Built on

Convex analysis
R. T. Rockafellar · 1970
Earlier work this paper cites.
A diffusion algorithm for decreasing the energy of the max-sum labeling problem
V. A. Kovalevsky and V. K. Koval · 1975
Earlier work this paper cites.
Nonlinear Programming
D. P. Bertsekas · 1999
Earlier work this paper cites.
Convergence of a block coordinate descent method for nondifferentiable minimization
P. Tseng · 2001
Earlier work this paper cites.

Similar

Fundamentals of Convex Analysis
J. Hiriart-Urruty and C. Lemaréchal · 2004
Cited alongside, same era.
Convergent tree-reweighted message passing for energy minimization
V. Kolmogorov · 2006
Cited alongside, same era.
A linear programming approach to max-sum problem: A review
T. Werner · 2007
Cited alongside, same era.
Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations
A. Globerson and T. Jaakkola · 2008
Cited alongside, same era.

Then

A comparative study of energy minimization methods for markov random fields with smoothness-based priors
R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, and C. Rother · 2008
Later among the works it cites.
Diffusion algorithms and structural recognition optimization problems
M. I. Schlesinger and K. Antoniuk · 2011
Later among the works it cites.
A comparative study of modern inference techniques for structured discrete energy minimization problems
J. H. Kappes, B. Andres, F. A. Hamprecht, C. Schnörr, S. Nowozin, D. Batra, S. Kim, B. X. Kausler, T. Kröger, J. Lellmann, N. Komodakis, B. Savchynskyy, and C. Rother · 2015
Later among the works it cites.
A new look at reweighted message passing
V. Kolmogorov · 2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…