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

Limited memory space dilation and reduction algorithms

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2001年第1期19卷 55-77页

作者： Sherali, HD Choi, G Ansari, Z Virginia Polytech Inst & State Univ Dept Ind & Syst Engn 0118 Blacksburg VA 24061 USA Hanyang Univ Dept Ind Engn Seoul 133791 South Korea

In this paper, we present variants of Shor and Zhurbenko's r-algorithm, motivated by the memoryless and limited memory updates for differentiable quasi-Newton methods. This well known r-algorithm, which employs a space dilation strategy in the direction of the difference between two successive subgradients, is recognized as being one of the most effective procedures for solving nondifferentiable optimization problems. However, the method needs to store the space dilation matrix and update it at every iteration, resulting in a substantial computational burden for large-sized problems. To circumvent this difficulty, we first propose a memoryless update scheme, which under a suitable choice of parameters, yields a direction of motion that turns out to be a convex combination of two successive anti-subgradients. Moreover, in the space transformation sense, the new update scheme can be viewed as a combination of space dilation and reduction operations. We prove convergence of this new method, and demonstrate how it can be used in conjunction with a variable target value method that allows a practical, convergent implementation of the method. We also examine a memoryless variant that uses a fixed dilation parameter instead of varying degrees of dilation and/or reduction as in the former algorithm, as well as another variant that examines a two-step limited memory update. These variants are tested along with Shor's r-algorithm and also a modified version of a related algorithm due to Polyak that employs a projection onto a pair of Kelley's cutting planes. We use a set of standard test problems from the literature as well as randomly generated dual transportation and assignment problems in our computational experiments. The results exhibit that the proposed space dilation and reduction method and the modification of Polyak's method are competitive, and offer a substantial advantage over the r-algorithm and over the other tested limited memory variants with respect to accura

关键词： nondifferentiable optimization subgradient algorithm space dilation operator memoryless update limited memory update variable target value method

来源：评论

学校读者我要写书评

暂无评论

Low-Complexity LP Decoding of Nonbinary Linear Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2013年第8期61卷 3073-3085页

作者： Punekar, Mayur Vontobel, Pascal O. Flanagan, Mark F. Texas A&M Univ Dept Elect & Comp Engn Doha Qatar Hewlett Packard Labs Palo Alto CA 94304 USA Univ Coll Dublin Sch Elect Elect & Commun Engn Dublin Ireland

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z(4), GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.

关键词： Linear programming decoding nonbinary codes LDPC codes coordinate-ascent algorithm subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

Dual approaches to finite element model updating

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2012年第7期236卷 1851-1861页

作者： Yuan, Quan Nanjing Univ Aeronaut & Astronaut Dept Math Nanjing 210016 Jiangsu Peoples R China

The problem of finding the least change adjustment to a stiffness matrix modeled by finite element method is considered in this paper. Desired stiffness matrix properties such as symmetry, sparsity, positive semidefiniteness, and satisfaction of the characteristic equation are imposed as side constraints of the constructed optimal matrix approximation for updating the stiffness matrix, which matches measured data better. The dual problems of the original constrained minimization are presented and solved by subgradient algorithms with different line search strategies. Some numerical results are included to illustrate the performance and application of the proposed methods. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Model updating Optimal matrix approximation Dual problem subgradient algorithm Line search

来源：评论

学校读者我要写书评

暂无评论

Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem

引用

DISCRETE APPLIED MATHEMATICS 2006年第15期154卷 2200-2211页

作者： Thiongane, Babacar Nagih, Anass Plateau, Gerard Univ Paris 13 Lab Informat Paris Nord UMR 7030 CNRS F-93430 Villetaneuse France

First, this paper deals with lagrangean heuristics for the 0-1 bidimensional knapsack problem. A projected subgradient algorithm is performed for solving a lagrangean dual of the problem, to improve the convergence of the classical subgradient algorithm. Secondly, a local search is introduced to improve the lower bound on the value of the biknapsack produced by lagrangean heuristics. Thirdly, a variable fixing phase is embedded in the process. Finally, the sequence of 0-1 one-dimensional knapsack instances obtained from the algorithm are solved by using reoptimization techniques in order to reduce the total computational time effort. Computational results are presented. (c) 2006 Elsevier B.V. All rights reserved.

关键词： 0-1 knapsack Lagrangean relaxation subgradient algorithm local search reoptimization

来源：评论

学校读者我要写书评

暂无评论

Optimal Power Control in Green Wireless Sensor Networks With Wireless Energy Harvesting, Wake-Up Radio and Transmission Control

引用

IEEE ACCESS 2017年 5卷 501-518页

作者： Mahapatra, Chinmaya Sheng, Zhengguo Kamalinejad, Pouya Leung, Victor C. M. Mirabbasi, Shahriar Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada Univ Sussex Dept Engn & Design Brighton BN1 9RH E Sussex England

Wireless sensor networks (WSNs) are autonomous networks of spatially distributed sensor nodes that are capable of wirelessly communicating with each other in a multihop fashion. Among different metrics, network lifetime and utility, and energy consumption in terms of carbon footprint are key parameters that determine the performance of such a network and entail a sophisticated design at different abstraction levels. In this paper, wireless energy harvesting (WEH), wake-up radio (WUR) scheme, and error control coding (ECC) are investigated as enabling solutions to enhance the performance of WSNs while reducing its carbon footprint. Specifically, a utility-lifetime maximization problem incorporating WEH, WUR, and ECC, is formulated and solved using distributed dual subgradient algorithm based on the Lagrange multiplier method. Discussion and verification through simulation results show how the proposed solutions improve network utility, prolong the lifetime, and pave the way for a greener WSN by reducing its carbon footprint.

