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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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.

来源：评论

学校读者我要写书评

暂无评论

Practical Acceleration of the Condat-Vu Algorithm

引用

SIAM JOURNAL ON IMAGING SCIENCES 2024年第4期17卷 2076-2109页

作者： Driggs, Derek Ehrhardt, Matthias J. Schonlieb, Carola-Bibiane Tang, Junqi Univ Cambridge Dept Appl Math & Theoret Phys Cambridge CB3 0WA England Univ Bath Dept Math Sci Bath BA2 7AY England Univ Birmingham Sch Math Birmingham B15 2TT England

The Condat-Vu algorithm is a widely used primal-dual method for optimizing composite objectives of three functions. Several algorithms for optimizing composite objectives of two functions are special cases of Condat-Vu, including proximal gradient descent (PGD). It is well known that PGD exhibits suboptimal performance, and a simple adjustment to PGD can accelerate its convergence rate from O(1/T) to O(1/T-2) on convex objectives, and this accelerated rate is optimal. In this work, we show that a simple adjustment to the Condat-Vu algorithm allows it to recover accelerated PGD (APGD) as a special case, instead of PGD. We prove that this accelerated Condat-Vu algorithm achieves optimal convergence rates and significantly outperforms the traditional Condat-Vu algorithm in regimes where the Condat-Vu algorithm approximates the dynamics of PGD. We demonstrate the effectiveness of our approach in various applications in machine learning and computational imaging.

关键词： saddle-point problems primal-dual algorithms optimal methods convex optimization

来源：评论

学校读者我要写书评

暂无评论

FINDING SPARSE SOLUTIONS FOR PACKING AND COVERING SEMIDEFINITE PROGRAMS

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第2期32卷 321-353页

作者： Elbassioni, Khaled Makino, Kazuhisa Najy, Waleed Khalifa Univ Sci & Technol Abu Dhabi U Arab Emirates Kyoto Univ Res Inst Math Sci RIMS Kyoto 6068502 Japan New York Univ Abu Dhabi Abu Dhabi U Arab Emirates

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, which utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it may be desirable to obtain sparse dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a logarithmic-potential based algorithm of Grigoriadis et al. [SIAM J. Optim. 11 (2001), pp. 1081--1091] for packing/covering linear programs.

关键词： Key words semidefinite programs packing and covering logarithmic potential primal-dual algorithms approximate solutions robust packing and covering SDPs

来源：评论

学校读者我要写书评

暂无评论

Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization

引用

MATHEMATICAL PROGRAMMING 2019年第1-2期176卷 207-245页

作者： Hajinezhad, Davood Hong, Mingyi SAS Inst Cary NC USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA

In this paper, we propose a perturbed proximal primal-dual algorithm (PProx-PDA) for an important class of linearly constrained optimization problems, whose objective is the sum of smooth (possibly nonconvex) and convex (possibly nonsmooth) functions. This family of problems can be used to model many statistical and engineering applications, such as high-dimensional subspace estimation and the distributed machine learning. The proposed method is of the Uzawa type, in which a primal gradient descent step is performed followed by an (approximate) dual gradient ascent step. One distinctive feature of the proposed algorithm is that the primal and dual steps are both perturbed appropriately using past iterates so that a number of asymptotic convergence and rate of convergence results (to first-order stationary solutions) can be obtained. Finally, we conduct extensive numerical experiments to validate the effectiveness of the proposed algorithm.

关键词： Nonconvex optimization Nonsmooth optimization primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：