Type of Document	Master's Thesis
Author	Ansari, Zafar A.
Author's Email Address	zafaransari@hotmail.com
URN	etd-61498-16858
Title	Limited Memory Space Dilation and Reduction Algorithms
Degree	Master of Science
Department	Industrial and Systems Engineering
Advisory Committee	Advisor Name Title Sherali, Hanif D. Committee Chair Loganathan, G. V. Committee Member Sarin, Subhash C. Committee Member
Keywords	r-algorithm Space Dilation Nondifferentiable Optimization Subgradient Optimization
Date of Defense	1998-07-13
Availability	unrestricted
Abstract (ABSTRACT) In this thesis, 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 develop a memoryless update scheme. 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 algorithm, and demonstrate how it can be used in conjunction with a variable target value method that allows a practical, convergent implementation of the method. For performance comparisons we examine other memoryless and limited memory variants, and also prove a modification of a related algorithm due to Polyak that employs a projection on a pair of Kelley's cutting planes. These variants are tested along with Shor's r-algorithm on a set of standard test problems from the literature as well as on randomly generated dual transportation and assignment problems. Our computational experiments reveal that the proposed memoryless space dilation and reduction algorithm (VT-MSDR) and the proposed modification of the Polyak-Kelly cutting plane method (VT-PKC) provide an overall competitive performance relative to the other methods tested with respect to solution quality and computational effort. The r-Algorithm becomes increasingly more expensive with an increase in problem size, while not providing any gain in solution quality. The fixed dilation (with no reduction) strategy (VT-MSD) provides a comparable, though second-choice, alternative to VT-MSDR. Employing a two-step limited memory extension over VT-MSD sometimes helps in improving the solution quality, although it adds to computational effort, and is not as robust a procedure.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    th.pdf 205.72 Kb 00:00:57 00:00:29 00:00:25 00:00:12 00:00:01

If you have questions or technical problems, please Contact DLA.