Optimization techniques I, livre ebook

This book in two volumes provides an overview of continuous, discrete and functional optimization techniques. This first volume is devoted to continuous optimization, which deals with problems with real variables, without or with constraints. After a reminder of the optimality conditions and their geometrical interpretation, the topics covered are:-gradient-free algorithms that can be applied to any type of function;-unconstrained algorithms based on Newton-type descent methods;-algorithms with constraints: penalization, primal, dual and primal-dual methods;-linear programming with the simplex method and interior point methods. The emphasis is on understanding the principles rather than on mathematical rigor. Each concept or algorithm is accompanied by a detailed example to help you grasp the main ideas. This book is the result of 30 years of experience and is intended for students, researchers and engineers wishing to acquire a general knowledge in the field of optimization.

1. Continuous optimization 1

1.1 Formulation 2

1.1.1 Standard form 2

1.1.2 Function of several variables 3

1.1.3 Level lines 5

1.1.4 Direction of descent 6

1.1.5 Directional variation 7

1.1.6 Solution 10

1.2 Numerical derivatives 14

1.2.1 First derivatives 15

1.2.2 Second derivatives 15

1.2.3 Increment setting 16

1.2.4 Complex derivative 19

1.2.5 Derivatives by extrapolation 20

1.3 Problem reduction 25

1.3.1 Linear reduction 25

1.3.2 Generalized reduction 31

1.4 Global optimum 37

1.4.1 Dual problem 37

1.4.2 Saddle point 40

1.4.3 Linear programming 45

1.5 Local optimum 49

1.5.1 Feasible directions 49

1.5.2 Conditions of Karush, Kuhn and Tucker 54

1.5.3 Geometric interpretation 70

1.5.4 Quadratic-linear problem 76

1.5.5 Sensitivity analysis 77

1.6 Conclusion 82

1.6.1 The key points 82

1.6.2 To go further 82

2. Gradient-free optimization 85

2.1 Difficult optimization 86

2.1.1 Discrete variables 86

2.1.2 Local minima 88

2.1.3 Local and global methods 93

2.2 One-dimensional optimization 96

2.2.1 Interval splitting 96

2.2.2 Split points positioning 97

2.2.3 Golden ratio method 99

2.2.4 Quadratic interpolation 102

2.3 DIRECT method 105

2.3.1 Lipschitzian function 105

2.3.2 Algorithm in dimension 1 107

2.3.3 Algorithm in dimension n 118

2.4 Nelder-Mead method 131

2.4.1 Polytope 131

2.4.2 Calculation stages 134

2.4.3 Improvements 136

2.5 Affine shaker 140

2.5.1 Principle 140

2.5.2 Affine transformation 142

2.5.3 Algorithm 144

2.6 CMAES 146

2.6.1 Principle 146

2.6.2 Covariance adaptation 147

2.6.3 Algorithm 150

2.7 Simulated annealing 153

2.7.1 Principle 153

2.7.2 Probability of transition 154

2.7.3 Algorithm 155

2.8 Research with tabu 161

2.8.1 Principle 161

2.8.2 Taboo list and neighborhood 161

2.8.3 Quadratic assignment 163

2.9 Particle swarms 171

2.9.1 Principle 171

2.9.2 Particle movement 171

2.9.3 Neighborhood 173

2.9.4 Algorithm 174

2.10 Ant colonies 176

2.10.1 Principle 176

2.10.2 Ant movement 177

2.10.3 Problem of the travelling salesman 177

2.11 Evolutionary algorithms 179

2.11.1 Principle 179

2.11.2 Evolutionary mechanisms 180

2.11.3 Algorithm 180

2.12 Conclusion 186

2.12.1 The key points 186

2.12.2 To go further 186

3. Unconstrained optimization 189

3.1 Newton’s method 190

3.1.1 System of equations 190

3.1.2 Homotopy method 196

3.1.3 Minimization 204

3.1.4 Least squares 207

3.2 Quasi-Newton methods 213

3.2.1 Broyden's method 213

3.2.2 DFP, BFGS and SR1 methods 217

3.2.3 BFGS improvements 227

3.3 Line search 231

3.3.1 Direction of descent 232

3.3.2 Step length 248

3.3.3 Algorithm 251

3.4 Trust region 256

3.4.1 Quadratic model 257

3.4.2 Direct solution 259

3.4.3 Dogleg solution 261

3.4.4 Algorithm 265

3.5 Proximal methods 268

3.5.1 Proximal operator 268

3.5.2 Interpretations 272

3.5.3 Proximal gradient 275

3.5.4 Primal-dual method 278

3.5.5 Calculation of the proximal operator 280

3.6 Convergence 284

3.6.1 Global convergence 284

3.6.2 Speed of convergence 286

3.6.3 Numerical accuracy 290

3.7 Conclusion 292

3.7.1 The key points 292

3.7.2 To go further 292

4. Constrained optimization 295

4.1 Classification of methods 296

4.1.1 Problem formulations 296

4.1.2 Primal, primal-dual and dual methods 298

4.1.3 Measuring improvement 301

4.2 Penalization 308

4.2.1 Penalized problem 308

4.2.2 Differentiable penalization 311

4.2.3 Exact penalization 312

4.2.4 Quadratic penalization 315

4.2.5 Barrier penalization 322

4.3 Reduced gradient 323

4.3.1 Move in tangent space 323

4.3.2 Restoration move 330

4.3.3 Line search 332

4.3.4 Quasi-Newton method 336

4.3.5 Algorithm 337

4.4 Sequential quadratic programming 341

4.4.1 Local quadratic model 341

4.4.2 Globalization 347

4.4.3 Constraint management 352

4.4.4 Quasi-Newton method 356

4.4.5 Algorithm 358

4.5 Interior point 362

4.5.1 Barrier problem 362

4.5.2 Globalization 365

4.5.3 Barrier height 366

4.6 Augmented Lagrangian 367

4.6.1 Dual problem 367

4.6.2 Augmented dual problem 371

4.6.3 Inequality constraints 375

4.6.4 Algorithm 377

4.7 Conclusion 381

4.7.1 The key points 381

4.7.2 To go further 381

5. Linear programming 383

5.1 Simplex 384

5.1.1 Standard form 384

5.1.2 Basis 387

5.1.3 Pivoting 398

5.1.4 Simplex array 404

5.1.5 Auxiliary problem 410

5.1.6 Two-phase method 415

5.1.7 Revised simplex 422

5.1.8 Dual simplex 423

5.1.9 Complementary simplex 430

5.2 Interior point 436

5.2.1 Central path 436

5.2.2 Direction of move 443

5.2.3 Step length 448

5.2.4 Prediction-correction algorithm 455

5.2.5 Extensions 458

5.3 Conclusion 460

5.3.1 The key points 460

5.3.2 To go further 461

Index

Bibliography