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

Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2017年第1期68卷 57-93页

作者： Latafat, Puya Patrinos, Panagiotis Katholieke Univ Leuven Dept Elect Engn ESAT STADIUS Kasteelpk Arenberg 10 B-3001 Leuven Belgium IMT Sch Adv Studies Lucca Piazza San Francesco 19 I-55100 Lucca Italy

In this work we propose a new splitting technique, namely Asymmetric Forward-Backward-Adjoint splitting, for solving monotone inclusions involving three terms, a maximally monotone, a cocoercive and a bounded linear operator. Our scheme can not be recovered from existing operator splitting methods, while classical methods like Douglas-Rachford and Forward-Backward splitting are special cases of the new algorithm. Asymmetric preconditioning is the main feature of Asymmetric Forward-Backward-Adjoint splitting, that allows us to unify, extend and shed light on the connections between many seemingly unrelated primal-dual algorithms for solving structured convex optimization problems proposed in recent years. One important special case leads to a Douglas-Rachford type scheme that includes a third cocoercive operator.

关键词： Convex optimization Monotone inclusion Operator splitting primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Implementation of infinite-dimensional interior-point method for solving multi-criteria linear-quadratic control problem

引用

OPTIMIZATION METHODS & SOFTWARE 2006年第2期21卷 315-341页

作者： Faybusovich, L Mouktonglang, T Tsuchiya, T Univ Notre Dame Dept Math Notre Dame IN 46556 USA Inst Stat Math Minato Ku Tokyo 1068569 Japan

We describe an implementation of an infinite-dimensional primal - dual algorithm based on the Nesterov - Todd direction. Several applications to both continuous and discrete-time multi-criteria linear-quadratic control problems and linear-quadratic control problem with quadratic constraints are described. Numerical results show a very fast convergence ( typically, within 3 - 4 iterations) to optimal solutions.

关键词： infinite-dimensional Jordan algebras primal-dual algorithms multi-criteria control

来源：评论

学校读者我要写书评

暂无评论

algorithms for provisioning virtual private networks in the hose model

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2002年第4期10卷 565-578页

作者： Kumar, A Rastogi, R Silberschatz, A Yener, B Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Bell Labs Murray Hill NJ 07974 USA

Virtual Private Networks (VPNs) provide customers with predictable and secure network connections over a shared network. The recently proposed hose model for VPNs allows for greater flexibility since it permits traffic to and from a hose. endpoint to be arbitrarily distributed to other endpoints. In this paper, we develop novel algorithms for provisioning VPNs in the hose model. We connect VPN endpoints using a tree structure and our algorithms attempt to optimize the total bandwidth reserved on edges of the VPN tree. We show that even for the simple scenario in which network links are assumed to have infinite capacity, the general problem of computing the optimal VPN tree is NP-hard. Fortunately, for the special case when the ingress and egress bandwidths for each VPN endpoint are equal, we can devise an algorithm for computing the optimal tree whose time complexity is 0(mn), where m and n are the number of links and nodes in the network, respectively. We present a novel integer programming formulation for the general VPN tree computation problem (that is, when ingress and egress bandwidths of VPN endpoints are arbitrary) and develop an algorithm that is based on the primal-dual method. Our experimental results with synthetic network graphs indicate. that the VPN trees constructed by our proposed algorithms dramatically reduce bandwidth requirements (in many instances, by more than a factor of 2) compared to scenarios in which Steiner trees are employed to connect VPN endpoints.

关键词： approximation algorithms bandwidth utilization facility location problem Hose model LP rounding primal-dual algorithms provisioning Steiner trees virtual private networks

来源：评论

学校读者我要写书评

暂无评论

Node-weighted Network Design in Planar and Minor-closed Families of Graphs

引用

ACM TRANSACTIONS ON algorithms 2021年第2期17卷 1–25页

作者： Chekuri, Chandra Ene, Alina Vakilian, Ali Univ Illinois 201 N Goodwin Ave Urbana IL 61801 USA Boston Univ 111 Cummington Mall Boston MA 02215 USA Toyota Technol Inst Chicago TTIC 6045 South Kenwood Ave Chicago IL 60637 USA

We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = (V, E) and integer connectivity requirements r (uv) for each unordered pair of nodes uv. The goal is to find a minimum weighted subgraph H of G such that H contains r (uv) disjoint paths between u and v for each node pair uv. Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O(k)-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs;here, k = max(uv) r (uv) is the maximum connectivity requirement. This improves upon the O(k logn)-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O(1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2};for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.

关键词： Approximation algorithms network design primal-dual algorithms element/vertex connectivity

来源：评论

学校读者我要写书评

暂无评论

"Cone-free" primal-dual path-following and potential-reduction polynomial time interior-point methods

引用

MATHEMATICAL PROGRAMMING 2005年第2期102卷 261-294页

