Optimization in Engineering Sciences: Exact Methods

The purpose of this book is to present the main methods of static and dynamic optimization. It has been written within the framework of the European Union project – ERRIC (Empowering Romanian Research on Intelligent Information Technologies), funded by the EU’s FP7 Research Potential program and developed in cooperation between French and Romanian teaching researchers. Through the principles of various proposed algorithms (with additional references) this book allows the interested reader to explore various methods of implementation such as linear programming, nonlinear programming – particularly important given the wide variety of existing algorithms, dynamic programming with various application examples and Hopfield networks. The book examines optimization in relation to systems identification; optimization of dynamic systems with particular application to process control; optimization of large scale and complex systems; optimization and information systems.

Table of Contents:
Foreword ix Preface xi List of Acronyms xiii Chapter 1. Linear Programming 1 1.1. Objective of linear programming 1 1.2. Stating the problem 1 1.3. Lagrange method 4 1.4. Simplex algorithm 5 1.4.1. Principle 5 1.4.2. Simplicial form formulation 5 1.4.3. Transition from one simplicial form to another 7 1.4.4. Summary of the simplex algorithm 9 1.5. Implementation example 11 1.6. Linear programming applied to the optimization of resource allocation 13 1.6.1. Areas of application 13 1.6.2. Resource allocation for advertising 13 1.6.3. Optimization of a cut of paper rolls 16 1.6.4. Structure of linear program of an optimal control problem 17 Chapter 2. Nonlinear Programming 23 2.1. Problem formulation 23 2.2. Karush–Kuhn–Tucker conditions 24 2.3. General search algorithm 26 2.3.1. Main steps 26 2.3.2. Computing the search direction 29 2.3.3. Computation of advancement step 33 2.4. Monovariable methods 33 2.4.1. Coggin’s method (of polynomial interpolation) 34 2.4.2. Golden section method 36 2.5. Multivariable methods 39 2.5.1. Direct search methods 39 2.5.2. Gradient methods 57 Chapter 3. Dynamic Programming 101 3.1. Principle of dynamic programming 101 3.1.1. Stating the problem 101 3.1.2. Decision problem 101 3.2. Recurrence equation of optimality 102 3.3. Particular cases 104 3.3.1. Infinite horizon stationary problems 104 3.3.2. Variable horizon problem 104 3.3.3. Random horizon problem 104 3.3.4. Taking into account sum-like constraints 105 3.3.5. Random evolution law 106 3.3.6. Initialization when the final state is imposed 106 3.3.7. The case when the necessary information is not always available 107 3.4. Examples 107 3.4.1. Route optimization 107 3.4.2. The smuggler problem 109 Chapter 4. Hopfield Networks 115 4.1. Structure 115 4.2. Continuous dynamic Hopfield networks 117 4.2.1. General problem 117 4.2.2. Application to the traveling salesman problem 121 4.3. Optimization by Hopfield networks, based on simulated annealing 123 4.3.1. Deterministic method 123 4.3.2. Stochastic method 125 Chapter 5. Optimization in System Identification 131 5.1. The optimal identification principle 131 5.2. Formulation of optimal identification problems 132 5.2.1. General problem 132 5.2.2. Formulation based on optimization theory 133 5.2.3. Formulation based on estimation theory (statistics) 136 5.3. Usual identification models 138 5.3.1. General model 138 5.3.2. Rational input/output (RIO) models 140 5.3.3. Class of autoregressive models (ARMAX) 142 5.3.4. Class of state space representation models 145 5.4. Basic least squares method 146 5.4.1. LSM type solution 146 5.4.2. Geometric interpretation of the LSM solution 151 5.4.3. Consistency of the LSM type solution 154 5.4.4. Example of application of the LSM for an ARX model 157 5.5. Modified least squares methods 158 5.5.1. Recovering lost consistency 158 5.5.2. Extended LSM 162 5.5.3. Instrumental variables method 164 5.6. Minimum prediction error method 168 5.6.1. Basic principle and algorithm 168 5.6.2. Implementation of the MPEM for ARMAX models 171 5.6.3. Convergence and consistency of MPEM type estimations 174 5.7. Adaptive optimal identification methods 175 5.7.1. Accuracy/adaptability paradigm 175 5.7.2. Basic adaptive version of the LSM 177 5.7.3. Basic adaptive version of the IVM 182 5.7.4. Adaptive window versions of the LSM and IVM 183 Chapter 6. Optimization of Dynamic Systems 191 6.1. Variational methods 191 6.1.1. Variation of a functional 191 6.1.2. Constraint-free minimization 192 6.1.3. Hamilton canonical equations 194 6.1.4. Second-order conditions 195 6.1.5. Minimization with constraints 195 6.2. Application to the optimal command of a continuous process, maximum principle 196 6.2.1. Formulation 196 6.2.2. Examples of implementation 198 6.3. Maximum principle, discrete case 206 6.4. Principle of optimal command based on quadratic criteria 207 6.5. Design of the LQ command 210 6.5.1. Finite horizon LQ command 210 6.5.2. The infinite horizon QL command 217 6.5.3. Robustness of the LQ command 221 6.6. Optimal filtering 224 6.6.1. Kalman–Bucy predictor 225 6.6.2. Kalman–Bucy filter 231 6.6.3. Stability of Kalman–Bucy estimators 234 6.6.4. Robustness of Kalman–Bucy estimators 235 6.7. Design of the LQG command 239 6.8. Optimization problems connected to quadratic linear criteria 245 6.8.1. Optimal control by state feedback 245 6.8.2. Quadratic stabilization 248 6.8.3. Optimal command based on output feedback 249 Chapter 7. Optimization of Large-Scale Systems 251 7.1. Characteristics of complex optimization problems 251 7.2. Decomposition techniques 252 7.2.1. Problems with block-diagonal structure 253 7.2.2. Problems with separable criteria and constraints 267 7.3. Penalization techniques 283 7.3.1. External penalization technique 284 7.3.2. Internal penalization technique 285 7.3.3. Extended penalization technique 286 Chapter 8. Optimization and Information Systems 289 8.1. Introduction 289 8.2. Factors influencing the construction of IT systems 290 8.3. Approaches 292 8.4. Selection of computing tools 296 8.5. Difficulties in implementation and use 297 8.6. Evaluation 297 8.7. Conclusions 298 Bibliography 299 Index 307

About the Author :
Pierre Borne is Professor at École Centrale de Lille in France. He has received honorary degrees from the University of Moscow, Russia, the Politehnica University of Bucharest, Romania and the University of Waterloo, Canada. He is a Fellow of the IEEE. Dumitru Popescu is Professor at Politehnica University of Bucharest, Romania in the fields of Advanced Control and Systems Optimization and also Associate Professor at major universities of France and Italy. He is Director of the Research Center in Automatics, Process Control and Computers (APCC) affiliated to Politehnica University of Bucharest, a member of the IFAC Technical Committees for the Control of Bioprocesses and Chemical Processes and a corresponding member of the Romanian Academy of Technical Sciences. Florin Gh. Filip is a researcher in the fields of applied IT and decision support systems. He was elected as a member of the Romanian Academy in 1991 and president of the “IT” section in 2011. He was Vice President of the Romanian Academy from 2001 to 2010. Dan Stefanoiu is Professor in the fields of Signal Processing and System Identification at Politehnica University of Bucharest. In 2002 he was elected as a member of the American Romanian Academy of Sciences and Arts (ARA).