Optimizations and Programming

Abdelkhalak El Hami is Full Professor of Universities at INSA-RouenNormandie, France. He is the author/co-author of several books and is responsible for the Chair of mechanics at the Conservatoire National des Arts et Métiers in Normandy, as well as for several European pedagogical projects. He is a specialist in problems of optimization and reliability in multi-physical systems. Bouchaïb Radi is Professor at the Faculty of Science and Technology at Hassan Premier University, Morocco. He is a specialist in numerical optimization methods and system reliability.

• Preface xiPart 1. Programmation 1Chapter 1. Linear Programming 31.1. Introduction 31.2. Definitions 31.3. Geometry of the linear program 51.3.1. Polyhedra 51.3.2. Extreme points and vertices 61.4. Graphical solving of a linear program 61.5. Simplex algorithm 91.5.1. Basic solutions and basic feasible solutions 91.5.2. Simplex tableau 101.5.3. Change of feasible basis 111.5.4. Existence and uniqueness of an optimal solution 141.6. Initialization of the simplex algorithm 151.6.1. Big M method 151.6.2. Auxiliary program or Phase I 171.6.3. Degeneracy and cycling 201.6.4. Geometric structure of realizable solutions 211.7. Interior-point algorithm 221.8. Duality 231.8.1. Duality theorem 251.9. Relaxation 271.9.1. Lagrangian relaxation 271.10. Postoptimal analysis 291.10.1. Effect of modifying b 311.10.2. Effect of modifying c 321.11. Application to an inventory problem 341.11.1. Optimal solution 341.11.2. Sensitivity to variation in stock 351.11.3. Dual problem of the competitor 361.12. Using Matlab 36Chapter 2. Integer Programming 412.1. Introduction 412.2. Solving methods 412.2.1. Branch-and-bound method 422.2.2. The branch-and-cut method 442.3. Binary programming 492.3.1. Knapsack problem 492.3.2. Investment problem 502.4. Decomposition principle 572.4.1. Benders decomposition 582.5. Using Matlab 62Chapter 3. Dynamic Programming 653.1. Introduction 653.2. Solving strategy 663.3. Discrete DP 683.3.1. Bellman’s equation and the principle of optimality 683.3.2. Approach of the method 703.3.3. A few examples of DP 703.3.4. Solving an LP 733.3.5. Shortest path problem 743.3.6. Knapsack problem 793.3.7. Stock management problem 813.4. Continuous DP 833.4.1. Hamilton–Jacobi equation 843.4.2. Application to a consumption-savings model 843.5. Stochastic DP 853.5.1. Decision-chance process 853.5.2. Solving method 863.5.3. Application to a contract problem 863.5.4. Optimal binary search tree 873.6. Using Matlab 91Chapter 4. Stochastic Programming 934.1. Introduction 934.2. Presentation of the problem 944.3. Optimal feedback in an open loop 944.4. Stochastic linear programming 954.4.1. Models with probability thresholds on the constraints 964.5. Stochastic linear programs with recourse 964.5.1. L-shaped method 974.5.2. Multicut L-shaped method 994.5.3. Interior linearization method 1004.6. Nonlinear stochastic programming 1004.6.1. Approaches to two-step problems with recourse 1004.6.2. Regularized decomposition method 1014.6.3. Methods based on the Lagrangian 1014.6.4. Frank–Wolfe method for problems with simple recourse 1034.6.5. Approximation by sampling average: Monte Carlo method 1054.6.6. Stochastic gradient method 1064.7. Stochastic dynamic programming 1074.7.1. Markov decision process 1084.7.2. Scenario tree 1094.8. Application to the reliability of mechanical systems 1114.8.1. Position and modeling of the reliability problem 1134.9. Using Matlab 121Part 2. Optimization 127Chapter 5. Combinatorial Optimization 1295.1. Introduction 1295.2. Symmetric TSP 1315.2.1. Historical overview 1325.2.2. Solving methods 1345.3. Asymmetric traveling salesman problem 1405.3.1. Variants of the ATSP 1405.3.2. Mathematical formulations 1425.3.3. Methods for solving the ATSP 1445.4. Vehicle routing problem 1485.4.1. Definition 1485.4.2. Fields of application 1495.4.3. Parameters of the VRP 1505.4.4. Variants of the VRP 1515.4.5. Mathematical formulation of the VRP 1535.4.6. Algorithmic complexity 1555.5. Selective routing problem 1565.5.1. Problems similar to the VRP 1575.5.2. Mathematical formulation 1575.6. Using Matlab 158Chapter 6. Unconstrained Nonlinear Programming 1616.1. Introduction 1616.2. Mathematical formulation 1616.2.1. Existence and uniqueness results 1626.3. Optimality conditions 1626.4. Quadratic problems 1636.4.1. Gradient method with optimal step size 1636.4.2. Conjugate gradient method 1646.5. Newton’s algorithm 1646.6. Methods of descent and linear search 1656.6.1. Presentation of methods of descent 1656.6.2. Method of greatest slope 1676.6.3. Acceptable step size 1686.6.4. Linear search 1696.6.5. Newton’s method with linear search 1706.7. Quasi-Newton methods 1716.7.1. DFP and BFGS methods 1726.8. Relaxation method 1736.9. Gradient method 1756.10. Least squares problem 1766.10.1. Gauss–Newton method 1766.10.2. Levenberg–Marquardt algorithm 1786.10.3. Kalman filter 1796.11. Direct search methods 1816.11.1. Nelder–Mead algorithm 1816.11.2. Torczon method 1836.12. Application to an identification problem 1836.13. Using Matlab 1856.13.1. The fminsearch function 1876.13.2. The fminunc function 1886.13.3. Relaxation method 190Chapter 7. Constrained Nonlinear Optimization 1937.1. Introduction 1937.2. Mathematical formulation 1937.3. Lagrange multipliers 1947.4. Optimization with inequality constraints 1957.4.1. First-order conditions of optimality 1957.4.2. Presentation of saddle points 1977.4.3. Saddle point and optimization 1987.4.4. Convex case 2017.5. Constrained minimization algorithms 2017.5.1. Relaxation method 2027.5.2. Projection method 2027.5.3. Exterior penalty method 2047.5.4. Uzawa’s algorithm 2057.6. Newton algorithms: SQP method 2067.6.1. Equality constraints 2077.6.2. Inequality constraints 2097.7. Application to structure optimization 2107.8. Using Matlab 2177.8.1. The fmincon function 2197.8.2. The fminbnd function 2207.8.3. Penalty method 221Appendices 229Appendix 1. Reminders from Linear Algebra 231Appendix 2. Reminders about functions from Rn into R 241Appendix 3. Optimization Toolbox 245Appendix 4. Software 249References 253Index 261