作者： Nemirovski, A Tunçel, L Technion Israel Inst Technol Fac IE&M Haifa Israel Univ Waterloo Fac Math Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the problem (as is, without a conic reformulation) using the very usual primal central path concept and a less usual version of a dual path concept. We show that many of the advantages of the primal-dual interior-point techniques are available to us in this framework and therefore, they are not intrinsically tied to the conic reformulation and the logarithmic homogeneity of the underlying barrier function.

关键词： convex optimization interior-point methods primal-dual algorithms self-concordant barriers

来源：评论

学校读者我要写书评

暂无评论

Designing Truthful Spectrum Auctions for Multi-hop Secondary Networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2015年第2期14卷 316-327页

作者： Li, Zongpeng Li, Baochun Zhu, Yuefei Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 3G4 Canada

Opportunistic wireless channel access granted to non-licensed users through auctions represents a promising approach for effectively distributing and utilizing the scarce wireless spectrum. A limitation of existing spectrum auction designs lies in the over-simplifying assumption that every non-licensed secondary user is a single node or single-hop network. For the first time in the literature, we propose to model non-licensed users as secondary networks (SNs), each of which comprises of a multihop network with end-to-end routing demands. We use simple examples to show that such auctions among SNs differ drastically from simple auctions among single-hop users, and previous solutions suffer from local, per-hop decision making. We first design a simple, heuristic auction that takes inter-SN interference into consideration and is truthful. We then design a randomized auction framework based on primal-dual linear optimization, which is automatically truthful and achieves a social welfare approximation ratio that matches one achieved by cooperative optimization assuming truthful bids for free. The framework relieves a spectrum auction designer from worrying about truthfulness of the auction, so that he or she can focus on social welfare maximization while assuming truthful bids for free.

关键词： Truthful auctions secondary spectrum allocation secondary networks linear programming primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Stochastic primal-dual Coordinate Method for Regularized Empirical Risk Minimization

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2017年第1期18卷 2939-2980页

作者： Zhang, Yuchen Xiao, Lin Stanford Univ Dept Comp Sci Stanford CA 94305 USA Microsoft Res Redmond WA 98052 USA

We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variables. An extrapolation step on the primal variables is performed to obtain accelerated convergence rate. We also develop a minibatch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods.

关键词： empirical risk minimization randomized algorithms convex-concave saddle point problems primal-dual algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

An FFT-based method for computing weighted minimal surfaces in microstructures with applications to the computational homogenization of brittle fracture

引用

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING 2020年第7期121卷 1367-1387页

作者： Schneider, Matti KIT Inst Engn Mech D-76131 Karlsruhe Germany

Cell formulae for the effective crack resistance of a heterogeneous medium obeying Francfort-Marigo's formulation of linear elastic fracture mechanics have been proved recently, both in the context of periodic and stochastic homogenization. This work proposes a numerical strategy for computing the effective, possibly anisotropic, crack resistance of voxelized microstructures using the fast Fourier transform (FFT). Based on Strang's continuous minimum cut-maximum flow duality, we explore a primal-dual hybrid gradient method for computing the effective crack resistance, which may be readily integrated into an existing FFT-based code for homogenizing thermal conductivity. We close with demonstrative numerical experiments.

关键词： brittle fracture computational homogenization FFT-based method maximum flow primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems

引用

APPLIED MATHEMATICS AND COMPUTATION 2010年第7期216卷 1889-1895页

作者： Achache, Mohamed Univ Ferhat Abbas Setif Lab Math Fondamentales & Numer Setif Algeria

In this paper we deal with the study of the polynomial complexity and numerical implementation for a short-step primal-dual interior point algorithm for monotone linear complementarity problems LCP. The analysis is based on a new class of search directions used by the author for convex quadratic programming (CQP) [M. Achache, A new primal-dual path-following method for convex quadratic programming, Computational and Applied Mathematics 25 (1) (2006) 97-110]. Here, we show that this algorithm enjoys the best theoretical polynomial complexity namely O(root n log n/epsilon), iteration bound. For its numerical performances some strategies are used. Finally, we have tested this algorithm on some monotone linear complementarity problems. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Linear complementarity problems Interior point methods primal-dual algorithms Polynomial complexity Numerical implementation

来源：评论

学校读者我要写书评

暂无评论

Learning Consistent Discretizations of the Total Variation

引用

SIAM JOURNAL ON IMAGING SCIENCES 2021年第2期14卷 778-813页

作者： Chambolle, Antonin Pock, Thomas CNRS CEREMADE F-75016 Paris France Univ Paris Dauphine PSL F-75016 Paris France Graz Univ Technol Inst Comp Graph & Vis A-8010 Graz Austria

In this work, we study a general framework of discrete approximations of the total variation for image reconstruction problems. The framework, for which we can show consistency in the sense of Gamma-convergence, unifies and extends several existing discretization schemes. In addition, we propose algorithms for learning discretizations of the total variation in order to achieve the best possible reconstruction quality for particular image reconstruction tasks. Interestingly, the learned discretizations significantly differ between the tasks, illustrating that there is no universal best discretization of the total variation.

关键词： total variation image denoising image inpainting discretization finite differences finite elements learning bilevel optimization primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：