Optimization Techniques and Applications with Examples

 
 
Standards Information Network (Verlag)
  • 1. Auflage
  • |
  • erschienen am 24. September 2018
  • |
  • 384 Seiten
 
E-Book | ePUB mit Adobe-DRM | Systemvoraussetzungen
978-1-119-49062-3 (ISBN)
 
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.
1. Auflage
  • Englisch
  • USA
John Wiley & Sons Inc
  • Für Beruf und Forschung
  • 9,32 MB
978-1-119-49062-3 (9781119490623)

weitere Ausgaben werden ermittelt
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.
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 Nelder-Mead Method 81

3.3.1 A Simplex 81

3.3.2 Nelder-Mead 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 129

6.2.2 Standard Formulation 130

6.2.3 Duality 131

6.2.4 Augmented Form 132

6.3 Worked Example by Simplex Method 133

6.4 Interior-PointMethod for LP 136

Exercises 139

Bibliography 139

7 Integer Programming 141

7.1 Integer Linear Programming 141

7.1.1 Review of LP 141

7.1.2 Integer LP 142

7.2 LP Relaxation 143

7.3 Branch and Bound 146

7.3.1 How to Branch 153

7.4 Mixed Integer Programming 155

7.5 Applications of LP, IP, and MIP 156

7.5.1 Transport Problem 156

7.5.2 Product Portfolio 158

7.5.3 Scheduling 160

7.5.4 Knapsack Problem 161

7.5.5 Traveling Salesman Problem 161

Exercises 163

Bibliography 163

8 Regression and Regularization 165

8.1 Sample Mean and Variance 165

8.2 Regression Analysis 168

8.2.1 Maximum Likelihood 168

8.2.2 Regression 168

8.2.3 Linearization 173

8.2.4 Generalized Linear Regression 175

8.2.5 Goodness of Fit 178

8.3 Nonlinear Least Squares 179

8.3.1 Gauss-Newton Algorithm 180

8.3.2 Levenberg-Marquardt Algorithm 182

8.3.3 Weighted Least Squares 183

8.4 Over-fitting and Information Criteria 184

8.5 Regularization and Lasso Method 186

8.6 Logistic Regression 187

8.7 Principal Component Analysis 191

Exercises 195

Bibliography 196

9 Machine Learning Algorithms 199

9.1 Data Mining 199

9.1.1 Hierarchy Clustering 200

9.1.2 k-Means Clustering 201

9.1.3 Distance Metric 202

9.2 Data Mining for Big Data 202

9.2.1 Characteristics of Big Data 203

9.2.2 Statistical Nature of Big Data 203

9.2.3 Mining Big Data 204

9.3 Artificial Neural Networks 206

9.3.1 Neuron Model 207

9.3.2 Neural Networks 208

9.3.3 Back Propagation Algorithm 210

9.3.4 Loss Functions in ANN 212

9.3.5 Stochastic Gradient Descent 213

9.3.6 Restricted Boltzmann Machine 214

9.4 Support Vector Machines 216

9.4.1 Statistical Learning Theory 216

9.4.2 Linear Support Vector Machine 217

9.4.3 Kernel Functions and Nonlinear SVM 220

9.5 Deep Learning 221

9.5.1 Learning 221

9.5.2 Deep Neural Nets 222

9.5.3 Tuning of Hyper-Parameters 223

Exercises 223

Bibliography 224

10 Queueing Theory and Simulation 227

10.1 Introduction 227

10.1.1 Components of Queueing 227

10.1.2 Notations 228

10.2 Arrival Model 230

10.2.1 Poisson Distribution 230

10.2.2 Inter-arrival Time 233

10.3 Service Model 233

10.3.1 Exponential Distribution 233

10.3.2 Service Time Model 235

10.3.3 Erlang Distribution 235

10.4 Basic QueueingModel 236

10.4.1 M/M/1 Queue 236

10.4.2 M/M/s Queue 240

10.5 Little's Law 242

10.6 Queue Management and Optimization 243

Exercises 245

Bibliography 246

Part IV Advanced Topics 249

11 Multiobjective Optimization 251

11.1 Introduction 251

11.2 Pareto Front and Pareto Optimality 253

11.3 Choice and Challenges 255

11.4 Transformation to Single Objective Optimization 256

11.4.1 Weighted Sum Method 256

11.4.2 Utility Function 259

11.5 The ??-Constraint Method 261

11.6 Evolutionary Approaches 264

11.6.1 Metaheuristics 264

11.6.2 Non-Dominated Sorting Genetic Algorithm 265

Exercises 266

Bibliography 266

12 Constraint-Handling Techniques 269

12.1 Introduction and Overview 269

12.2 Method of Lagrange Multipliers 270

12.3 Barrier Function Method 272

12.4 PenaltyMethod 272

