A primal-dual conjugate subgradient algorithm for large- scale/specially structured linear programming problems

This dissertation deals with a primal-dual conjugate subgradient-based algorithm for solving large-scale and/or specially structured linear programming problems. The proposed algorithm coordinates a Lagrangian dual function and a primal penalty function which satisfies a flexible set of specified properties, in order to generate a sequence of primal and dual iterates which can be shown to converge to an optimal pair of primal and dual solutions. Besides producing both primal and dual solutions, this coordination of primal and dual functions serves to guide the crucial choice of step-sizes in the iterative algorithm, and also provides a natural stopping criterion based on the duality gap. The generic algorithm maintains a considerable degree of flexibility which permits one to exploit any special structures inherent in the problem. Moreover, the algorithm admits a rich variety of admissible penalty functions and dual formulations in designing a particular implementation scheme. Other algorithmic strategies that can be gainfully employed to improve the performance of the algorithm include space-dilation and box step techniques, pattern search strategies and suboptimization based on complementary slackness conditions. The algorithm is tested on three different transportation problems with additional constraints which are faced by the Freight Equipment Management Program of the Association of American Railroads. Problem 1 is a maximin problem in which ∫(x) = minimum {∫,(x), r=1, ... , R} is maximized subject to the transportation constraints and a total cost constraint, where ∫, (·) is a savings function for the r^th railroad, for r=1, ... , R. Problem 2 minimizes weighted absolute deviations of ∫, (x); r=1, ... , R from its mean value subject to the Problem 1 constraint set. Problem 3, on the other hand, minimizes total cost subject to the transportation constraints and the constraint which requires each ∫, (x), r=1, ... , R to be at least at some desired level. Both theoretical issues concerning convergence properties and rates, as well as algorithmic design and computational performance issues are investigated. The results indicate that the algorithm is a viable strategy for these problems. In particular, a new conjugate gradient strategy emerges as a byproduct of this algorithm, which is shown to dominate other available strategies on standard test problems from the literature.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Industrial Engineering and Operations Research

Department dc:contributor.department

Industrial Engineering and Operations Research

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1988

Author dc:creator

• Ulular, Osman

Chair dc:contributor.committeechair

• Sherali, Hanif

Committee members dc:contributor.committeemember

• Frendewey, James O.
• Koelling, C. Patrick
• Sarin, Subhash C.
• Wang, C.C.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10919/77750

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/77750