关键词： Green wireless sensor network (GWSN) wireless energy harvesting (WEH) wake-up radio (WUR) error control coding (ECC) subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

Ergodic, primal convergence in dual subgradient schemes for convex programming, II: the case of inconsistent primal problems

引用

MATHEMATICAL PROGRAMMING 2017年第1-2期163卷 57-84页

作者： Onnheim, Magnus Gustavsson, Emil Stromberg, Ann-Brith Patriksson, Michael Larsson, Torbjorn Chalmers Univ Technol Dept Math Sci S-41296 Gothenburg Sweden Univ Gothenburg S-41296 Gothenburg Sweden Linkoping Univ Div Optimizat Dept Math S-58183 Linkoping Sweden

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal-dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which-in the inconsistent case-the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized;the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional epsilon-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions;this composite algorithm yields convergence of the primal-dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function;for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.

关键词： Inconsistent convex program Lagrange dual Homogeneous Lagrangian function subgradient algorithm Ergodic primal sequence

来源：评论

学校读者我要写书评

暂无评论

An Adjustable Robust Two-stage Stochastic Quadric Programming and its Solution with subgradient algorithms 22

An Adjustable Robust Two-stage Stochastic Quadric Programmin...

引用

Proceedings of the 6th International Conference on algorithms, Computing and Systems

作者： Xinshun Ma Qi An Department of Mathematics and Physics North China Electric Power University China

ISBN: (纸本)9781450397407

Robust stochastic optimization provides a worst-case decision-making scheme under uncertain probability distributions, but the results could be too conservative and pessimistic. This paper establishes a class of adjustable robust two-stage stochastic quadratic programming based on a parameter-related affine uncertain set. The convexity of the problem is verified, and the subdifferential is obtained. An improved subgradient algorithm is proposed for solving the problem based on a deflected subgradient direction and a step-size strategy with exponential decay. The convergence of the algorithm is proved, and the numerical examples demonstrate the effectiveness. The calculation results show that the adjustable robust stochastic programming is related to the parameter-related, and the optima value decreases as the parameter increases. The approach can provide decision-makers with more optimistic solutions besides the worst-case ones.

关键词： subgradient algorithm Robust stochastic programming Two-stage stochastic programming Linear partial information

来源：评论

学校读者我要写书评

暂无评论

A Primal-Dual Heuristic for a Heterogeneous Unmanned Vehicle Path Planning Problem Regular Paper

引用

INTERNATIONAL JOURNAL OF ADVANCED ROBOTIC SYSTEMS 2013年第10期10卷

作者： Sundar, Kaarthik Rathinam, Sivakumar Texas A&M Univ College Stn TX 77843 USA

We consider a path planning problem where a team of Unmanned Vehicles (UVs) is required to visit a given set of targets. The UVs are assumed to carry different sensors, and as a result, there are vehicle-target constraints that require each UV to visit a distinct subset of targets. The objective of the path planning problem is to find a path for each UV such that each target is visited at least once by some vehicle, the vehicle-target constraints are satisfied and the total distance travelled by the vehicles is a minimum. This path planning problem is a generalization of the Hamiltonian path problem and is NP-Hard. We develop a primal-dual heuristic and incorporate the heuristic in a Lagrangian relaxation procedure to find good, feasible solutions and lower bounds for the path planning problem. Computational results show that solutions whose costs are on an average within 14% of the optimum can be obtained relatively quickly for the path planning problem involving five UVs and 40 targets.

关键词： Unmanned Vehicle Hamiltonian Path Problem Primal-Dual Method Lagrangian Relaxation subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed algorithms for maximum lifetime routing in wireless sensor networks

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2006年第8期5卷 2185-2193页

作者： Madan, Ritesh Lall, Sanjay Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Aeronaut & Astronaut Stanford CA 94035 USA

A sensor network of nodes with wireless transceiver capabilities and limited energy is considered. We propose distributed algorithms to compute an optimal routing scheme that maximizes the time at which the first node in the network drains out of energy. The problem is formulated as a linear programming problem and subgradient algorithms are used to solve it in a distributed manner. The resulting algorithms have low computational complexity and are guaranteed to converge to an optimal routing scheme that maximizes the network lifetime. The algorithms are illustrated by an example in which an optimal flow is computed for a network of randomly distributed nodes. We also show how our approach can be used to obtain distributed algorithms for many different extensions to the problem. Finally, we extend our problem formulation to more general definitions of network lifetime to model realistic scenarios in sensor networks.

关键词： routing linear programming dual decomposition subgradient algorithm sensor networks network lifetime

来源：评论

学校读者我要写书评

暂无评论

PATHOLOGICAL subgradient DYNAMICS

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第2期30卷 1327-1338页

作者： Daniilidis, Aris Drusvyatskiy, Dmitriy Univ Chile Dept Engn Math DIM CMM UMI CNRS 2807FCFM Beauchef 851 Santiago 8370459 Chile Univ Washington Dept Math Seattle WA 98195 USA

We construct examples of Lipschitz continuous functions, with pathological subgradient dynamics in both continuous and discrete time. In both settings, the iterates generate bounded trajectories and yet fail to detect... 详细信息

关键词： subgradient algorithm Lipschitz function Clarke subdifferential splitting set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：