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

INTERPOLATION CONDITIONS FOR LINEAR OPERATORS AND APPLICATIONS TO PERFORMANCE ESTIMATION PROBLEMS*

SIAM JOURNAL ON OPTIMIZATION 2024年第3期34卷 3033-3063页

作者： Bousselmi, Nizar Hendrickx, Julien m. Glineur, Francois UCLouvain ICTEAM Louvain La Neuve Belgium UCLouvain CORE Louvain LaNeuve Belgium

The performance estimation problem methodology makes it possible to determine the exact worst-case performance of an optimization method. In this work, we generalize this framework to first-order methods involving linear operators. This extension requires an explicit formulation of interpolation conditions for those linear operators. We consider the class of linear operators M : x H- Mx, where matrix M has bounded singular values, and the class of linear operators, where M is symmetric and has bounded eigenvalues. We describe interpolation conditions for these classes, i.e., necessary and sufficient conditions that, given a list of pairs {(xi, yi)}, characterize the existence of a linear operator mapping xito yifor all i. Using these conditions, we first identify the exact worst-case behavior of the gradient method applied to the composed objective h \circ M, and observe that it always corresponds to M being a scaling operator. We then investigate the Chambolle-Pock method applied to f + g \circ M, and improve the existing analysis to obtain a proof of the exact convergence rate of the primal-dual gap. In addition, we study how this method behaves on Lipschitz convex functions, and obtain a numerical convergence rate for the primal accuracy of the last iterate. We also show numerically that averaging iterates is beneficial in this setting.

关键词： first-order algorithms performance estimation exact convergence rates interpola- tion conditions linear operators primal-dual algorithms quadratic functions

来源：评论

学校读者我要写书评

暂无评论

An inexact primal-dual algorithm for semi-infinite programming

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2020年第3期91卷 501-544页

作者： Wei, Bo Haskell, William B. Zhao, Sixiang Natl Univ Singapore Singapore Singapore Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA Shanghai Jiao Tong Univ Sino US Global Logist Inst Shanghai Peoples R China

This paper considers an inexact primal-dual algorithm for semi-infinite programming (SIP) for which it provides general error bounds. We create a new prox function for nonnegative measures for the dual update, and it turns out to be a generalization of the Kullback-Leibler divergence. We show that, with a tolerance for small errors (approximation and regularization error), this algorithm achieves anO(1/K) rate of convergence in terms of the optimality gap and constraint violation, whereKis the total number of iterations. We then use our general error bounds to analyze the convergence and sample complexity of a specific primal-dual SIP algorithm based on Monte Carlo sampling. Finally, we provide numerical experiments to demonstrate the performance of this algorithm.

关键词： Semi-infinite programming primal-dual algorithms Monte Carlo integration

来源：评论

学校读者我要写书评

暂无评论

ZONE: Zeroth-Order Nonconvex Multiagent Optimization Over Networks

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第10期64卷 3995-4010页

作者： Hajinezhad, Davood Hong, Mingyi Garcia, Alfredo SAS Inst Cary NC 27513 USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77840 USA

In this paper, we consider distributed optimization problems over a multiagent network, where each agent can only partially evaluate the objective function, and it is allowed to exchange messages with its immediate neighbors. Differently from all existing works on distributed optimization, our focus is given to optimizing a class of nonconvex problems and under the challenging setting, where each agent can only access the zeroth-order information (i.e., the functional values) of its local functions. For different types of network topologies, such as undirected connected networks or star networks, we develop efficient distributed algorithms and rigorously analyze their convergence and rate of convergence (to the set of stationary solutions). Numerical results are provided to demonstrate the efficiency of the proposed algorithms.

关键词： Distributed optimization nonconvex optimization primal-dual algorithms zeroth-order information

来源：评论

学校读者我要写书评

暂无评论

Preconditioned Douglas-Rachford algorithms for TV- and TGV-Regularized Variational Imaging Problems

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2015年第3期52卷 317-344页

作者： Bredies, Kristian Sun, Hong Peng Graz Univ Inst Math & Sci Comp A-8010 Graz Austria

