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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：