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

primal-dual Interior-Point Methods for Domain-Driven Formulations

MATHEMATICS OF OPERATIONS RESEARCH 2020年第2期45卷 591-621页

作者： Karimi, Mehdi Tuncel, Levent Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We study infeasible-start, primal-dual interior-point methods for convex optimization problems given in a typically natural form we denote as domain-driven formulations. Our algorithms extend many advantages of primal-dual interior-point techniques available for conic formulations, such as the current best complexity bounds, and more robust certificates of approximate optimality, unboundedness, and infeasibility, to domain-driven formulations. The complexity results are new for the infeasible-start setup used even in the case of linear programming. In addition to complexity results, our algorithms aim for expanding the applications of and software for interior-point methods to wider classes of problems beyond optimization over symmetric cones.

关键词： convex optimization interior-point methods primal-dual algorithms duality theory

来源：评论

学校读者我要写书评

暂无评论

STOCHASTIC primal-dual HYBRID GRADIENT ALGORITHM WITH ARBITRARY SAMPLING AND IMAGING APPLICATIONS

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第4期28卷 2783-2808页

作者： Chambolle, Antonin Ehrhardt, Matthias J. Richtarik, Peter Schonlieb, Carola-Bibiane Ecole Polytech CNRS CMAP F-91128 Palaiseau France Univ Cambridge Dept Appl Math & Theoret Phys Cambridge CB3 0WA England KAUST Visual Comp Ctr Thuwal 23955 Saudi Arabia KAUST Extreme Comp Res Ctr Thuwal 23955 Saudi Arabia Univ Edinburgh Sch Math Edinburgh EH9 3PD Midlothian Scotland Alan Turing Inst London NW1 2DB England

We propose a stochastic extension of the primal-dual hybrid gradient algorithm studied by Chambolle and Pock in 2011 to solve saddle point problems that are separable in the dual variable. The analysis is carried out for general convex-concave saddle point problems and problems that are either partially smooth / strongly convex or fully smooth / strongly convex. We perform the analysis for arbitrary samplings of dual variables, and we obtain known deterministic results as a special case. Several variants of our stochastic method significantly outperform the deterministic variant on a variety of imaging tasks.

关键词： convex optimization primal-dual algorithms saddle point problems stochastic optimization imaging

来源：评论

学校读者我要写书评

暂无评论

Graphical Inference in Linear-Gaussian State-Space Models

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2022年 70卷 4757-4771页

作者： Elvira, Victor Chouzenoux, Emilie Univ Edinburgh Sch Math Edinburgh EH8 9YL Midlothian Scotland Alan Turing Inst London NW1 2DB England Univ Paris Saclay INRIA Cent Supelec Ctr Vis Numer F-1190 Gif Sur Yvette France

State-space models (SSM) are central to describe time-varying complex systems in countless signal processing applications such as remote sensing, networks, biomedicine, and finance to name a few. Inference and prediction in SSMs are possible when the model parameters are known, which is rarely the case. The estimation of these parameters is crucial, not only for performing statistical analysis, but also for uncovering the underlying structure of complex phenomena. In this paper, we focus on the linear-Gaussian model, arguably the most celebrated SSM, and particularly in the challenging task of estimating the transition matrix that encodes the Markovian dependencies in the evolution of the multi-variate state. We introduce a novel perspective by relating this matrix to the adjacency matrix of a directed graph, also interpreted as the causal relationship among state dimensions in the Granger-causality sense. Under this perspective, we propose a new method called GraphEM based on the well sounded expectation-maximization (EM) methodology for inferring the transition matrix jointly with the smoothing/filtering of the observed data. We propose an advanced convex optimization solver relying on a consensus-based implementation of a proximal splitting strategy for solving the M-step. This approach enables an efficient and versatile processing of various sophisticated priors on the graph structure, such as parsimony constraints, while benefiting from convergence guarantees. We demonstrate the good performance and the interpretable results of GraphEM by means of two sets of numerical examples.

关键词： Time series analysis Mathematical models Sparse matrices Numerical models Kalman filters Signal processing algorithms State-space methods State-space modeling graphical inference sparsity proximal methods primal-dual algorithms Kalman filtering EM algorithm

来源：评论

学校读者我要写书评

暂无评论

Market Equilibrium via a primal-dual Algorithm for a Convex Program

引用

JOURNAL OF THE ACM 2008年第5期55卷 22:1-22:18页

