Return to search

Global Optimization of Monotonic Programs: Applications in Polynomial and Stochastic Programming.

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.

Identiferoai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/6938
Date15 April 2005
CreatorsCheon, Myun-Seok
PublisherGeorgia Institute of Technology
Source SetsGeorgia Tech Electronic Thesis and Dissertation Archive
Languageen_US
Detected LanguageEnglish
TypeDissertation
Format1261944 bytes, application/pdf

Page generated in 0.0017 seconds