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

Spending Constraint Utilities with Applications to the Adwords Market

MATHEMATICS OF OPERATIONS RESEARCH 2010年第2期35卷 458-478页

作者： Vazirani, Vijay V. Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

The notion of a "market" has undergone a paradigm shift with the Internet. Totally new and highly successful markets have been defined and launched by Internet companies, which already form an important part of today's economy and are projected to grow considerably in the future. Another major change is the availability of massive computational power for running these markets in a centralized or distributed manner. In view of these new realities, the study of market equilibria, an important, though essentially nonalgorithmic, theory within mathematical economics, needs to be revived and rejuvenated via an inherently algorithmic approach. Such a theory should not only address traditional market models, but also de. ne new models for some of the new markets. We present a new, natural class of utility functions that allow buyers to explicitly provide information on their relative preferences as a function of the amount of money spent on each good. These utility functions offer considerable expressivity, especially in Google's Adwords market. In addition, they lend themselves to efficient computation, while retaining some of the nice properties of traditional models. The latter include weak gross substitutability, and the uniqueness and continuity of equilibrium prices and utilities.

关键词： market equilibrium Fisher's model linear utilities piecewise-linear concave utilities Adwords market search engines combinatorial algorithms primal-dual algorithms weak gross substitutability

来源：评论

学校读者我要写书评

暂无评论

A primal-dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

引用

ALGORITHMICA 2009年第1期55卷 227-239页

作者： Mestre, Julian Univ Maryland Dept Comp Sci College Pk MD 20742 USA

We study the PARTIAL VERTEX COVER problem. Given a graph G = (V, E), a weight function w : V -> R+, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the well-known VERTEX COVER problem. We provide a primal-dual 2-approximation algorithm which runs in O(n log n + m) time. This represents an improvement in running time from the previously known fastest algorithm. Our technique can also be used to get a 2-approximation for a more general version of the problem. In the PARTIAL CAPACITATED VERTEX COVER problem each vertex u comes with a capacity k(u). A solution consists of a function x : V -> N-0 and an orientation of all but s edges, such that the number of edges oriented toward vertex u is at most x(u)k(u). Our objective is to find a cover that minimizes Sigma(v is an element of V) x(v)w(v). This is the first 2-approximation for the problem and also runs in O(n log n + m) time.

关键词： Approximation algorithms Vertex cover primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Status determination by interior-point methods for convex optimization problems in domain-driven form

引用

MATHEMATICAL PROGRAMMING 2022年第1-2期194卷 937-974页

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

We study the geometry of convex optimization problems given in a Domain-Driven form and categorize possible statuses of these problems using duality theory. Our duality theory for the Domain-Driven form, which accepts both conic and non-conic constraints, lets us determine and certify statuses of a problem as rigorously as the best approaches for conic formulations (which have been demonstrably very efficient in this context). We analyze the performance of a class of infeasible-start primal-dual algorithms for the Domain-Driven form in returning the certificates for the defined statuses. Our iteration complexity bounds for this more practical Domain-Driven form match the best ones available for conic formulations. At the end, we propose some stopping criteria for practical algorithms based on insights gained from our analyses.

关键词： Convex optimization Interior-point methods primal-dual algorithms duality theory Status determination

来源：评论

学校读者我要写书评

暂无评论

On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting

引用

MATHEMATICAL PROGRAMMING 2020年第1-2期179卷 85-108页

作者： O'Connor, Daniel Vandenberghe, Lieven Univ San Francisco Dept Math & Stat San Francisco CA 94117 USA Univ Calif Los Angeles Dept Elect & Comp Engn Los Angeles CA USA

The primal-dual hybrid gradient (PDHG) algorithm proposed by Esser, Zhang, and Chan, and by Pock, Cremers, Bischof, and Chambolle is known to include as a special case the Douglas-Rachford splitting algorithm for minimizing the sum of two convex functions. We show that, conversely, the PDHG algorithm can be viewed as a special case of the Douglas-Rachford splitting algorithm.

关键词： Douglas-Rachford splitting primal-dual algorithms Monotone operators Proximal algorithms