The recently introduced preconditioned Douglas-Rachford iteration (PDR) for convex-concave saddle-point problems is studied with respect to convergence rates and applied to variational imaging problems with total variation (TV) and total generalized variation (TGV) penalty. A rate of for restricted primal-dual gaps evaluated for ergodic sequences generated by the PDR iteration is established. Based on PDR, new fast iterative algorithms for TV-denoising, TV-deblurring, and TGV-denoising of second order with and discrepancy are proposed. While for denoising, symmetric (block) Red-Black Gauss-Seidel preconditioners are effective, fast Fourier transform-based preconditioners are employed for the deblurring problems. Finally, for the -TGV-denoising problem, an effective modified primal-dual gap is developed which may serve as a stopping criterion. All algorithms are tested and compared in numerical experiments. In particular, for problems where strong convexity does not hold, it turns out that the proposed preconditioning techniques are beneficial and lead to competitive results.

关键词： Preconditioned Douglas-Rachford iteration primal-dual algorithms Variational image denoising and deblurring Total generalized variation Block preconditioner

来源：评论

学校读者我要写书评

暂无评论

A primal-dual bicriteria distributed algorithm for capacitated vertex cover

引用

SIAM JOURNAL ON COMPUTING 2008年第3期38卷 825-840页

作者： Grandoni, F. Koenemann, J. Panconesi, A. Sozio, M. Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Roma La Sapienza Dipartimento Informat I-00198 Rome Italy Max Planck Inst Informat Dept Databases & Informat Syst D-66123 Saarbrucken Germany

In this paper we consider the capacitated vertex cover problem, which is the variant of vertex cover where each node is allowed to cover a limited number of edges. We present an efficient, deterministic, distributed approximation algorithm for the problem. Our algorithm computes a (2+epsilon)-approximate solution which violates the capacity constraints by a factor of (4+epsilon) in a polylogarithmic number of communication rounds. On the other hand, we also show that every efficient distributed approximation algorithm for this problem must violate the capacity constraints. Our result is achieved in two steps. We first develop a 2-approximate, sequential primal-dual algorithm that violates the capacity constraints by a factor of 2. Subsequently, we present a distributed version of this algorithm. We demonstrate that the sequential algorithm has an inherent need for synchronization which forces any naive distributed implementation to use a linear number of communication rounds. The challenge in this step is therefore to achieve a reduction of the communication complexity to a polylogarithmic number of rounds without worsening the approximation guarantee.

关键词： vertex cover approximation algorithms distributed algorithms primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Combinatorial algorithms for Data Migration to Minimize Average Completion Time

引用

ALGORITHMICA 2009年第1期54卷 54-71页

作者： Gandhi, Rajiv Mestre, Julian Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA Max Planck Inst Informat Saarbrucken Germany

The data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. It is modeled by a transfer graph, where vertices represent the storage devices, and edges represent data transfers required between pairs of devices. Each vertex has a non-negative weight, and each edge has a processing time. A vertex completes when all the edges incident on it complete;the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim (J. algorithms 55, 42-57, 2005) gave an LP-rounding 3-approximation algorithm when edges have unit processing times. We give a more efficient primal-dual algorithm that achieves the same approximation guarantee. When edges have arbitrary processing times we give a primal-dual 5.83-approximation algorithm. We also study a variant of the open shop scheduling problem. This is a special case of the data migration problem in which the transfer graph is bipartite and the objective is to minimize the sum of completion times of edges. We present a simple algorithm that achieves an approximation ratio of root 2 approximate to 1.414, thus improving the 1.796-approximation given by Gandhi et al. (ACM Trans. algorithms 2(1), 116-129, 2006). We show that the analysis of our algorithm is almost tight.

关键词： primal-dual algorithms Approximation algorithms Min-sum scheduling problems

来源：评论

学校读者我要写书评

暂无评论

An Inertial Forward-Backward Algorithm for Monotone Inclusions

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2015年第2期51卷 311-325页