12.5 Equality Constraints via Tolerance 273

12.6 Feasibility Criteria 274

12.7 Stochastic Ranking 275

12.8 Multiobjective Constraint-Handling and Ranking 276

Exercises 276

Bibliography 277

Part V Evolutionary Computation and Nature-Inspired

Algorithms 279

13 Evolutionary Algorithms 281

13.1 Evolutionary Computation 281

13.3.1 Basic Procedure 284

13.3.2 Choice of Parameters 285

13.4 Simulated Annealing 287

13.5 Differential Evolution 290

Exercises 293

Bibliography 293

14 Nature-Inspired Algorithms 297

14.1 Introduction to SI 297

14.2 Ant and Bee Algorithms 298

14.3 Particle Swarm Optimization 299

14.3.1 Accelerated PSO 301

14.3.2 Binary PSO 302

14.4 Firefly Algorithm 303

14.5 Cuckoo Search 306

14.5.1 CS Algorithm 307

14.5.2 Levy Flight 309

14.5.3 Advantages of CS 312

14.6 Bat Algorithm 313

14.7 Flower Pollination Algorithm 315

14.8 Other Algorithms 319

Exercises 319

Bibliography 319

Appendix A Notes on Software Packages 323

Appendix B Problem Solutions 329

Index 345

Introduction


Optimization is everywhere, though it can mean different things from different perspectives. From basic calculus, optimization can be simply used to find the maximum or minimum of a function such as in the real domain . In this case, we can either use a gradient-based method or simply spot the solution due to the fact that x4 and x2 are always nonnegative, the minimum values of x4 and x2 are zero, thus has a minimum at . This can be confirmed easily by taking the first derivative of f(x) with respect to x, we have

(I.1)

which has only one solution because x is a real number. The condition seems to be sufficient to determine the optimal solution in this case. In fact, this function is convex with only one minimum in the whole real domain.

However, things become more complicated when f(x) is highly nonlinear with multiple optima. For example, if we try to find the maximum value of in the real domain, we can naively use

(I.2)

which has an infinite number of solutions for . There is no simple formula for these solutions, thus a numerical method has to be used to calculate these solutions. In addition, even with all the efforts to find these solutions, care has to be taken because the actual global maximum occurs at . However, this solution can only be found by taking the limit , and it is not part of the solutions from the above condition of . This highlights the potential difficulty for nonlinear problems with multiple optima or multi-modality.

Furthermore, not all functions are smooth. For example, if we try to use to find the minimum of

(I.3)

we will realize that f(x) is not differentiable at , though the global minimum occurs at . In this case, optimization techniques that require the calculation of derivatives will not work.

Problems become more challenging in higher-dimensional spaces. For example, the nonlinear function

(I.4)

where for , has a minimum at , but this function is not differentiable at x*.

Therefore, optimization techniques have to be diverse to use gradient information when appropriate, and not to use it when it is not defined or not easily calculated. Though the above nonlinear optimization problems can be challenging to solve, constraints on the search domain and certain independent variables can make the search domain much more complicated, which can consequently make the problem even harder to solve. In addition, sometime, we have to optimize several objective functions instead of just one function, which will in turn make a problem more challenging to solve.

In general, it is possible to write most optimization problems in the general form mathematically

(I.5) (I.6) (I.7)

where fi(x),??j(x), and ?k(x) are functions of the design vector

(I.8)

Here, the components xi of x are called design or decision variables, and they can be real continuous, discrete, or the mixture of these two. The functions fi(x) where are called the objective functions, and in the case of , there is only a single objective, and the problem becomes single-objective optimization. The objective function is sometimes called the cost function, loss function, or energy function in the literature. The space spanned by the decision variables is called the design space or search space Rn, while the space formed by the objective function values is called the response space or objective landscape. The equalities for ?j and inequalities for ?k are called constraints. It is worth pointing out that we can also write the inequalities in the other way , and we can also formulate the objectives as maximization.

If a solution vector x satisfies all the constraints ?j(x) and ?k(x), it is called a feasible solution; otherwise, it is infeasible. All the feasible points or vectors form the feasible regions in the search space.

In a rare but extreme case where there is no objective at all, there are only constraints. Such a problem is called a feasibility problem and any feasible solution is an optimal solution to such problems.

If all the problem functions are linear, the problem becomes a linear programming (LP) problem. Here, the term "programming" means planning, it has nothing to do with computer programming in this context. Thus, mathematical optimization is also called mathematical programming. In addition, if the variables in LP only take integer values, the LP becomes an integer LP or simple integer programming (IP). If the variables can only take two values (0 or 1), such an LP is called binary IP.

If there are no constraints (i.e. and ), the problem becomes an unconstrained optimization problem. If but , it becomes equality-constrained optimization. Conversely, if but , it becomes the inequality-constrained problem.

