Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization
Journal of Optimization Theory and ApplicationsPublished 1 June 2001
P. Tseng
Citations1,923
SJR quartileQ1
SJR score0.78
SNIP1.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Abstract We study the convergence properties of a (block) coordinate descent method applied to minimize a nondifferentiable (nonconvex) function f(x 1, . . . , x N ) with certain separability and regularity properties. Assuming that f is continuous on a compact level set, the subsequence convergence of the iterates to a stationary point is shown when either f is pseudoconvex in every pair of coordinate blocks from among N-1 coordinate blocks or f has at most one minimum in each of N-2 coordinate blocks. If f is quasiconvex and hemivariate in every coordinate block, then the assumptions of continuity of f and compactness of the level set may be relaxed further. These results are applied to derive new (and old) convergence results for the proximal minimization algorithm, an algorithm of Arimoto and Blahut, and an algorithm of Han. They are applied also to a problem of blind source separation.
Keywords
Computer ScienceMathematicsEngineering
Mathematics and Computers in SimulationLinear and nonlinear programming.
4,850 Citations1986
The linear and nonlinear programming is universally compatible with any devices to read and is available in the book collection an online access to it is set as public so you can download it instantly.
USSR Computational Mathematics and Mathematical PhysicsThe relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming
2,659 Citations1967L.M. Bregman
This method can be regarded as a generalization of the methods discussed in [1–4] and applied to the approximate solution of problems in linear and convex programming.
IEEE Transactions on Information TheoryComputation of channel capacity and rate-distortion functions
1,402 Citations1972Richard E. Blahut
A simple algorithm for computing channel capacity is suggested that consists of a mapping from the set of channel input probability vectors into itself such that the sequence of probability vectors generated by successive applications of the mapping converges to the vector that achieves the capacity of the given channel.
Mathematics of Operations ResearchAugmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
1,209 Citations1976R. T. Rockafellar
The theory of the proximal point algorithm for maximal monotone operators is applied to three algorithms for solving convex programs, one of which has not previously been formulated and is shown to have much the same convergence properties, but with some potential advantages.
IEEE Transactions on Information TheoryAn algorithm for computing the capacity of arbitrary discrete memoryless channels
849 Citations1972S. Arimoto
A systematic and iterative method of computing the capacity of arbitrary discrete memoryless channels is presented and a few inequalities that give upper and lower bounds on the capacity are derived.
Computers & Mathematics with ApplicationsParallel optimization: Theory, algorithms, and applications
830 Citations1998
Annals of Operations ResearchError bounds and convergence analysis of feasible descent methods: a general approach
440 Citations1993Zhi-Quan Luo, Paul Tseng
A general approach to analyzing the convergence and the rate of convergence of feasible descent methods that does not require any nondegeneracy assumption on the problem is surveyed and extended.
Mathematical ProgrammingOn search directions for minimization algorithms
319 Citations1973M. J. D. Powell
The relevance of differentiable functions of three variables, having the property that if they are treated by the minimization algorithm that searches along the coordinate directions in sequence, then the search path tends to a closed loop, is discussed.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Blind source separation by sparse decomposition</title>
203 Citations2000Michael Zibulevsky, Barak A. Pearlmutter
This work exploits the property of the sources to have a sparse representation in a corresponding signal dictionary, which provides faster and more robust computations, when there are an equal number of sources and mixtures.
Journal of Computational and Graphical StatisticsBlock Coordinate Relaxation Methods for Nonparametric Wavelet Denoising
170 Citations2000Sylvain Sardy, A. Gregory Bruce +1 more
This article investigates an alternative optimization approach based on block coordinate relaxation (BCR) for sets of basis functions that are the finite union of sets of orthonormal basis functions (e.g., wavelet packets), and shows that the BCR algorithm is globally convergent, and empirically, the B CR algorithm is faster than the IP algorithm for a variety of signal denoising problems.
Mathematical ProgrammingA new algorithm for the solution of multi-state dynamic programming problems
152 Citations1975H. R. Howson, N. G. F. Sancho
This paper presents a new algorithm for the solution of multi-state dynamic programming problems, referred to as the Progressive Optimality Algorithm, a method of successive approximation using a general two-stage solution that is computationally efficient and has minimal storage requirements.
Journal of the Society for Industrial and Applied MathematicsMinimizing Certain Convex Functions
103 Citations1963J. Warga
SIAM Journal on Control and OptimizationDual Ascent Methods for Problems with Strictly Convex Costs and Linear Constraints: A Unified Approach
91 Citations1990Paul Tseng
A block coordinate ascent method is presented for solving (P) that contains as special cases both dual coordinate ascent methods and dual gradient methods.
Mathematical ProgrammingDual coordinate ascent methods for non-strictly convex minimization
83 Citations1993Paul Tseng
A convergence result can be applied to sharpen the available convergence results for Han's methods and it is proved that the decomposition methods of Han and the method of multipliers may be viewed as special cases of this method.
IRE Transactions on Communications SystemsA Class of Decentralized Routing Algorithms Using Relaxation
69 Citations1977Thomas Stern
It is shown that a simple, convergent relaxation procedure can be used to "solve" the analog network, thereby yielding the optimal routing strategy, and the computational load compares favorably with other (centralized) methods, although further work is needed to obtain quantitive comparisons in specific cases.
Mathematics of Operations ResearchFree-Steering Relaxation Methods for Problems with Strictly Convex Costs and Linear Constraints
56 Citations1997Krzysztof C. Kiwiel
This work considers dual coordinate ascent methods for minimizing a strictly convex possibly nondifferentiable function subject to linear constraints and establishes their global convergence under weak conditions and a free-steering order of relaxation.
Journal of Optimization Theory and ApplicationsParallel successive overrelaxation methods for symmetric linear complementarity problems and linear programs
45 Citations1987O. L. Mangasarian, Renato De Leone
Management ScienceNote—A Note on the Cyclic Coordinate Ascent Method
32 Citations1970Norman Zadeh
It is proved that the cyclic coordinate ascent method will converge for pseudo Concave functions, as well as for strictly concave functions as was previously known.
Journal of Optimization Theory and ApplicationsSuccessive approximation technique for a class of large-scale NLP problems and its application to dynamic programming
6 Citations1989Z.-Q. Zuo, C.P. Wu
Two successive approximation techniques are presented for a class of large-scale nonlinear programming problems with decomposable constraints and aclass of high-dimensional discrete optimal control problems, respectively.