New development of the inclusive-cone-based method for linear optimization

Ding, M 2014, New development of the inclusive-cone-based method for linear optimization, Doctor of Philosophy (PhD), Mathematical and Geospatial Sciences, RMIT University.


Document type: Thesis
Collection: Theses

Attached Files
Name Description MIMEType Size
Ding.pdf Thesis application/pdf 661.51KB
Title New development of the inclusive-cone-based method for linear optimization
Author(s) Ding, M
Year 2014
Abstract The purpose of this dissertation is to present a simple method for linear optimization including linear programming and linear semi-infinite programming, which is termed “the inclusive-cone-based method”. Using the inclusive cone as an analytic tool, theoretical aspects of linear programming are investigated. Sensitivity analysis in linear programming is examined from the perspective of an inclusive cone. The relationship of inclusiveness between correlated linear programming problems is also studied. New inclusive-cone-based ladder algorithms are proposed to solve linear programming problems in inequality form. Numerical experiments are implemented to show effectiveness and efficiency of the new linear programming ladder algorithms. To start the ladder method for linear programming problems, a single artificial constraint technique is introduced to find an initial ladder. Further, in the context of a new category of linear programming problems, an inclusive-cone-based solvability criterion is established to distinguish that a linear programming problem is inclusive-feasible (i.e., optimal), noninclusive-feasible (i.e., unbounded), inclusive-infeasible or noninclusive-infeasible. The inclusive-cone-based method for linear programming is also generalized to linear semi-infinite programming. An optimality result, based upon the concept of the generalized base point, is established. With this optimality result as a theoretical foundation, a ladder algorithm for solving linear semi-infinite programming problems is developed. The new algorithm has several features: at each iteration it only deals with a small fraction of constraints; at each iteration it selects a constraint most violated along a “parameterized centreline”, by solving a one-dimensional global optimization problem using the efficient bridging algorithm; at each iteration the selection of the incoming constraint has a great degree of freedom, which is controlled by a parameter arising in the global optimization problem; it can detect infeasibility and unboundedness after a finite number of iterations; it obviates extra work for feasibility verification as it handles feasibility and optimality simultaneously. A simple convergent result is presented. Numerical behaviour of the algorithm is examined on several test problems.
Degree Doctor of Philosophy (PhD)
Institution RMIT University
School, Department or Centre Mathematical and Geospatial Sciences
Keyword(s) Linear programming
Linear semi-infinite programming
Inclusive cone
Ladder algorithms
Optimality
Versions
Version Filter Type
Access Statistics: 227 Abstract Views, 183 File Downloads  -  Detailed Statistics
Created: Fri, 02 May 2014, 10:43:22 EST by Keely Chapman
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us