A dissertation submitted to the Faculty of Science School of Computational and Applied Mathematics, University of the Witwatersrand,
Johannesburg. April 27, 2013. / In a number of situations the derivative of the objective function of an optimization
problem is not available. This thesis presents a novel algorithm
for solving mixed integer programs when this is the case. The algorithm
is the first developed for problems of this type which uses a trust region
methodology. Three implementations of the algorithm are developed and
deterministic proofs of convergence to local minima are provided for two of
the implementations.
In the development of the algorithm several other contributions are made.
The derivative free algorithm requires the solution of several mixed integer
quadratic programming subproblems and novel methods for solving nonconvex
instances of these problems are developed in this thesis. Additionally,
it is shown that the current definitions of local minima for mixed integer programs
are deficient and a rigorous approach to developing possible definitions
is proposed. Using this approach we propose a new definition which improves
on those currently used in the literature.
Other components of this thesis are an overview of derivative based mixed
integer non-linear programming, extensive reviews of mixed integer quadratic
programming and deterministic derivative free optimization and extensive
computational results illustrating the effectiveness of the contributions mentioned
in the previous paragraphs.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/12914 |
| Date | 29 July 2013 |
| Creators | Newby, Eric |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0014 seconds