Optimization Techniques II, livre ebook

This book in two volumes provides an overview of continuous, discrete and functional optimization techniques. This second volume is devoted to discrete optimization (problems with integer variables) and functional optimization (problems where the unknown is a function). The topics covered are: • mixed linear programming: cutting methods and tree methods; • combinatorial optimization based on graphs: path, flow, assignment problems ... ; • the computation of variations based on Euler-Lagrange conditions and their extensions; • optimal control based on the Pontryaguin maximum principle and its extensions; • numerical methods: differential equations, direct and indirect 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. Mixed linear programming 1

1.1 Formulation 2

1.1.1 Mixed-variable linear problem 2

1.1.2 Linearization techniques 4

1.1.3 Reduction techniques 10

1.2 Cutting methods 12

1.2.1 Cut on a variable 12

1.2.2 Cut on the cost 14

1.2.3 Gomory’s method 15

1.2.4 Integral cut 21

1.2.5 Mixed cut 23

1.3 Tree methods 31

1.3.1 Implicit enumeration 31

1.3.2 Separation 31

1.3.3 Evaluation 33

1.3.4 Exploration strategy 51

1.4 Applications 58

1.4.1 Travelling salesman problem 58

1.4.2 Assignment problem 62

1.4.3 Coloring problem 66

1.4.4 Flow problem 68

1.4.5 Knapsack problem 71

1.5 Quadratic problem 73

1.5.1 Tree method 73

1.5.2 Convexification 75

1.5.3 Quadratic assignment problem 80

1.6 Conclusion 81

1.6.1 The key points 81

1.6.2 To go further 82

2. Discrete optimization 83

2.1 Combinatorial problem 84

2.1.1 Graph 84

2.1.2 Route in a graph 87

2.1.3 Complexity 91

2.2 Path problem 95

2.2.1 Ford's algorithm 95

2.2.2 Bellman's algorithm 98

2.2.3 Dijkstra's algorithm 107

2.2.4 A* algorithm 110

2.2.5 Demoucron and Floyd’s algorithm 124

2.3 Scheduling problem 128

2.3.1 PERT method 129

2.3.2 MPM method 132

2.3.3 Margins 136

2.4 Flow problem 138

2.4.1 Ford-Fulkerson algorithm 138

2.4.2 Roy-Busacker-Gowen algorithm 144

2.5 Assignment problem 149

2.5.1 Equivalent flow problem 149

2.5.2 Hungarian method 152

2.5.3 Theoretical justification 159

2.6 Heuristics 163

2.6.1 Stacking problem 164

2.6.2 Bin packing problem 165

2.6.3 Set covering problem 166

2.6.4 Coloring problem 168

2.6.5 Travelling salesman problem 172

2.7 Conclusion 175

2.7.1 The key points 175

2.7.2 To go further 175

3. Functional optimization 177

3.1 Formulation 178

3.1.1 Functional 178

3.1.2 Neighborhood 178

3.1.3 Variation 179

3.1.4 Minimum 180

3.1.5 Standard problem 181

3.2 Optimality conditions 184

3.2.1 Weak minimum necessary conditions 184

3.2.2 Weak minimum sufficient conditions 196

3.2.3 Corner necessary conditions 205

3.2.4 Strong minimum necessary conditions 214

3.2.5 Summary 218

3.3 Constraints 219

3.3.1 Final constraint 219

3.3.2 Integral constraint 226

3.3.3 Path constraint 232

3.4 Canonical form 234

3.4.1 Change of variables 234

3.4.2 Canonical variables 237

3.4.3 Hamilton-Jacobi-Bellman equation 241

3.4.4 Application to mechanics 244

3.5 Dynamic system 248

3.5.1 State formulation 248

3.5.2 Stability 250

3.5.3 Linear system 256

3.5.4 Two-point boundary value problem 264

3.6 Conclusion 267

3.6.1 The key points 267

3.6.2 To go further 267

4. Optimal control 269

4.1 Optimality conditions 270

4.1.1 Control problem 270

4.1.2 Principle of the minimum 272

4.1.3 Variational method 281

4.1.4 Two-point boundary value problem 292

4.2 Constraints 304

4.2.1 Terminal constraints 304

4.2.2 Interior constraints 311

4.2.3 Path constraints 315

4.2.4 Quadratic-linear problem 323

4.2.5 Robust control 333

4.3 Extremals 337

4.3.1 Definitions 337

4.3.2 Abnormal extremal 338

4.3.3 Singular extremal 341

4.3.4 Neighboring extremals 346

4.3.5 State feedback control 352

4.3.6 Hamilton-Jacobi-Bellman equation 356

4.4 Optimality conditions of second order 362

4.4.1 Auxiliary minimum problem 362

4.4.2 Sufficient conditions of minimum 368

4.4.3 Singular arcs 372

4.5 Conclusion 389

4.5.1 The key points 389

4.5.2 To go further 390

5. Numerical methods in optimal control 391

5.1 Transcription 392

5.1.1 Differential equations 393

5.1.2 Direct and indirect methods 396

5.2 Runge-Kutta methods 398

5.2.1 Quadrature formulas 398

5.2.2 Error analysis 405

5.2.3 Order conditions 411

5.2.4 Embedded methods 415

5.3 Adams methods 418

5.3.1 Adams-Bashford methods 419

5.3.2 Adams-Moulton methods 420

5.4 Collocation methods 423

5.4.1 Collocation conditions 423

5.4.2 Collocation points 424

5.4.3 Collocation of degree 3 426

5.4.4 Collocation of degree 5 429

5.5 Direct methods 431

5.5.1 Discretization 431

5.5.2 Variational approach 433

5.6 Indirect methods 440

5.6.1 Shooting method 440

5.6.2 Variational approach 450

5.7 Conclusion 455

5.7.1 The key points 455

5.7.2 To go further 455