Introduction to mathematical optimization

✍ Scribed by Xin-She Yang

• Publisher: Cambridge ISP
• Year: 2008
• Tongue: English
• Leaves: 161
• Category: Library

✦ Synopsis

This book strives to provide a balanced coverage of efficient algorithms commonly used in solving mathematical optimization problems. It covers both the convectional algorithms and modern heuristic and metaheuristic methods. Topics include gradient-based algorithms such as Newton-Raphson method, steepest descent method, Hooke-Jeeves pattern search, Lagrange multipliers, linear programming, particle swarm optimization (PSO), simulated annealing (SA), and Tabu search. Multiobjective optimization including important concepts such as Pareto optimality and utility method is also described. Three Matlab and Octave programs so as to demonstrate how PSO and SA work are provided. An example of demonstrating how to modify these programs to solve multiobjective optimization problems using recursive method is discussed.

✦ Table of Contents

Contents......Page 6
Part I Fundamentals......Page 12
1.1 Optimization......Page 14
1.2 Optimality Criteria......Page 17
1.3 Computational Complexity......Page 18
1.4 NP-Complete Problems......Page 20
2.1 Vector and Matrix Norms......Page 22
2.2 Eigenvalues and Eigenvectors......Page 25
2.3 Spectral Radius of Matrices......Page 29
2.4 Hessian Matrix......Page 31
2.5 Convexity......Page 33
3.1 Simple Iterations......Page 36
3.2 Bisection Method......Page 38
3.3 Newton’s Method......Page 40
3.4 Iteration Methods......Page 41
4.1 Linear systems......Page 46
4.2 Gauss Elimination......Page 49
4.3 Gauss-Jordan Elimination......Page 52
4.4 LU Factorization......Page 54
4.5.1 Jacobi Iteration Method......Page 56
4.5.2 Gauss-Seidel Iteration......Page 61
4.6 Nonlinear Equation......Page 62
4.6.2 Newton-Raphson Method......Page 63
Part II Mathematical Optimization......Page 64
5.1 Univariate Functions......Page 66
5.2 Multivariate Functions......Page 67
5.3.1 Newton’s Method......Page 70
5.3.2 Steepest Descent Method......Page 71
5.4 Hooke-Jeeves Pattern Search......Page 75
6.1 Linear Programming......Page 78
6.2.1 Basic Procedure......Page 81
6.2.2 Augmented Form......Page 83
6.2.3 A Case Study......Page 84
7.1 Penalty Method......Page 90
7.2 Lagrange Multipliers......Page 92
7.3 Kuhn-Tucker Conditions......Page 94
7.4 No Free Lunch Theorems......Page 95
Part III Metaheuristic Methods......Page 98
8.1 Tabu Search......Page 100
8.2 Travelling Salesman Problem......Page 104
8.3 Tabu Search for TSP......Page 106
9.1 Behaviour of Ants......Page 110
9.2 Ant Colony Optimization......Page 112
9.3 Double Bridge Problem......Page 114
9.4 Multi-Peak Functions......Page 115
10.1 Swarm Intelligence......Page 118
10.2 PSO algorithms......Page 119
10.3 Accelerated PSO......Page 120
10.4 Multimodal Functions......Page 122
10.5 Implementation......Page 124
10.6 Constraints......Page 128
11.1 Fundamental Concepts......Page 130
11.2 Choice of Parameters......Page 131
11.3 SA Algorithm......Page 133
11.4 Implementation......Page 134
12.1 Pareto Optimality......Page 140
12.2 Weighted Sum Method......Page 144
12.3 Utility Method......Page 147
12.4 Metaheuristic Search......Page 150
12.5 Other Algorithms......Page 154
Bibliography......Page 156
Index......Page 160