来源：评论

学校读者我要写书评

暂无评论

Domain-Driven Solver (DDS) Version 2.1: a MATLAB-based software package for convex optimization problems in domain-driven form

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2024年第1期16卷 37-92页

作者： Karimi, Mehdi Tuncel, Levent Illinois State Univ Dept Math Normal IL 61761 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

Domain-Driven Solver (DDS) is a MATLAB-based software package for convex optimization. The current version of DDS accepts every combination of the following function/set constraints: (1) symmetric cones (LP, SOCP, and SDP);(2) quadratic constraints that are SOCP representable;(3) direct sums of an arbitrary collection of 2-dimensional convex sets defined as the epigraphs of univariate convex functions (including as special cases geometric programming and entropy programming);(4) generalized Koecher (power) cone;(5) epigraphs of matrix norms (including as a special case minimization of nuclear norm over a linear subspace);(6) vector relative entropy;(7) epigraphs of quantum entropy and quantum relative entropy;and (8) constraints involving hyperbolic polynomials. The infeasible-start primal-dual algorithms used for DDS rely heavily on duality theory and properties of Legendre-Fenchel conjugate functions, and are designed to rigorously determine the status of a given problem. We discuss some important implementation details and techniques we used to improve the robustness and efficiency of the software. The appendix contains many examples.

关键词： Convex optimization Software package Self-concordant functions Interior-point methods primal-dual algorithms duality theory

来源：评论

学校读者我要写书评

暂无评论

INFEASIBILITY DETECTION WITH primal-dual HYBRID GRADIENT FOR LARGE-SCALE LINEAR PROGRAMMING

引用

SIAM JOURNAL ON OPTIMIZATION 2024年第1期34卷 459-484页

作者： Applegate, David Diaz, Mateo Lu, Haihao Lubin, Miles Google Res New York NY 11950 USA Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD 21218 USA Univ Chicago Booth Sch Business Chicago IL 60637 USA

We study the problem of detecting infeasibility of large-scale linear programming problems using the primal-dual hybrid gradient (PDHG) method of Chambolle and Pock [J. Math. Imaging Vision, 40 (2011), pp. 120--145]. The literature on PDHG has focused chiefly on problems with at least one optimal solution. We show that when the problem is infeasible or unbounded, the iterates diverge at a controlled rate toward a well-defined ray. In turn, the direction of such a ray recovers infeasibility certificates. Based on this fact, we propose a simple way to extract approximate infeasibility certificates from the iterates of PDHG. We study three sequences that converge to certificates: the difference of iterates, the normalized iterates, and the normalized average. All of them are easy to compute and suitable for large-scale problems. We show that the normalized iterates and normalized averages achieve a convergence rate of O \bigl( k-1\bigr) . This rate is general and applies to any fixed-point iteration of a nonexpansive operator. Thus, it is a result of independent interest that goes well beyond our setting. Finally, we show that, under nondegeneracy assumptions, the iterates of PDHG identify the active set of an auxiliary feasible problem in finite time, which ensures that the difference of iterates exhibits eventual linear convergence. These results provide a theoretical justification for infeasibility detection in the newly developed linear programming solver PDLP.

关键词： linear programming infeasibility detection primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Newton-KKT interior-point methods for indefinite quadratic programming

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2007年第1期36卷 5-41页

作者： Absil, P.-A. Tits, Andre L. Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA Univ Catholique Louvain Dept Ingn Math B-1348 Louvain Belgium

Two interior-point algorithms are proposed and analyzed, for the (local) Solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (Much like in the case of primal-dual algorithms for linear programming) search directions for the "primal" variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the Solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a "primal" affine-scaling algorithm (a la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285-300]. we consider a simple Newton-KKT affine-scaling algorithm. Then, a "barrier" version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems Suggest that the proposed algorithms may be of great practical interest.

关键词： interior-point algorithms primal-dual algorithms indefinite quadratic programming Newton-KKT

来源：评论

学校读者我要写书评

暂无评论

A group-strategyproof cost sharing mechanism for the steiner forest game

