Back to search

Georgia Institute of Technology

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

Abstract

dc:description.abstract

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.

Degree

thesis:*
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cheon, Myun-Seok
Advisors dc:contributor.advisor
  • Al-Khayyal, Faiz
  • Ahmed, Shabbir
Committee members dc:contributor.committeemember
  • Barnes, Earl R.
  • Realff, Matthew J.
  • Shapiro, Alexander

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/6938

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Cheon, Myun-Seok. Global Optimization of Monotonic Programs: Applications in Polynomial and Stochastic Programming.. Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/6938