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

Monotonic programs;Global optimization;Polyblock algorithm;Branch and bound algorithm;Polynomial programming;Stochastic programming;Probabilistically constrained linear program

Cheon, Myun-Seok ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Monotonic programs;    Global optimization;    Polyblock algorithm;    Branch and bound algorithm;    Polynomial programming;    Stochastic programming;    Probabilistically constrained linear program;   

Others  :  https://smartech.gatech.edu/bitstream/1853/6938/1/Cheon_MyunSeok_200505_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Monotonic optimization consists of minimizing or maximizing amonotonic objective function over a set of constraints defined bymonotonic functions. Many optimization problems in economics andengineering often have monotonicity while lacking other usefulproperties, such as convexity. This thesis is concerned with thedevelopment and application of global optimization algorithms formonotonic optimization problems.First, we propose enhancements to an existing outer-approximationalgorithm | called the Polyblock Algorithm | for monotonicoptimization problems. The enhancements are shown to significantlyimprove the computational performance of the algorithm whileretaining the convergence properties. Next, we develop a genericbranch-and-bound algorithm for monotonic optimization problems. Acomputational study is carried out for comparing the performance ofthe Polyblock Algorithm and variants of the proposedbranch-and-bound scheme on a family of separable polynomialprogramming problems. Finally, we study an important class ofmonotonic optimization problems | probabilistically constrainedlinear programs. We develop a branch-and-bound algorithm thatsearches for a global solution to the problem. The basic algorithmis enhanced by domain reduction and cutting plane strategies toreduce the size of the partitions and hence tighten bounds. Theproposed branch-reduce-cut algorithm exploits the monotonicityproperties inherent in the problem, and requires the solution ofonly linear programming subproblems. We provide convergence proofsfor the algorithm. Some illustrative numerical results involvingproblems with discrete distributions are presented.