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

On embedding the volume algorithm in a variable target value method

OPERATIONS RESEARCH LETTERS 2004年第5期32卷 455-462页

作者： Sherali, HD Lim, C Virginia Polytech Inst & State Univ Grado Dept Ind & Syst Engn Blacksburg VA 24061 USA

We employ the volume algorithm as a subgradient deflection strategy in a variable target value method for solving nondifferentiable optimization problems. Focusing on Lagrangian duals for LPs, we exhibit primal nonconvergence of the original method, establish convergence of the proposed algorithm in the dual space, and present related computational results. (C) 2004 Elsevier B.V. All rights reserved.

关键词： nondifferentiable optimization Lagrangian relaxation variable target value method volume algorithm

来源：评论

学校读者我要写书评

暂无评论

A variable target value method for nondifferentiable optimization

引用

OPERATIONS RESEARCH LETTERS 2000年第1期26卷 1-8页

作者： Sherali, HD Choi, G Tuncbilek, CH Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA

This paper presents a new variable target value method (VTVM) that can be used in conjunction with pure or deflected subgradient strategies. The proposed procedure assumes no a priori knowledge regarding bounds on the optimal value. The target values are updated iteratively whenever necessary, depending on the information obtained in the process of the algorithm. Moreover, convergence of the sequence of incumbent solution values to a near-optimum is proved using popular, practically desirable step-length rules. In addition, the method also allows a wide flexibility in designing subgradient deflection strategies by imposing only mild conditions on the deflection parameter. Some preliminary computational results are reported on a set of standard test problems in order to demonstrate the viability of this approach. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： nondifferentiable optimization subgradient algorithm conjugate subgradient methods deflected subgradient directions variable target value method

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Solving Euclidean distance multifacility location problems using conjugate subgradient and line-search methods

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1999年第3期14卷 275-291页

作者： Sherali, HD Al-Loughani, I Virginia Polytech Inst & State Univ Dept Ind & Syst Engn 0118 Blacksburg VA 24061 USA

Subgradient methods are popular for solving nondifferentiable optimization problems because of their relative ease in implementation, but are not always robust and require a careful design of strategies in order to yield an effective procedure for any given class of problems. In this paper, we present an approach for solving the Euclidean distance multifacility location problem (EMFLP) using conjugate or deflected subgradient based algorithms along with suitable line-search strategies. The subgradient deflection method considered is the Average Direction Strategy (ADS) imbedded within the variable target value method (VTVM). We also investigate the generation of two types of subgradients to be employed in conjunction with ADS. The first type is a simple valid subgradient that assigns zero values to contributions corresponding to the nondifferentiable terms in the objective function, and so, the subgradient is composed by summing the contributions corresponding to the differentiable terms alone. The second type expends more effort to derive a low-norm member of the subdifferential in order to enhance the prospect of obtaining a descent direction. Furthermore, a special Newton-based line-search that exploits the nondifferentiability of the problem is also designed to be implemented in the developed algorithm in order to study its impact on the convergence behavior. Various combinations of the above strategies are composed and evaluated on a set of test problems. The results show that a modification of the VTVM method along with the first or a certain combination of the two subgradient generation strategies, and the use of a suitable line-search technique, provides promising results. An alternative block-halving step-size strategy used within VTVM in conjunction with the proposed line-search method yields a competitive second choice performance.

关键词： Euclidean multifacility location problem nondifferentiable optimization conjugate subgradient methods variable target value method inexact line-search

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：