A guide to modern optimization applications and techniques in newly emerging areas spanning optimization, data science, machine intelligence, engineering, and computer sciences
Optimization Techniques and Applications with Examples introduces the fundamentals of all the commonly used techniques in optimization that encompass the broadness and diversity of the methods (traditional and new) and algorithms. The author--a noted expert in the field--covers a wide range of topics including mathematical foundations, optimization formulation, optimality conditions, algorithmic complexity, linear programming, convex optimization, and integer programming. In addition, the book discusses artificial neural network, clustering and classifications, constraint-handling, queueing theory, support vector machine and multi-objective optimization, evolutionary computation, nature-inspired algorithms and many other topics.
Designed as a practical resource, all topics are explained in detail with step-by-step examples to show how each method works. The book's exercises test the acquired knowledge that can be potentially applied to real problem solving. By taking an informal approach to the subject, the author helps readers to rapidly acquire the basic knowledge in optimization, operational research, and applied data mining. This important resource:
* Offers an accessible and state-of-the-art introduction to the main optimization techniques
* Contains both traditional optimization techniques and the most current algorithms and swarm intelligence-based techniques
* Presents a balance of theory, algorithms, and implementation
* Includes more than 100 worked examples with step-by-step explanations
Written for upper undergraduates and graduates in a standard course on optimization, operations research and data mining, Optimization Techniques and Applications with Examples is a highly accessible guide to understanding the fundamentals of all the commonly used techniques in optimization.
Autorentext
XIN-SHE YANG, PHD, is Reader/Professor in Modelling and Optimization at Middlesex University London. He is also an elected Bye-Fellow and College Lecturer at Cambridge University, Adjunct Professor at Reykjavik University, Iceland, as well as Distinguished Chair Professor at Xi'an Polytechnic University, China.
Inhalt
List of Figures xiii
List of Tables xvii
Preface xix
Acknowledgements xxi
Acronyms xxiii
Introduction xxv
Part I Fundamentals 1
1 Mathematical Foundations 3
1.1 Functions and Continuity 3
1.1.1 Functions 3
1.1.2 Continuity 4
1.1.3 Upper and Lower Bounds 4
1.2 Review of Calculus 6
1.2.1 Differentiation 6
1.2.2 Taylor Expansions 9
1.2.3 Partial Derivatives 12
1.2.4 Lipschitz Continuity 13
1.2.5 Integration 14
1.3 Vectors 16
1.3.1 Vector Algebra 17
1.3.2 Norms 17
1.3.3 2D Norms 19
1.4 Matrix Algebra 19
1.4.1 Matrices 19
1.4.2 Determinant 23
1.4.3 Rank of a Matrix 24
1.4.4 Frobenius Norm 25
1.5 Eigenvalues and Eigenvectors 25
1.5.1 Definiteness 28
1.5.2 Quadratic Form 29
1.6 Optimization and Optimality 31
1.6.1 Minimum and Maximum 31
1.6.2 Feasible Solution 32
1.6.3 Gradient and Hessian Matrix 32
1.6.4 Optimality Conditions 34
1.7 General Formulation of Optimization Problems 35
Exercises 36
Further Reading 36
2 Algorithms, Complexity, and Convexity 37
2.1 What Is an Algorithm? 37
2.2 Order Notations 39
2.3 Convergence Rate 40
2.4 Computational Complexity 42
2.4.1 Time and Space Complexity 42
2.4.2 Class P 43
2.4.3 Class NP 44
2.4.4 NP-Completeness 44
2.4.5 Complexity of Algorithms 45
2.5 Convexity 46
2.5.1 Linear and Affine Functions 46
2.5.2 Convex Functions 48
2.5.3 Subgradients 50
2.6 Stochastic Nature in Algorithms 51
2.6.1 Algorithms with Randomization 51
2.6.2 Random Variables 51
2.6.3 Poisson Distribution and Gaussian Distribution 54
2.6.4 Monte Carlo 56
2.6.5 Common Probability Distributions 58
Exercises 61
Bibliography 62
Part II Optimization Techniques and Algorithms 63
3 Optimization 65
3.1 Unconstrained Optimization 65
3.1.1 Univariate Functions 65
3.1.2 Multivariate Functions 68
3.2 Gradient-Based Methods 70
3.2.1 Newton's Method 71
3.2.2 Convergence Analysis 72
3.2.3 Steepest Descent Method 73
3.2.4 Line Search 77
3.2.5 Conjugate Gradient Method 78
3.2.6 Stochastic Gradient Descent 79
3.2.7 Subgradient Method 81
3.3 Gradient-Free NelderMead Method 81
3.3.1 A Simplex 81
3.3.2 NelderMead Downhill Simplex Method 82
Exercises 84
Bibliography 84
4 Constrained Optimization 87
4.1 Mathematical Formulation 87
4.2 Lagrange Multipliers 87
4.3 Slack Variables 91
4.4 Generalized Reduced Gradient Method 94
4.5 KKT Conditions 97
4.6 PenaltyMethod 99
Exercises 101
Bibliography 101
5 Optimization Techniques: Approximation Methods 103
5.1 BFGS Method 103
5.2 Trust-Region Method 105
5.3 Sequential Quadratic Programming 107
5.3.1 Quadratic Programming 107
5.3.2 SQP Procedure 107
5.4 Convex Optimization 109
5.5 Equality Constrained Optimization 113
5.6 Barrier Functions 115
5.7 Interior-PointMethods 119
5.8 Stochastic and Robust Optimization 121
Exercises 123
Bibliography 123
Part III Applied Optimization 125
6 Linear Programming 127
6.1 Introduction 127
6.2 Simplex Method 129
6.2.1 Slack Variables...