The classification of optimization problems can also be done by looking at the modality of the objective landscape, which can be divided into multimodal problems and unimodal problems including convex optimization. In addition, classification can also be about the determinacy of the problem. If there is NO randomness in the formulation, the problem is called deterministic and in fact all the above problems are essentially deterministic. However, if there is uncertainty in the variables or function forms, then optimization involves probability distribution and expectation, such problems are often called stochastic optimization or robust optimization.

Classification of optimization problems and the terminologies used in the optimization literature can be diverse and confusing. We summarize most of these terms in Figure I.1.

Figure I.1 Classification of optimization problems.

Whether an optimization problem is considered easy or hard, it can depend on many factors and the actual perspective of mathematical formulations. In fact, three factors that make a problem more challenging are: nonlinearity of the objective function, the high dimensionality of the problem, and the complex shape of the search domain.

  • Nonliearity and multimodality: The high nonlinearity of a function to be optimized usually means multimodality with multiple local modes with multiple (even infinite) optima. In most cases, algorithms to solve such problems are more likely to get trapped in local modes.
  • High dimensionality: High dimensionality is associated with the so-called curse of dimensionality where the distance becomes large, while the volume of any algorithm that can actually search becomes insignificant compared to the vast feasible space.
  • Constraints: The multiple complex constraints can make the feasible region complicated with irregular geometry or shapes. In some cases, feasible regions can be split into multiple disconnected regions with isolated islands, which makes it harder for algorithms to search all the feasible regions (thus potentially missing the true optimality).

Other factors such as the evaluation time of an objective are also important. In many applications such as protein folding, bio-informatics, aero-space engineering, and deep machine learning (ML), the evaluation of a single objective can take a long time (from a few hours to days or even weeks), therefore the computational costs can be very high. Thus, the choice of efficient algorithms becomes paramount.

Algorithms for solving optimization problems tend to be iterative, and thus multiple evaluations of objectives are needed, typically hundreds or thousands (or even millions) of evaluations. Different algorithms may have different efficiency and different requirements. For example, Newton's method, which is gradient-based, is very efficient for solving smooth objective functions, but they can get stuck in local modes if the objective is highly multimodal. If the objective is not smooth or has a kink, then the Nelder-Mead simplex method can be used because it is a gradient-free method, and can work well even for problems with discontinuities, but it can become slow and get stuck in a local mode. Algorithms for solving nonlinear optimization are diverse, including the trust-region method, interior-point method, and others, but they are mostly local search methods. In a special case when the objective becomes convex, they can be very efficient. Quadratic programming (QP) and sequential quadratic programming use such convexity properties to their advantage.

The simplex method for solving LP can be efficient in practice, but it requires all the problem functions to be linear. But, if an LP problem has integer variables, the simplex method will not work directly, it has to be combined with branch and bound to solve IP problems.

As traditional methods are usually local search algorithms, one of the current trends is to use heuristic and metaheuristic algorithms. Here meta- means "beyond" or "higher level," and they generally perform better than simple heuristics. In addition, all metaheuristic algorithms use certain tradeoff of randomization and local search. It is worth pointing out that...

Dateiformat: ePUB
Kopierschutz: Adobe-DRM (Digital Rights Management)

Systemvoraussetzungen:

Computer (Windows; MacOS X; Linux): Installieren Sie bereits vor dem Download die kostenlose Software Adobe Digital Editions (siehe E-Book Hilfe).

Tablet/Smartphone (Android; iOS): Installieren Sie bereits vor dem Download die kostenlose App Adobe Digital Editions (siehe E-Book Hilfe).

E-Book-Reader: Bookeen, Kobo, Pocketbook, Sony, Tolino u.v.a.m. (nicht Kindle)

Das Dateiformat ePUB ist sehr gut für Romane und Sachbücher geeignet - also für "fließenden" Text ohne komplexes Layout. Bei E-Readern oder Smartphones passt sich der Zeilen- und Seitenumbruch automatisch den kleinen Displays an. Mit Adobe-DRM wird hier ein "harter" Kopierschutz verwendet. Wenn die notwendigen Voraussetzungen nicht vorliegen, können Sie das E-Book leider nicht öffnen. Daher müssen Sie bereits vor dem Download Ihre Lese-Hardware vorbereiten.

Bitte beachten Sie bei der Verwendung der Lese-Software Adobe Digital Editions: wir empfehlen Ihnen unbedingt nach Installation der Lese-Software diese mit Ihrer persönlichen Adobe-ID zu autorisieren!

Weitere Informationen finden Sie in unserer E-Book Hilfe.


Download (sofort verfügbar)

100,99 €
inkl. 7% MwSt.
Download / Einzel-Lizenz
ePUB mit Adobe-DRM
siehe Systemvoraussetzungen
E-Book bestellen