Heuristic Global Optimization by Mubashsharul Islam Shafique, M. A dissertation submitted to the Faculty of Graduate and Postdoctoral Affairs in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical Engineering Ottawa-Carleton Institute for Electrical and Computer Engineering Department of Systems and Computer Engineering Carleton University Ottawa, Ontario April, 2017 c Copyright Mubashsharul Islam Shafique, 2017 The undersigned hereby recommends to the Faculty of Graduate and Postdoctoral Affairs acceptance of the dissertation Heuristic Global Optimization submitted by Mubashsharul Islam Shafique, M. in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical Engineering Professor Yvan Labiche, Chair, Department of Systems and Computer Engineering Ottawa-Carleton Institute for Electrical and Computer Engineering Department of Systems and Computer Engineering Carleton University April, 2017 ii Abstract Global Optimization (GO) problems occur quite frequently in real-life applications, but are very hard to solve. As a result there is an ever-growing demand to find effec- tive, fast methods for solving GO problems.
The goal of this research is to develop algorithms that can quickly find good quality solutions to large-scale nonconvex GO problems, which are the hardest form of GO problems. This research develops a fast heuristic multistart algorithm for solving large-scale GO problems. The new heuristic algorithm, Constraint Consensus Global Optimizer (CCGO), has two phases: global and local. The global phase is an approximate search that quickly explores the vari- able space using a variety of heuristics.
The local phase launches local solvers from the most promising points found in the global phase. CCGO has been specifically designed to utilize the state-of-the-art hardware systems supporting concurrency in software execution. The components of the new heuristic algorithm have been thor- oughly examined via a number of experiments. The performance of the new heuristic is then studied with respect to some state of the art complete and heuristic solver- s.
Empirical results show that the CCGO algorithm has an edge in runtime while offering competitive solution quality. CCGO’s ability to find high-quality solutions quickly makes it an attractive choice in both theory and practice: (a) practical ap- plications that need a solution as quickly as possible can use CCGO to get one and (b) optimization solvers that want to capitalize on an early incumbent solution can use CCGO or its approximate search feature within their workflow. iii This work is dedicated to: My parents, without whom I could never be who I am today, whose innumerable contributions surround my existence My amazing family, who has been a constant source of inspiration for me, who stood beside me during all hardships My siblings, who nourished me in all possible ways My teachers, from kindergarten to university, who taught me, who were patient in the face of my stupid questions, who guided me all the way - to think precisely in this fuzzy world. iv Acknowledgments I am grateful to my creator who has given me the opportunity to enjoy all bounties in this world.
My sincere gratitude goes to all of my teachers, who have inspired me since my childhood and whose lessons have enriched my knowledge. This thesis would not have been possible without the guidance of my supervisor Professor John W. I am deeply indebted to him. His motivations, suggestions, thoughts, and insights enlightened my heart and brought a success to this thesis work.
His cooperation and constructive feedback helped me a lot during my graduate study at Carleton University. I acknowledge all scholarships and awards granted toward my research and grad- uate studies through the Department of Systems and Computer Engineering (SCE), Carleton University. Without these financial support it was impossible for me to pay for my tuition and living expenses. It is my honor to thank all teachers and the administrative staffs at SCE Department, from whom I got lessons, advices, and cooperation.
I am immensely indebted to my father, Dr. Abdul Wahhab and my mother, Monowara Begum, who have ever lasting impact in my life. Their contributions to my upbringing are unfathomable, and I owe a lot to them. I also deeply acknowledge the support and advice of my father-in-law Dr.
Ridwan Ullah Shahidi, and my mother-in- law Shaheen Akhter during the most crucial period of my PhD study in 2017. They helped and accompanied my wife and my newborn, when I was staying for long hours at Carleton University. Last but not the least, I am grateful to my superhero wife Sohaila Binte Ridwan, for her continuous and unparalleled love, help and support; and to my daughter Samawi Mayameen for her little smiles that kept me alive through many tough days. v Table of Contents Abstract iii Acknowledgments v Table of Contents vi List of Tables ix List of Figures xi List of Symbols xiv List of Acronyms xviii 1 Introduction 1 2 Background 3 2.3 Feasibility Seeking via Constraint Consensus.
7 3 State of the Art in Global Optimization of Nonconvex Continuous Problems 11 3.1 Space-Covering Methods .1 Multistart-based Methods .3 Software State of the Art. 23 4 Thesis Statement 24 5 New Algorithms for Global Optimization 26 5.1 Components of the CCGO Algorithm .1 Initial Point Generator .2 Point Improvement via Constraint Consensus .3 Finding Clusters via Cluster Builder .4 Cluster Improvement via Simple Search .2 CCGO: Basic Serial Algorithm .3 CCGO: Concurrent Enhanced Algorithm. 51 6 Parameter Tuning of the CCGO Algorithm 52 6.1 Performance Tuning - Phase One .2 Performance Tuning - Phase Two. 81 7 Performance Analysis of the CCGO Algorithm 82 7.1 Platform - Software and Hardware .3 Test Models and Performance Metric .2 Performance Analysis for Nonlinearly Constrained Models .3 Performance Analysis for Linearly Constrained Models .4 Performance Analysis for Highly Nonconvex Models .1 Contributions to Knowledge.
118 List of References 119 Appendix A Best Known Objective Function Value for Test Problems in CUTEr 127 Appendix B MSNLP Log Showing Involuntary Termination after Time Limit 170 viii List of Tables 6.1 Settings for CCGO Components in Phase One Tuning Experiments .2 Statistics of Models used in Phase One Tuning Experiments .3 Matrix for Experiment A .4 Data on Relative Strength of ‘ NLC’ Variants in Experiment A .5 Data on Relative Strength of ‘ ALL’ Variants in Experiment A .6 Data on Relative Strength of Variants A4 NLC and A1 ALL .7 Matrix for Experiment B .8 Data on Relative Strength of B1 ALL Variants in Experiment B .9 Data on Relative Strength of B4 NLC Variants in Experiment B .10 Data on Relative Strength of B4 NLC D10 and B1 ALL D5 .11 Statistics of Models used in Phase Two Tuning Experiments .12 List of Algorithmic Variants in Experiment C .13 Data on Relative Strength of C1 Variants .14 Data on Relative Strength of C2 Variants .15 Data on Relative Strength of C3 Variants .16 Data on Relative Strength of C4 Variants .1 Solvers for Experiment D .2 Statistics of Test Models used in Experiment D .3 NLC Solution Quality - Difference from Best in Group (CCGO vs.4 NLC Solution Quality - Difference from Best in Group (CCGO vs.5 NLC - Solver Robustness .6 NLC - Multistart Robustness of CCGO .7 NLC - CCGO Coefficient of Variation .8 NLC Solution Quality - First Incumbent vs.9 NLC Solution Quality - Difference from Best in Group (CCGO First Incumbent vs. Complete Solvers’ Final) .10 NLC Solution Quality - Difference from Best in Group (CCGO First Incumbent vs. Heuristic Solvers’ Final) .11 LC Solution Quality - Difference from Best in Group (CCGO vs.12 LC Solution Quality - Difference from Best in Group (CCGO vs.13 LC Solution Quality - First Incumbent vs.14 LC - Solver Robustness .15 LC - Multistart Robustness of CCGO .16 LC - CCGO Coefficient of Variation .17 LC Solution Quality - Difference from Best in Group (CCGO First Incumbent vs. Complete Solvers’ Final) .18 LC Solution Quality - Difference from Best in Group (CCGO First Incumbent vs.
Heuristic Solvers’ Final) .19 MProbe Statistics for Highly Nonconvex Models .20 Highly Nonconvex Solution Quality - Difference from Best in Group (CCGO vs.21 Highly Nonconvex Solution Quality - Difference from Best in Group (CCGO vs.22 Highly Nonconvex - Solver Robustness .23 Highly Nonconvex - Multistart Robustness of CCGO .24 Highly Nonconvex - CCGO Coefficient of Variation .25 Highly Nonconvex Solution Quality - Difference from Best in Group (CCGO First Incumbent vs. Complete Solvers’ Final) .26 Highly Nonconvex Solution Quality - Difference from Best in Group (CCGO First Incumbent vs. Heuristic Solvers’ Final) .1 Best Known Objective Function Value for Test Problems in CUTEr [1] 127 x List of Figures 2. Global Maxima for a 1-variable Maximization [2] .2 Multiple Disconnected Feasible Regions [2] .1 Nonlinear Convex Underestimator .2 Branch & Reduce Method [3] .3 One Iteration of the K-Means Method [4] .1 Example of Segment Probability Calculation in Weighted Sampling .2 Exterior Search Hyperbox of SS in 2D .3 Execution Flow in the Concurrent Algorithm .1 Performance Profile of Solution Quality - using Nonlinear Constraints 57 6.2 Performance Profile of Runtime - using Nonlinear Constraints .3 Performance Profile of Solution Quality - using All Constraints .4 Performance Profile of Runtime - using All Constraints .5 Performance Profile of Solution Quality - A4 NLC vs.6 Performance Profile of Runtime - A4 NLC vs.7 Performance Profile of Solution Quality - B1 ALL with Varying δ .8 Performance Profile of Runtime - B1 ALL with Varying δ .9 Performance Profile of Solution Quality - B4 NLC with Varying δ .10 Performance Profile of Runtime - B4 NLC with Varying δ .11 Performance Profile of Solution Quality - B4 NLC D10 vs.12 Performance Profile of Runtime - B4 NLC D10 vs.13 Performance Profile of Overall Solution Quality - C1 .14 Performance Profile of Overall Runtime - C1 .15 Performance Profile of First Incumbent Solution Quality - C1 .16 Performance Profile of First Incumbent Runtime - C1 .17 Performance Profile of Overall Solution Quality - C2 .18 Performance Profile of Overall Runtime - C2 .19 Performance Profile of First Incumbent Solution Quality - C2 .20 Performance Profile of First Incumbent Runtime - C2 .21 Performance Profile of Overall Solution Quality - C3 .22 Performance Profile of Overall Runtime - C3 .23 Performance Profile of First Incumbent Solution Quality - C3 .24 Performance Profile of First Incumbent Runtime - C3 .25 Performance Profile of Overall Solution Quality - C4 .26 Performance Profile of Overall Runtime - C4 .27 Performance Profile of First Incumbent Solution Quality - C4 .28 Performance Profile of First Incumbent Runtime - C4 .1 NLC - First Incumbent Solution Speed (vs.2 NLC - Total Runtime if within Time Limit (vs.3 NLC - Total Runtime (vs.4 NLC - First Incumbent Solution Speed (vs.5 NLC - Total Runtime if within Time Limit (vs.6 NLC - Total Runtime (vs.7 NLC - Total Runtime if within Time Limit (CCGO First Incumbent vs.
Complete Solvers’ Final) .8 NLC - Total Runtime (CCGO First Incumbent vs. Complete Solvers’ Final) .9 NLC - Total Runtime if within Time Limit (CCGO First Incumbent vs. Heuristic Solvers’ Final) .10 NLC - Total Runtime (CCGO First Incumbent vs. Heuristic Solvers’ Final) .11 LC - First Incumbent Solution Speed (vs.12 LC - Total Runtime if within Time Limit (vs.13 LC - Total Runtime (vs.14 LC - First Incumbent Solution Speed (vs.15 LC - Total Runtime if within Time Limit (vs.16 LC - Total Runtime (vs.17 LC - Total Runtime if within Time Limit (CCGO First Incumbent vs.
Complete Solvers’ Final) .18 LC - Total Runtime (CCGO First Incumbent vs. Complete Solvers’ Final) .19 LC - Total Runtime if within Time Limit (CCGO First Incumbent vs. Heuristic Solvers’ Final) .20 LC - Total Runtime (CCGO First Incumbent vs. Heuristic Solvers’ Final) .21 Highly Nonconvex - First Incumbent Solution Speed (vs.22 Highly Nonconvex - Overall Solution Speed if within Time Limit (vs.23 Highly Nonconvex - Overall Solution Speed (vs.24 Highly Nonconvex - First Incumbent Solution Speed (vs.25 Highly Nonconvex - Overall Solution Speed if within Time Limit (vs.26 Highly Nonconvex - Overall Solution Speed (vs.