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

A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms

引用

MATHEMATICAL PROGRAMMING 2008年第1期115卷 105-149页

作者： Monteiro, Renato D. C. Tsuchiya, Takashi Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Inst Stat Math Minato Ku Tokyo 1068569 Japan

The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and;ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m x n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of O(n(2)) long but straight continuous parts while the remaining curved part is relatively "short".

关键词： interior-point algorithms primal-dual algorithms path-following central path layered least squares steps condition number polynomial complexity crossover events scale-invariance predictor-corrector affine scaling strongly polynomial linear programming curvature

来源：评论

学校读者我要写书评

暂无评论

primal-dual path-following algorithms for semidefinite programming

引用

SIAM JOURNAL ON OPTIMIZATION 1997年第3期7卷 663-678页

作者： Monteiro, RDC Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper deals with a class of primal-dual interior-point algorithms for semidefinite programming (SDP) which was recently introduced by Kojima, Shindoh, and Kara [SIAM J. Optim., 7 (1997), pp. 86-125]. These authors proposed a family of primal-dual search directions that generalizes the one used in algorithms for linear programming based on the scaling matrix (XS-1/2)-S-1/2. They study three primal-dual algorithms based on this family of search directions: a short-step path-following method, a feasible potential-reduction method, and an infeasible potential-reduction method. However, they were not able to provide an algorithm which generalizes the long-step path-following algorithm introduced by Kojima, Mizuno, and Yoshise [Progress in Mathematical Programming: Interior Point and Related Methods, N. Megiddor, ed., Springer-Verlag, Berlin, New York, 1989, pp. 29-47]. In this paper, we characterize two search directions within their family as being (unique) solutions of systems of linear equations in symmetric variables. Based on this characterization, we present a simplified polynomial convergence proof for one of their short-step path-following algorithms and, for the first time, a polynomially convergent long-step path-following algorithm for SDP which requires an extra root n factor in its iteration-complexity order as compared to its linear programming counterpart, where n is the number of rows (or columns) of the matrices involved.

关键词： semidefinite programming interior-point methods polynomial complexity path-following methods primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Monotonicity of primal-dual interior-point algorithms for semidefinite programming problems

引用

OPTIMIZATION METHODS & SOFTWARE 1998年第2期10卷 275-296页

作者： Kojima, M Tunçel, L Tokyo Inst Technol Dept Math & Informat Sci Meguro Ku Tokyo 152 Japan Univ Waterloo Fac Math Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We present primal-dual interior-point algorithms with polynomial iteration bounds to find approximate solutions of semidefinite programming problems. Our algorithms achieve the current best iteration bounds and, in ev... 详细信息

关键词： semidefinite programming interior-point methods primal-dual algorithms monotonicity of objective values search directions polynomial complexity

来源：评论

学校读者我要写书评

暂无评论

Monotonicity of primal-dual Interior-point algorithms for Semidefinite Programming Problems

引用

Optimization Methods and Software 1999年第2期10卷 275-296页

作者： Kojima, Masakazu Tuncel, Levent Dept. of Math. and Info. Sciences Tokyo Institute of Technology 2-12-1 Oh-Okayama Meguro-ku Tokyo 152 Japan Dept. Combinatorics and Optimization Faculty of Mathematics University of Waterloo Waterloo Ont. N2L 3G1 Canada

关键词： Semidefinite programming Interior-point methods primal-dual algorithms Monotonicity of objective values Search directions Polynomial complexity

来源：评论

学校读者我要写书评

暂无评论

On the ergodic convergence rates of a first-order primal-dual algorithm

引用

MATHEMATICAL PROGRAMMING 2016年第1-2期159卷 253-287页

作者： Chambolle, Antonin Pock, Thomas CNRS Ecole Polytech CMAP F-91128 Palaiseau France Graz Univ Technol Inst Comp Graph & Vis A-8010 Graz Austria AIT Austrian Inst Technol GmbH Digital Safety & Secur Dept A-1220 Vienna Austria

We revisit the proofs of convergence for a first order primal-dual algorithm for convex optimization which we have studied a few years ago. In particular, we prove rates of convergence for a more general version, with simpler proofs and more complete results. The new results can deal with explicit terms and nonlinear proximity operators in spaces with quite general norms.

关键词： Saddle-point problems First order algorithms primal-dual algorithms Convergence rates Ergodic convergence

来源：评论

学校读者我要写书评

暂无评论

Approximate proof-labeling schemes

引用

THEORETICAL COMPUTER SCIENCE 2020年 811卷 112-124页

作者： Censor-Hillel, Keren Paz, Ami Perry, Mor Technion Dept Comp Sci Haifa Israel CNRS IRIF Paris France Univ Paris Diderot Paris France Tel Aviv Univ Dept Elect Engn Tel Aviv Israel

We study a new model of verification of boolean predicates over distributed networks. Given a network configuration, the proof-labeling scheme (PIS) model defines a distributed proof in the form of a label that is given to each node, and all nodes locally verify that the network configuration satisfies the desired boolean predicate by exchanging labels with their neighbors. The proof size of the scheme is defined to be the maximum size of a label. In this work, we extend this model by defining the approximate proof-labeling scheme (APIS) model. In this new model, the predicates for verification are of the form psi <= phi, where psi, phi : F -> N for a family of configurations F. Informally, the predicates considered in this model are a comparison between two values of the configuration. As in the PLS model, nodes exchange labels in order to locally verify the predicate, and all must accept if the network satisfies the predicate. The soundness condition is relaxed with an approximation ration alpha, so that only psi > alpha phi) some node must reject. We focus on two verification problems: upper and lower bounds on the diameter of the graph, and the maximality of a given matching. For these problems, we present the first results that apply to all graph structures. In our new APLS model, we show that the proof size can be much smaller than the proof size of the same predicate in the PLS model. Moreover, we prove that there is a tradeoff between the approximation ratio and the proof size. Finally, we present the first general result for maximum cardinality matching in the PLS model. (C) 2018 Published by Elsevier B.V.

