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

Two "well-known" properties of subgradient optimization

MATHEMATICAL PROGRAMMING 2009年第1期120卷 213-220页

作者： Anstreicher, Kurt M. Wolsey, Laurence A. Univ Iowa Dept Management Sci Iowa City IA 52242 USA Univ Catholique Louvain Ctr Operat Res & Econometr B-1348 Louvain Belgium

The subgradient method is both a heavily employed and widely studied algorithm for non-differentiable optimization. Nevertheless, there are some basic properties of subgradient optimization that, while "well known" to specialists, seem to be rather poorly known in the larger optimization community. This note concerns two such properties, both applicable to subgradient optimization using the divergent series steplength rule. The first involves convergence of the iterative process, and the second deals with the construction of primal estimates when subgradient optimization is applied to maximize the Lagrangian dual of a linear program. The two topics are related in that convergence of the iterates is required to prove correctness of the primal construction scheme.

关键词： subgradient optimization Divergent series Lagrangian relaxation Primal recovery

来源：评论

学校读者我要写书评

暂无评论

A GENERALIZATION OF POLYAK CONVERGENCE RESULT FOR subgradient optimization

引用

MATHEMATICAL PROGRAMMING 1987年第3期37卷 309-317页

作者： ALLEN, E HELGASON, R KENNINGTON, J SHETTY, B TEXAS A&M UNIV DEPT BUSINESS ANALCOLLEGE STNTX 77843

This paper generalizes a practical convergence result first presented by Polyak. This new result presents a theoretical justification for the step size which has been successfully used in several specialized algorithm... 详细信息

关键词： subgradient optimization nonlinear programming convergence

来源：评论

学校读者我要写书评

暂无评论

Distributed online adaptive subgradient optimization with dynamic bound of learning rate over time-varying networks

引用

IET CONTROL THEORY AND APPLICATIONS 2022年第18期16卷 1834-1846页

作者： Fang, Runyue Li, Dequan Shen, Xiuyu Anhui Univ Sci & Technol Sch Math & Big Data Huaina Peoples R China Anhui Univ Sci & Technol Sch Artificial Intelligence Huainan 232000 Peoples R China Southeast Univ Sch Transportat Nanjing Peoples R China

Adaptive online optimization algorithms, such as Adam, RMSprop, and AdaBound, have recently been tremendously popular as they have been widely applied to address the issues in the field of deep learning. Despite their prevalence and prosperity, however, it is rare to investigate the distributed versions of these adaptive online algorithms. To fill the gap, a distributed online adaptive subgradient learning algorithm over time-varying networks, called DAdaxBound, which exponentially accumulates long-term past gradient information and possesses dynamic bounds of learning rates under learning rate clipping is developed. Then, the dynamic regret bound of DAdaxBound on convex and potentially nonsmooth objective functions is theoretically analysed. Finally, numerical experiments are carried out to assess the effectiveness of DAdaxBound on different datasets. The experimental results demonstrate that DAdaxBound compares favourably to other competing distributed online optimization algorithms.

关键词： time-varying networks distributed online adaptive subgradient learning algorithm possesses dynamic bounds subgradient optimization adaptive online algorithms gradient information deep learning learning (artificial intelligence) learning rate convex programming deep learning (artificial intelligence) optimisation adaptive online optimization algorithms rate clipping distributed versions competing distributed online gradient methods called dadaxbound dynamic regret

来源：评论

学校读者我要写书评

暂无评论

Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2019年第3期17卷 261-295页

作者： Haddadi, Salim 8 Mai 1945 Univ LabSTIC BP 401 Guelma 24000 Algeria

We propose a two-phase heuristic for the generalized assignment problem (GAP). The first phase-a generic variable-fixing method-heuristically eliminates up to 98% of the variables without sacrificing the solution quality. The second phase takes as input the small reduced GAP obtained during the first phase and applies a very large scale neighborhood search. The definition of the successive exponential size neighborhoods is guided by the subgradient method applied to the Lagrangian relaxation of the knapsack constraints via the reduced costs. Searching the proposed neighborhood is NP-hard and amounts to solving a monotone binary program (BP) with m constraints and p variables, where m and p are respectively the number of agents and tasks of the reduced GAP (monotone BPs are BPs with two nonzero coefficients of opposite sign per column). To the best of our knowledge, this is the first time the above ideas are exposed. Extensive testing on large scale GAP instances is presented and previously unknown better values for eight instances are obtained. Comparison to well-established methods shows that this new approach is competitive and constitutes a substantial addition to the arsenal of tools for solving GAP.

关键词： Generalized assignment Variable-fixing VLSN search subgradient optimization Monotone binary program

来源：评论

学校读者我要写书评

暂无评论

Validation of subgradient optimization

引用

Mathematical Programming 1974年第1期6卷 62-88页

作者： Held, Michael Wolfe, Philip Crowder, Harlan P. IBM Systems Research Institute New York United States IBM Watson Research Center Yorktown Heights New York United States

The “relaxation” procedure introduced by Held and Karp for approximately solving a large linear programming problem related to the traveling-salesman problem is refined and studied experimentally on several classes of specially structured large-scale linear programming problems, and results on the use of the procedure for obtaining exact solutions are given. It is concluded that the method shows promise for large-scale linear programming © 1974, The Mathematical Programming Society. All rights reserved.

