On the convergence of the block nonlinear Gauss-Seidel method under convex constraints

By Luigi Grippo, Marco Sciandrone. Operations Research Letters, 2000

748 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/80bd6b05fd9cc616cb7eff66dcac9bba74367740

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis (2007, background): “The existence of accumulation points and the differentiability of the objective function in Equation (9) imply that the assumptions of Grippo and Sciandrone’s Corollary (Grippo and Sciandrone, 2000) are satisfied, so that we can establish that the two-block minimization process is convergent, in the”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “rms of f and diﬀerent variants of BCD). If f is diﬀerentiable, multi-convex or has separable non-smooth parts, then every limit point of the sequence generated by the proximal BCD is a critical point [16,50,60,61], but again, the nonsmooth terms cannot couple more than one block of variable. When th”
An introduction to continuous optimization for imaging (2016, background): “In general, block coordinate (or Gauss–Seidel) descent schemes can be implemented in many ways, and many generalizations involving non-smooth terms are proved to converge in the literature (Grippo and Sciandrone 2000, Auslender 1976, Attouch et al. 2013).”
On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays (2016, background): “The convergence of BM was established early for both convex and nonconvex problems, for example [19,10,31].”
Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework (2013, background): “The proof of this theorem for an arbitrary number of blocks is shown in Bertsekas [5], and the last statement regarding the two-block case is due to Grippo and Sciandrone [41].”
A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing (2015, background): “Therefore every feasible solution x ∈ X is regular, and the convergence of PPA is covered by BSUM.”
Parallel matrix factorization for low-rank tensor completion (2013, neutral): “The literature has work that analyzes the convergence of alternating minimization method for non-convex problems such as [4, 25, 29, 30].”
Joint distribution optimal transportation for domain adaptation (2017, neutral): “[27] on 2-block Gauss-Seidel methods directly applies.”
The Why and How of Nonnegative Matrix Factorization (2014, background): “ANLS is guaranteed to converge to a stationary point [59].”
A Signal Processing Perspective on Hyperspectral Unmixing: Insights from Remote Sensing (2014, background): “Specifically, we carry out the following heuristic: for , , ,k N1 f= determine an estimate IEEE SIGNAL PROCESSING MAGAZINE [74] JANUARY 2014 { [ ], , [ ]},arg maxb P f b x x L1s.t. conv b Fk k k2 2”
Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks (2014, background): “enerated by Algorithm 1 is a stationary point of Eq. 2. Proof: We omit the details since this can be easily derived following previous results about convergence in block coordinate descent approaches [28, 9]. 2 Algorithm 1 The global BCGD algorithm for inferring dynamic community Input: Graph matric”
Stochastic Joint Radio and Computational Resource Management for Multi-User Mobile-Edge Computing Systems (2017, methodology): “Since SP′2 is convex and its feasible region is a Cartesian product of those of {ptx,i (t)} and {αi (t)}, the alternating minimization procedure is guaranteed to converge to the global optimal solution, which is termed as the Gauss-Seidel method in literature [39].”
Fast Nonnegative Matrix Factorization: An Active-Set-Like Method and Comparisons (2011, methodology): “(ANLS-BPP) ANLS with the block principal pivoting method proposed in this paper 2.”
Outlier Detection for Text Data (2017, methodology): “quence generated by the block coordinate descent method as in Eq. (6). Then, every limit point of n x(i) o is a stationary point. The uniqueness of the minimum is not required for the case when m = 2 [15]. The proof of this theorem for an arbitrary number of blocks is shown in Bertsekas [3]. For a n”
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization (2012, neutral): “Alternatively, we can consider an alternating proximal minimization algorithm [12], in each iteration of which the following subproblem is solved (50) It is not hard to see that this subproblem always admits a unique solution, as the objective is a strictly .”
Local Convergence of the Alternating Least Squares Algorithm for Canonical Tensor Approximation (2012, background): “The great majority of the literature focuses on global properties of the iteration, like the existence of convergent subsequences and critical points, or the occurrence of swamps [3, 6, 7, 15, 17, 21, 22].”
Algorithms and applications for approximate nonnegative matrix factorization (2007, background): “Furthermore, it is known that an ALS algorithm that properly enforces nonnegativity, for example, through the nonnegative least squares (NNLS) algorithm of Lawson and Hanson (1995), will converge to a local minimum (Bertsekas, 1999; Grippo and Sciandrone, 2000; Lin, 2005b).”