作者： Devanur, Nikhil R. Papadimitriou, Christos H. Saberi, Amin Vazirani, Vijay V. Georgia Inst Technol Atlanta GA 30332 USA Univ Calif Berkeley Div Comp Sci Dept EECS Berkeley CA 94720 USA

We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal-dual paradigm in the enhanced setting of KKT conditions and convex programs. We pinpoint the added difficulty raised by this setting and the manner in which our algorithm circumvents it.

关键词： algorithms Economics Market equilibria primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Steady Bingham fluid flow in cylindrical pipes: a time dependent approach to the iterative solution

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2000年第6期7卷 381-428页

作者： He, JW Glowinski, R Univ Houston Dept Math Houston TX 77204 USA

The main goal of this article is to discuss a novel iterative method for the numerical simulation of a steady Bingham fluid flow in a cylindrical pipe. The method is of the primal-dual type and can be interpreted as an implicit scheme of backward Euler type, applied to a well chosen time dependent variant of the problem under consideration. A key ingredient of the algorithm is a kind of dynamical Tychonoff regularization of the fixed point relation verified by the dual solution. After proving the convergence of the method, we apply it to the solution of test problems and verify its anticipated good convergence properties. Copyright (C) 2000 John Wiley & Sons, Ltd.

关键词： Bingham fluids primal-dual algorithms Tychonoff regularization backward Euler schemes Opial's lemma fast Poisson solvers

来源：评论

学校读者我要写书评

暂无评论

Online Budgeted Allocation with General Budgets 16

Online Budgeted Allocation with General Budgets

引用

17th ACM Conference on Economics and Computation (EC)

作者： Kell, Nathaniel Panigrahi, Debmalya Duke Univ Dept Comp Sci Durham NC 27706 USA

ISBN: (纸本)9781450339360

We study the online budgeted allocation (also called ADWORDS) problem, where a set of impressions arriving online are allocated to a set of budget-constrained advertisers to maximize revenue. Motivated by connections to Internet advertising, several variants of this problem have been studied since the seminal work of Mehta, Saberi, Vazirani, and Vazirani (FOCS 2005). However, this entire body of work focuses on a single budget for every advertising campaign, whereas in order to fully represent the actual agenda of an advertiser, an advertising budget should be expressible over multiple tiers of user-attribute granularity. A simple example is an advertising campaign that is constrained by an overall budget but is also accompanied by a set of sub-budgets for each target demographic. In such a contract scheme, an advertiser can specify their true user-targeting goals, allowing the publisher to fulfill them through relevant allocations. In this paper, we give a complete characterization of the ADWORDS problem for general advertising budgets. In the most general setting, we show that, unlike in the single-budget ADWORDS problem, obtaining a constant competitive ratio is impossible and give asymptotically tight upper and lower bounds. However for our main result, we observe that in many real-world scenarios (as in the above example), multi-tier budgets have a laminar structure, since most relevant consumer or product classifications are hierarchical. For laminar budgets, we obtain a competitive ratio of e/(e-1) in the small bids case, which matches the best known ADWORDS result for single budgets. Our algorithm has a primal-dual structure and generalizes the primal-dual analysis for single-budget ADWORDS first given by Buchbinder, Jain, and Naor (ESA 2007). However many new ideas are required to overcome the barriers introduced by laminar budgets-our algorithm uses a novel formulation that overcomes non-monotonicity in the syntactically defined dual variables, as well as

关键词： Internet advertising adwords user targeting primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

The clustering matroid and the optimal clustering tree

引用

MATHEMATICAL PROGRAMMING 2003年第1-3期98卷 385-414页

作者： Korach, E Stern, M Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

We consider the following problem: Given a complete graph G=(V,E) with a cost on every edge and a given collection of subsets of V, we have to find a minimum cost spanning tree T such that each subset of the vertices in the collection induces a subtree in T. One motivation for this problem is to construct a minimum cost communication tree network for a collection of non-disjoint groups of customers such that the network will provide ``group fault tolerance'' and ``group privacy''. We model this problem as a matroid. We extend it to general matroids and call the new matroids ``clustering matroids''. We define three variations of the clustering tree problem and show that from an algorithmic point of view they are polynomially equivalent. We present a polynomial algorithm for one of the three variations, which implies that all of them can be solved polynomially. For the case where the cardinality of the subsets in the collection does not exceed three, we provide a greedy algorithm, a linear algorithm and also a polyhedron description of the convex hull of all the feasible solutions.

关键词： combinatorial optimization clustering spanning trees matroids hypergraphs polynomial graph algorithms primal-dual algorithms polyhedra