作者： Lorenz, Dirk A. Pock, Thomas TU Braunschweig Inst Anal & Algebra D-38092 Braunschweig Germany Graz Univ Technol Inst Comp Graph & Vis A-8010 Graz Austria AIT Austrian Inst Technol GmbH Safety & Secur Dept A-1220 Vienna Austria

In this paper, we propose an inertial forward-backward splitting algorithm to compute a zero of the sum of two monotone operators, with one of the two operators being co-coercive. The algorithm is inspired by the accelerated gradient method of Nesterov, but can be applied to a much larger class of problems including convex-concave saddle point problems and general monotone inclusions. We prove convergence of the algorithm in a Hilbert space setting and show that several recently proposed first-order methods can be obtained as special cases of the general algorithm. Numerical results show that the proposed algorithm converges faster than existing methods, while keeping the computational cost of each iteration basically unchanged.

关键词： Convex optimization Forward-backward splitting Monotone inclusions primal-dual algorithms Saddle-point problems Image restoration

来源：评论

学校读者我要写书评

暂无评论

A nested primal-dual FISTA-like scheme for composite convex optimization problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2023年第1期84卷 85-123页

作者： Bonettini, S. Prato, M. Rebegoldi, S. Univ Modena & Reggio Emilia Dipartimento Sci Fis Informat & Matemat Via Campi 213 I-41125 Modena Italy Univ Firenze Dipartimento Ingn Ind Viale Morgagni 40 I-50143 Florence Italy

We propose a nested primal-dual algorithm with extrapolation on the primal variable suited for minimizing the sum of two convex functions, one of which is continuously differentiable. The proposed algorithm can be interpreted as an inexact inertial forward-backward algorithm equipped with a prefixed number of inner primal-dual iterations for the proximal evaluation and a "warm-start" strategy for starting the inner loop, and generalizes several nested primal-dual algorithms already available in the literature. By appropriately choosing the inertial parameters, we prove the convergence of the iterates to a saddle point of the problem, and provide an O(1/n) convergence rate on the primal-dual gap evaluated at the corresponding ergodic sequences. Numerical experiments on some image restoration problems show that the combination of the "warm-start" strategy with an appropriate choice of the inertial parameters is strictly required in order to guarantee the convergence to the real minimum point of the objective function.

关键词： primal-dual algorithms Forward-backward algorithms Inertial techniques Convex optimization Image deblurring

来源：评论

学校读者我要写书评

暂无评论

A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2009年第3期18卷 258-271页

作者： Jung, Hyunwoo Hasan, Mohammad Khairul Chwa, Kyung-Yong Korea Adv Inst Sci & Technol Div Comp Sci Taejon 305701 South Korea

In the connected facility location (ConFL) problem, we are given a graph G = (V, E) with nonnegative edge cost c(e) on the edges, a set of facilities F subset of V, a set of demands (i.e., clients) D subset of V, and a parameter M >= 1. Each facility i has a nonnegative opening cost f(i) and each client j has d(j) units of demand. Our objective is to open some facilities, say F. F, assign each demand j to some open facility i(j) is an element of F and connect all open facilities using a Steiner tree T such that the total cost, which is Sigma(i is an element of F) f(i) + Sigma(j is an element of D) d(j) c(i) ((j)) (j) + M Sigma(e is an element of T) c(e), is minimized. We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation algorithm given by Swamy and Kumar (Algorithmica 40:245-269, 2004).

关键词： Approximation algorithms primal-dual algorithms Facility location problems Greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Generalization of primal-dual interior-point methods to convex optimization problems in conic form

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2001年第3期1卷 229-254页

作者： Tunçel, L Univ Waterloo Fac Math Dept Combinatories & Optimizat Waterloo ON N2L 3G1 Canada

We generalize primal-dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal-dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace, In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov-Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal-dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal-dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal-dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework.

关键词： convex optimization interior-point method primal-dual algorithms self-concordant barriers Quasi-Newton updates symmetric cones polynomial iteration-complexity variable metric methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：