关键词： Distributed graph algorithms Distributed verification Approximation algorithms primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving a non-smooth eigenvalue problem using operator-splitting methods

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2007年第6期84卷 825-846页

作者： Majava, K. Glowinski, R. Karkkainen, T. Univ Jyvaskyla Dept Math Informat Technol SF-40014 Jyvaskyla Finland Univ Houston Dept Math Houston TX 77204 USA

In this paper, we study the solution of a certain non-smooth eigenvalue problem, using operator-splitting methods to solve an equivalent, constrained minimization problem. We present the Marchuk-Yanenko and Peaceman-Rachford schemes for solving the problem and compare their performance numerically on some model problems. The Peaceman-Rachford scheme turns out to be superior to the Marchuk Yanenko scheme in terms of accuracy and computational efficiency.

关键词： constrained optimization nonsmooth eigenvalue problem operator-splitting methods primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

A POLYNOMIAL PREDICTOR-CORRECTOR TRUST-REGION ALGORITHM FOR LINEAR PROGRAMMING

引用

SIAM JOURNAL ON OPTIMIZATION 2009年第4期19卷 1918-1946页

作者： Lan, Guanghui Monteiro, Renato D. C. Tsuchiya, Takashi Georgia Inst Technol Sch ISyE Atlanta GA 30332 USA Inst Stat Math Minato Ku Tokyo 1068569 Japan

In this paper we present a scaling-invariant, interior-point, predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling (AS) direction or a new trust-region type direction, whose construction depends on a scaling-invariant bipartition of the variables determined by the AS direction. This contrasts with the layered least squares direction introduced in S. Vavasis and Y. Ye [Math. Program., 74 (1996), pp. 79-120], whose construction depends on multiple-layered partitions of the variables that are not scaling-invariant. Moreover, it is shown that the overall arithmetic complexity of the algorithm (weakly) depends on the right-hand side and the cost of the LP in view of the work involved in the computation of the trust region steps.

关键词： interior-point algorithms primal-dual algorithms path-following trust-region central path layered steps condition number polynomial complexity predictor-corrector affine scaling strongly polynomial linear programming

来源：评论

学校读者我要写书评

暂无评论

On stackelberg pricing with computationally bounded customers

引用

NETWORKS 2012年第1期60卷 31-44页

作者： Briest, Patrick Guala, Luciano Hoefer, Martin Ventre, Carmine Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Roma Tor Vergata Dipartimento Matemat I-00173 Rome Italy Univ Paderborn Dept Comp Sci Paderborn Germany

In Stackelberg pricing a leader sets prices for items to maximize revenue from a follower purchasing a feasible subset of items. We consider computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but who apply publicly known algorithms to determine the items to purchase. This corresponds to general multidimensional pricing when customers cannot optimize their valuation functions efficiently but still aim to act rationally to the best of their ability. We consider two versions of this novel type of pricing problem. In the MIn-KNAPSACK variant items are weighted objects and the follower seeks to purchase a min-cost selection of objects of some bounded weight. When he uses a greedy 2-approximation algorithm, we provide a polynomial-time (2+e) -approximation algorithm for the leader's revenue maximization problem based on so-called near-uniform price assignments. We also prove the problem to be strongly NP-hard. In the SET-COVER variant items are subsets of some ground set which the follower seeks to cover. When he uses a standard primal-dual approach, we prove that exact revenue maximization is possible in polynomial time when elements have frequency 2 (VERTEX-COVER variant). This stands in sharp contrast to APX-hardness for the problem with elements of frequency 3. (c) 2011 Wiley Periodicals, Inc. NETWORKS, 2012

关键词： algorithmic pricing Stackelberg game Knapsack set cover primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

A new iteration-complexity bound for the MTY predictor-corrector algorithm

引用

SIAM JOURNAL ON OPTIMIZATION 2005年第2期15卷 319-347页

作者： Monteiro, RDC Tsuchiya, T Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Inst Stat Math Minato Ku Tokyo 1068569 Japan

In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program min{c(T)x : Ax = b, x >= 0} with decision variable x is an element of R(n), we show that the MTY P-C algorithm, started from a well-centered interior-feasible solution with duality gap n mu(0), finds an interior-feasible solution with duality gap less than n eta in O(T(mu(0)/eta) + n(3.5) log((chi) over bar (A)*)) iterations, where T(t) = min{n(2) log(log t), log t} for all t > 0 and (chi) over bar (A)* is a scaling invariant condition number associated with the matrix A. More specifically, (chi) over bar (A)* is the infimum of all the conditions numbers (chi) over bar (AD), where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O(n(3.5) L(A) + min{n(2) log L, L}) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where LA and L are the input sizes of the matrix A and the data (A, b, c), respectively. This contrasts well with the classical iteration- complexity bound for the MTY P-C algorithm, which depends linearly on L instead of log L.

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：