Luận Văn TIẾN SỸ : Global Optimization of Monotonic Programs: Applications in Polynomial and Stochastic Progr

ACKNOWLEDGEMENTS



First, I would like to express my sincere gratitude to my two advisors, Dr. Faiz Al-Khayyal


and Dr. Shabbir Ahmed for their guidance and encouragements throughout the entire


course of my research. Without their excellent insights and invaluable suggestions, I could


not be able to complete this thesis.


I am grateful to Dr. Earl Barnes, Dr. Alex Shapiro and Dr. Matthew Realf for serving


as members of my committee and their valuable comments and suggestions.


Finally, I am deeply thankful to my parents, Bong-Nam Cheon and Sung-Hang Lee for


their support and encouragement. I owe special thanks to my wife, Jin-Ah Lim, and my


princess and prince, Esther and Ethan. Their support, patience, and love enabled me to


complete this thesis.



TABLE OF CONTENTS




DEDICATION iii


ACKNOWLEDGEMENTS iv


LIST OF TABLES . vii


LIST OF FIGURES viii


SUMMARY ix




CHAPTER I INTRODUCTION .


CHAPTER II MONOTONIC PROGRAMMING: STRUCTURE AND AL-

GORITHMS .

2.1 Introduction .

2.2 Characteristics of Monotonic Programs

2.3 Polyblock Algorithm

2.3.1 An illustrative example . 10

2.3.2 Enhancement 11

2.3.3 Convergence analysis 21

2.4 Branch-and-Bound Algorithm . 23

2.4.1 Selection and branching 23

2.4.2 Domain reduction 25

2.4.3 Bounding and optimality cuts . 28

2.4.4 Fathoming 30

2.4.5 Convergence analysis 30

2.5 Simplicial branching 33


CHAPTER III COMPUTATIONAL RESULTS FOR SEPARABLE POLY-

NOMIAL PROGRAMMING PROBLEMS . 36

3.1 Separable polynomial programming 36

3.1.1 Problem transformation 37

3.1.2 Convex relaxations . 38

3.2 Computational Experiments 42

3.2.1 Test problems 42


3.2.2 Bounding by variable fixing 45

3.2.3 Computational Results . 46


CHAPTER IV PROBABILISTICALLY CONSTRAINED LINEAR PRO-

GRAMS . 53

4.1 Introduction . 53

4.2 Problem reformulation and structural properties . 55

4.3 A Branch-Reduce-Cut algorithm 60

4.3.1 Selection and branching 63

4.3.2 Domain reduction 64

4.3.3 Feasibility and optimality cuts . 65

4.3.4 Upper bounding and searching for feasible solutions . 66

4.3.5 Fathoming 67

4.4 Convergence analysis 68

4.4.1 Discrete distribution 68

4.4.2 Continuous distribution 70

4.5 Computational results . 71


CHAPTER V CONCLUSION . 74


APPENDIX A — COMPUTATIONAL RESULTS . 77


REFERENCES . 92


VITA 95