检索结果-内蒙古大学图书馆

On the convergence of inexact block coordinate descent methods for constrained optimization

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第2期231卷 274-281页

作者： Cassioli, A. Di Lorenzo, D. Sciandrone, M. Univ Florence Dipartimento Ingn Informaz I-50145 Florence Italy

We consider the problem of minimizing a smooth function over a feasible set defined as the Cartesian product of convex compact sets. We assume that the dimension of each factor set is huge, so we are interested in studying inexact block coordinate descent methods (possibly combined with column generation strategies). We define a general decomposition framework where different line search based methods can be embedded, and we state global convergence results. Specific decomposition methods based on gradient projection and Frank-Wolfe algorithms are derived from the proposed framework. The numerical results of computational experiments performed on network assignment problems are reported. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Nonlinear programming block coordinate descent methods Inexact decomposition methods Gradient projection Frank-Wolfe

来源：评论

学校读者我要写书评

暂无评论

An almost cyclic 2-coordinate descent method for singly linearly constrained problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2019年第2期73卷 411-452页

作者： Cristofari, Andrea Univ Padua Dept Math Via Trieste 63 I-35121 Padua Italy

A block decomposition method is proposed for minimizing a (possibly non-convex) continuously differentiable function subject to one linear equality constraint and simple bounds on the variables. The proposed method iteratively selects a pair of coordinates according to an almost cyclic strategy that does not use first-order information, allowing us not to compute the whole gradient of the objective function during the algorithm. Using first-order search directions to update each pair of coordinates, global convergence to stationary points is established for different choices of the stepsize under an appropriate assumption on the level set. In particular, both inexact and exact line search strategies are analyzed. Further, linear convergence rate is proved under standard additional assumptions. Numerical results are finally provided to show the effectiveness of the proposed method.

关键词： block coordinate descent methods block decomposition methods Linear convergence rate SVM

来源：评论

学校读者我要写书评

暂无评论

Serial and parallel approaches for image segmentation by numerical minimization of a second-order functional

引用

APPLIED MATHEMATICS AND COMPUTATION 2018年 318卷 153-175页

作者： Zanella, R. Porta, F. Ruggiero, V. Zanetti, M. Univ Ferrara Math & Comp Sci Dept Ferrara Italy Univ Trento Informat & Commun Technol Dept Trento Italy

Because of its attractive features, second order segmentation has shown to be a promising tool in remote sensing. A known drawback about its implementation is computational complexity, above all for large set of data. Recently in Zanetti et al. [1], an efficient version of the block-coordinate descent algorithm (BCDA) has been proposed for the minimization of a second order elliptic approximation of the Blake-Zissermann functional. Although the parallelization of linear algebra operations is expected to increase the performance of BCDA when addressing the segmentation of large-size gridded data (e.g., full-scene images or Digital Surface Models (DSMs)), numerical evidence shows that this is not sufficient to get significant reduction of computational time. Therefore a novel approach is proposed which exploits a decomposition technique of the image domain into tiles. The solution can be computed by applying BCDA on each tile in parallel way and combining the partial results corresponding to the different blocks of variables through a proper interconnection rule. We prove that this parallel method (OPARBCDA) generates a sequence of iterates which converges to a critical point of the functional on the level set devised by the starting point. Furthermore, we show that the parallel method can be efficiently implemented even in a commodity multicore CPU. Numerical results are provided to evaluate the efficiency of the parallel scheme on large images in terms of computational cost and its effectiveness with respect to the behavior on the tile junctions. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Segmentation Blake-Zisserman functional Domain decomposition block coordinate descent methods Parallel interconnection rule

来源：评论

学校读者我要写书评

暂无评论

On the Convergence of a Regularized Jacobi Algorithm for Convex Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2018年第4期63卷 1113-1119页

作者： Banjac, Goran Margellos, Kostas Goulart, Paul J. Univ Oxford Dept Engn Sci Oxford OX1 3PJ England

In this paper, we consider the regularized version of the Jacobi algorithm, a block coordinate descent method for convex optimization with an objective function consisting of the sum of a differentiable function and a block-separable function. Under certain regularity assumptions on the objective function, this algorithm has been shown to satisfy the so-called sufficient decrease condition, and consequently, to converge in objective function value. In this paper, we revisit the convergence analysis of the regularized Jacobi algorithm and show that it also converges in iterates under very mild conditions on the objective function. Moreover, we establish conditions under which the algorithm achieves a linear convergence rate.

关键词： block coordinate descent methods decentralized optimization Jacobi algorithm linear convergence

来源：评论

学校读者我要写书评

暂无评论

Nonnegative Matrix Factorization

引用

丛书名： Data Science

2020年

作者： Nicolas Gillis

ISBN: (数字)9781611976410

ISBN: (纸本)9781611976403

Nonnegative matrix factorization (NMF) in its modern form has become a standard tool in the analysis of high-dimensional data sets. This book provides a comprehensive and up-to-date account of the most important aspects of the NMF problem and is the first to detail its theoretical aspects, including geometric interpretation, nonnegative rank, complexity, and uniqueness. It explains why understanding these theoretical insights is key to using this computational tool effectively and meaningfully.

Nonnegative Matrix Factorization

is accessible to a wide audience and is ideal for anyone interested in the workings of NMF,
discusses some new results on the nonnegative rank and the identifiability of NMF, and
makes available MATLAB codes for readers to run the numerical examples presented in the book.

Graduate students starting to work on NMF and researchers interested in better understanding the NMF problem and how they can use it will find this book useful. It can be used in advanced undergraduate and graduate-level courses on numerical linear algebra and on advanced topics in numerical linear algebra and requires only a basic knowledge of linear algebra and optimization.

关键词： Nonnegative matrix factorization low-rank matrix approximations nonnegative rank multiplicative updates extended formulations linear dimensionality reduction matrix factorization non-linear optimization blind source separation dictionary learning nested polytope problem identifiability recommender systems topic modeling feature extraction hyperspectral imaging extended formulations audio source separation communication complexity sparsity principal component analysis singular value decomposition computational complexity beta-divergences separability block coordinate descent methods self-modeling curve resolution gene expression analysis matrix factorization

来源：评论

学校读者我要写书评

暂无评论

ACTIVE-SET IDENTIFICATION WITH COMPLEXITY GUARANTEES OF AN ALMOST CYCLIC 2-coordinate descent METHOD WITH ARMIJO LINE SEARCH

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第2期32卷 739-764页

作者： Cristofari, Andrea Univ Padua Dept Math Tullio Levi Civita Via Trieste 63 I-35121 Padua Italy

This paper establishes finite active-set identification of an almost cyclic 2-coordinate descent method for problems with one linear coupling constraint and simple bounds. First, general active-set identification results are stated for nonconvex objective functions. Then, under convexity and a quadratic growth condition (satisfied by any strongly convex function), complexity results on the number of iterations required to identify the active set are given. In our analysis, a simple Armijo line search is used to compute the stepsize, thus not requiring exact minimizations or additional information.

关键词： active-set identification surface identification manifold identification active-set complexity block coordinate descent methods

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：