来源：评论

学校读者我要写书评

暂无评论

A superlinearly convergent primal - dual algorithm model for constrained optimization problems with bounded variables

引用

OPTIMIZATION METHODS & SOFTWARE 2000年第1-2期14卷 49-73页

作者： Di Pillo, G Lucidi, S Palagi, L Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy

In this paper we introduce a Newton-type algorithm model for solving smooth nonlinear optimization problems with general constraints and bound constraints on the variables. Under very mild assumptions and without requiring the strict complementarity assumption, the algorithm produces a sequence of pairs {(x(k), gimel (k))} converging quadratically to ((x) over bar, <()over bar>), where (x ) over bar is the solution of the problem and gimel is the KKT multiplier associated with the general constraints. As regards the behaviour of the sequence {x(k)} alone, it converges at least superlinearly. A distinguishing feature of the proposed algorithm is that it exploits the particular structure of the constraints of the optimization problem so as to limit the computational burden as much as possible. In fact, at each iteration, it requires only the solution of a linear system whose dimension is equal at most to the number of variables plus the number of the general constraints. Hence, the proposed algorithm model may be well suited to tackle large scale problems. Even though the analysis is concerned mainly with the local behavior of the algorithm, we also suggest a way of forcing the global convergence.

关键词： nonlinear programming primal-dual algorithms bound constraints

来源：评论

学校读者我要写书评

暂无评论

On the Convergence of Approximate Message Passing With Arbitrary Matrices

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第9期65卷 5339-5351页

作者： Rangan, Sundeep Schniter, Philip Fletcher, Alyson K. Sarkar, Subrata NYU Dept Elect & Comp Engn Brooklyn NY 11201 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Univ Calif Los Angeles Dept Stat & Elect Engn Los Angeles CA 90095 USA

Approximate message passing (AMP) methods and their variants have attracted considerable recent attention for the problem of estimating a random vector x observed through a linear transform A. In the case of large i.i.d. zero-mean Gaussian A, the methods exhibit fast convergence with precise analytic characterizations on the algorithm behavior. However, the convergence of AMP under general transforms A is not fully understood. In this paper, we provide sufficient conditions for the convergence of a damped version of the generalized AMP (GAMP) algorithm in the case of quadratic cost functions (i.e., Gaussian likelihood and prior). It is shown that, with sufficient damping, the algorithm is guaranteed to converge, although the amount of damping grows with peak-to-average ratio of the squared singular values of the transforms A. This result explains the good performance of AMP on i.i.d. Gaussian transforms A, but also their difficulties with ill-conditioned or non-zero-mean transforms A. A related sufficient condition is then derived for the local stability of the damped GAMP method under general cost functions, assuming certain strict convexity conditions.

关键词： Approximate message passing loopy belief propagation Gaussian belief propagation primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Nearly-Linear Time Positive LP Solver with Faster Convergence Rate 15

Nearly-Linear Time Positive LP Solver with Faster Convergenc...

引用

47th Annual ACM Symposium on Theory of Computing (STOC) held as part of the Federated Computing Research Conference

作者： Allen-Zhu, Zeyuan Orecchia, Lorenzo MIT CSAIL Cambridge MA 02139 USA Boston Univ Boston MA 02215 USA

ISBN: (纸本)9781450335362

Positive linear programs (LP), also known as packing and covering linear programs, are an important class of problems that bridges computer science, operation research, and optimization. Efficient algorithms for solving such LPs have received significant attention in the past 20 years [2, 3, 4, 6, 7, 9, 11, 15, 16, 18, 19, 21, 24, 25, 26, 29, 30]. Unfortunately, all known nearly-linear time algorithms for producing (1+epsilon)-approximate solutions to positive LPs have a running time dependence that is at least proportional to epsilon(-2). This is also known as an O(1/root T) convergence rate and is particularly poor in many applications. In this paper, we leverage insights from optimization theory to break this longstanding barrier. Our algorithms solve the packing LP in time (O) over tilde (N epsilon(-1)) and the covering LP in time (O) over tilde (N epsilon(-1.5)). At high level, they can be described as linear couplings of several first-order descent steps. This is the first application of our linear coupling technique (see [1]) to problems that are not amenable to blackbox applications known iterative algorithms in convex optimization. Our work also introduces a sequence of new techniques, including the stochastic and the non-symmetric execution of gradient truncation operations, which may be of independent interest.

关键词： packing and covering linear programs primal-dual algorithms width-independent algorithms first-order iterative methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：