关键词： Exact Solution Mathematical Method Programming Problem Linear Programming Problem subgradient optimization

来源：评论

学校读者我要写书评

暂无评论

Lagrangean relaxation and subgradient optimization applied to optimal design with discrete sizing

引用

Engineering optimization 1990年第3期16卷 221-233页

作者： Ŏrjan, Jonsson Torbjörn, Larsson Department of Mathematics Linköping Institute of Technology S-581 83 Linköping Sweden

The discrete sizing problem in optimal design is adressed. Lagrangean dual approaches earlier published are briefly reviewed and it is noted that quite sophisticated procedures have been used to solve the dual problems. The simple concept of Lagrangean relaxation combined with subgradient optimization and Lagrangean heuristics has, however, not been applied to the discrete sizing problem. In this paper a scheme based on this concept is described and tested on some small problems. The results indicate that subgradient optimization is completely capable of solving the dual problem. Moreover it is possible to devise heuristics that construct feasible solutions to the original problem, using the Lagrangean subproblem solution. © 1990, Taylor & Francis Group, LLC. All rights reserved.

关键词： discrete variables Lagrangean duality optimal design structural optimization subgradient optimization

来源：评论

学校读者我要写书评

暂无评论

Primal convergence from dual subgradient methods for convex optimization

引用

MATHEMATICAL PROGRAMMING 2015年第2期150卷 365-390页

作者： Gustavsson, Emil Patriksson, Michael Stromberg, Ann-Brith Chalmers Univ Technol Dept Math Sci S-41296 Gothenburg Sweden Univ Gothenburg Dept Math Sci S-41296 Gothenburg Sweden

When solving a convex optimization problem through a Lagrangian dual reformulation subgradient optimization methods are favorably utilized, since they often find near-optimal dual solutions quickly. However, an optimal primal solution is generally not obtained directly through such a subgradient approach unless the Lagrangian dual function is differentiable at an optimal solution. We construct a sequence of convex combinations of primal subproblem solutions, a so called ergodic sequence, which is shown to converge to an optimal primal solution when the convexity weights are appropriately chosen. We generalize previous convergence results from linear to convex optimization and present a new set of rules for constructing the convexity weights that define the ergodic sequence of primal solutions. In contrast to previously proposed rules, they exploit more information from later subproblem solutions than from earlier ones. We evaluate the proposed rules on a set of nonlinear multicommodity flow problems and demonstrate that they clearly outperform the ones previously proposed.

关键词： Convex programming Lagrangian duality subgradient optimization Ergodic convergence Primal recovery Nonlinear multicommodity flow problem

来源：评论

学校读者我要写书评

暂无评论

A RANDOMIZED INCREMENTAL subgradient METHOD FOR DISTRIBUTED optimization IN NETWORKED SYSTEMS

引用

SIAM JOURNAL ON optimization 2009年第3期20卷 1157-1170页

作者： Johansson, Bjorn Rabi, Maben Johansson, Mikael Royal Inst Technol KTH Sch Elect Engn S-10044 Stockholm Sweden

We present an algorithm that generalizes the randomized incremental subgradient method with fixed stepsize due to Nedic and Bertsekas [SIAM J. Optim., 12 (2001), pp. 109-138]. Our novel algorithm is particularly suitable for distributed implementation and execution, and possible applications include distributed optimization, e.g., parameter estimation in networks of tiny wireless sensors. The stochastic component in the algorithm is described by a Markov chain, which can be constructed in a distributed fashion using only local information. We provide a detailed convergence analysis of the proposed algorithm and compare it with existing, both deterministic and randomized, incremental subgradient methods.

关键词： convex programming subgradient optimization distributed optimization Markov chain

来源：评论

学校读者我要写书评

暂无评论

The efficiency of subgradient projection methods for convex optimization .1. General level methods

引用

SIAM JOURNAL ON CONTROL AND optimization 1996年第2期34卷 660-676页

作者： Kiwiel, KC Systems Research Institute 01-447 Warsaw Newelska 6 Poland

We study subgradient methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We present several variants and show that they enjoy almost optimal efficiency estimates. In another paper we discuss possible implementations of such methods. In particular, their projection subproblems may he solved inexactly via relaxation methods, thus opening the way for parallel implementations. They can also exploit accelerations of relaxation methods based on simultaneous projections, surrogate constraints, and conjugate and projected (conditional) subgradient techniques.

关键词： nondifferentiable (nonsmooth) optimization convex programming relaxation methods subgradient optimization successive projections linear inequalities parallel computing

来源：评论

学校读者我要写书评

暂无评论

Convergence of approximate and incremental subgradient methods for convex optimization

引用

SIAM JOURNAL ON optimization 2004年第3期14卷 807-840页

作者： Kiwiel, KC Polish Acad Sci Syst Res Inst PL-01447 Warsaw Poland

We present a unified convergence framework for approximate subgradient methods that covers various stepsize rules (including both diminishing and nonvanishing stepsizes), convergence in objective values, and convergence to a neighborhood of the optimal set. We discuss ways of ensuring the boundedness of the iterates and give efficiency estimates. Our results are extended to incremental subgradient methods for minimizing a sum of convex functions, which have recently been shown to be promising for various large-scale problems, including those arising from Lagrangian relaxation.

关键词： nondifferentiable optimization convex programming subgradient optimization approximate subgradients efficiency

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：