Monotonic optimization consists of minimizing or maximizing a
monotonic objective function over a set of constraints defined by
monotonic functions. Many optimization problems in economics and
engineering often have monotonicity while lacking other useful
properties, such as convexity. This thesis is concerned with the
development and application of global optimization algorithms for
monotonic optimization problems.
First, we propose enhancements to an existing outer-approximation
algorithm | called the Polyblock Algorithm | for monotonic
optimization problems. The enhancements are shown to significantly
improve the computational performance of the algorithm while
retaining the convergence properties. Next, we develop a generic
branch-and-bound algorithm for monotonic optimization problems. A
computational study is carried out for comparing the performance of
the Polyblock Algorithm and variants of the proposed
branch-and-bound scheme on a family of separable polynomial
programming problems. Finally, we study an important class of
monotonic optimization problems | probabilistically constrained
linear programs. We develop a branch-and-bound algorithm that
searches for a global solution to the problem. The basic algorithm
is enhanced by domain reduction and cutting plane strategies to
reduce the size of the partitions and hence tighten bounds. The
proposed branch-reduce-cut algorithm exploits the monotonicity
properties inherent in the problem, and requires the solution of
only linear programming subproblems. We provide convergence proofs
for the algorithm. Some illustrative numerical results involving
problems with discrete distributions are presented.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/6938 |
| Date | 15 April 2005 |
| Creators | Cheon, Myun-Seok |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | 1261944 bytes, application/pdf |
Page generated in 0.0014 seconds