引用

SIAM JOURNAL ON COMPUTING 2008年第5期37卷 1319-1341页

作者： Koenemann, Jochen Leonardi, Stefano Schaefer, Guido van Zwam, Stefan H. M. Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Tech Univ Berlin Inst Math D-10623 Berlin Germany Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

We consider a game-theoretical variant of the Steiner forest problem in which each player j, out of a set of k players, strives to connect his terminal pair (s(j), t(j)) of vertices in an undirected, edge-weighted graph G. In this paper we show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein, and Ravi [SIAM J. Comput., 24 ( 1995), pp. 445-456] yields a 2-budget balanced and cross-monotonic cost sharing method for this game. We also present a negative result, arguing that no cross-monotonic cost sharing method can achieve a budget balance factor of less than 2 for the Steiner tree game. This shows that our result is tight. Our algorithm gives rise to a new linear programming relaxation for the Steiner forest problem which we term the lifted-cut relaxation. We show that this new relaxation is stronger than the standard undirected cut relaxation for the Steiner forest problem.

关键词： approximation algorithms mechanism design primal-dual algorithms Steiner forests group-strategyproofness

来源：评论

学校读者我要写书评

暂无评论

A New Randomized Block-Coordinate primal-dual Proximal Algorithm for Distributed Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第10期64卷 4050-4065页

作者： Latafat, Puya Freris, Nikolaos M. Patrinos, Panagiotis Katholieke Univ Leuven Dept Elect Engn ESAT STADIUS B-3001 Leuven Belgium IMT Sch Adv Studies Lucca I-55100 Lucca Italy Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230000 Anhui Peoples R China

This paper proposes Triangularly Preconditioned primal- dual algorithm, a new primal-dual algorithm for minimizing the sum of a Lipschitz-differentiable convex function and two possibly nonsmooth convex functions, one of which is composed with a linear mapping. We devise a randomized block-coordinate ( BC) version of the algorithm which converges under the same stepsize conditions as the full algorithm. It is shown that both the original as well as the BC scheme feature linear convergence rate when the functions involved are either piecewise linear-quadratic, or when they satisfy a certain quadratic growth condition (which is weaker than strong convexity). Moreover, we apply the developed algorithms to the problem of multiagent optimization on a graph, thus obtaining novel synchronous and asynchronous distributed methods. The proposed algorithms are fully distributed in the sense that the updates and the stepsizes of each agent only depend on local information. In fact, no prior global coordination is required. Finally, we showcase an application of our algorithm in distributed formation control.

关键词： Asynchronous algorithms block-coordinate (BC) minimization distributed optimization primal-dual algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Curvature integrals and iteration complexities in SDP and symmetric cone programs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2014年第3期57卷 623-665页

作者： Kakihara, Satoshi Ohara, Atsumi Tsuchiya, Takashi Natl Grad Inst Policy Studies Minato Ku Tokyo 1068677 Japan Univ Fukui Grad Sch Engn Fukui 9108507 Japan

In this paper, we study iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithms in SDP and symmetric cone programs by way of curvature integrals. The curvature integral is defined along the central path, reflecting the geometric structure of the central path. Integrating curvature along the central path, we obtain a precise estimate of the number of iterations to solve the problem. It has been shown for LP that the number of iterations is asymptotically precisely estimated with the integral divided by , where beta is the opening parameter of the neighborhood of the central path in MTY-PC algorithms. Furthermore, this estimate agrees quite well with the observed number of iterations of the algorithm even when beta is close to one and when applied to solve large LP instances from NETLIB. The purpose of this paper is to develop direct extensions of these two results to SDP and symmetric cone programs. More specifically, we give concrete formulas for curvature integrals in SDP and symmetric cone programs and give asymptotic estimates for iteration complexities. Through numerical experiments with large SDP instances from SDPLIB, we demonstrate that the number of iterations is explained quite well with the integral even for a large step size which is enough to solve practical large problems.

关键词： Interior-point methods primal-dual algorithms Path-following methods Iteration complexities Curvature Semidefinite programming Symmetric cone programs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：