Second Edition

OPTIMIZATION
FOR ENGINEERING
DESIGN
Algorithms and Examples

Kalyanmoy Deb
OPTIMIZATION FOR ENGINEERING DESIGN
 Optimization for
Engineering Design
Algorithms and Examples
SECOND EDITION

KALYANMOY DEB
Department of Mechanical Engineering
Indian Institute of Technology Kanpur

New Delhi-110001
2012
OPTIMIZATION FOR ENGINEERING DESIGN—Algorithms and Examples, Second Edition
Kalyanmoy Deb

© 2012 by PHI Learning Private Limited, New Delhi. All rights reserved. No part of this book
may be reproduced in any form, by mimeograph or any other means, without permission in
writing from the publisher.

ISBN-978-81-203-4678-9

The export rights of this book are vested solely with the publisher.

Twelfth Printing (Second Edition) . . . . . . November, 2012

Published by Asoke K. Ghosh, PHI Learning Private Limited, M-97, Connaught Circus,
New Delhi-110001 and Printed by Rajkamal Electric Press, Plot No. 2, Phase IV, HSIDC,
Kundli-131028, Sonepat, Haryana.
 To
My Parents
Contents

Preface................................................................................................ xi
Preface to the First Edition................................................................ xiii
Acknowledgements.............................................................................. xvii

1. Introduction............................................................................. 1–42
1.1 Optimal Problem Formulation   2
1.1.1 Design Variables   3
1.1.2 Constraints  4
1.1.3 Objective Function   5
1.1.4 Variable Bounds   6
1.2 Engineering Optimization Problems   8
1.2.1 Design and Manufacturing   9
1.2.2 Modelling  17
1.2.3 Data Fitting and Regression   21
1.2.4 Control Systems   22
1.2.5 Inverse Problems   24
1.2.6 Scheduling and Routing   26
1.2.7 Data Mining   31
1.2.8 Intelligent System Design   32
1.3 Classification of Optimization Algorithms   35
1.4 Summary  40
References  40

2. Single-variable Optimization Algorithms.............................. 43–84

2.1 Optimality Criteria   44
2.2 Bracketing Methods   46
2.2.1 Exhaustive Search Method   46
2.2.2 Bounding Phase Method   49
2.3 Region-Elimination Methods   51
2.3.1 Interval Halving Method   52
vii
viii   Contents

2.3.2 Fibonacci Search Method   54

2.3.3 Golden Section Search Method   57
2.4 Point-Estimation Method   60
2.4.1 Successive Quadratic Estimation Method   60
2.5 Gradient-based Methods   63
2.5.1 Newton-Raphson Method   63
2.5.2 Bisection Method   65
2.5.3 Secant Method   67
2.5.4 Cubic Search Method   68
2.6 Root-finding Using Optimization Techniques   71
2.7 Summary  74
References  75
Problems  75
Computer Programs   78

3. Multivariable Optimization Algorithms...............................85–142

3.1 Optimality Criteria   85
3.2 Unidirectional Search   87
3.3 Direct Search Methods   89
3.3.1 Box’s Evolutionary Optimization Method   90
3.3.2 Simplex Search Method   95
3.3.3 Hooke-Jeeves Pattern Search Method   98
3.3.4 Powell’s Conjugate Direction Method   103
3.4 Gradient-based Methods   108
3.4.1 Cauchy’s (Steepest Descent) Method   112
3.4.2 Newton’s Method   114
3.4.3 Marquardt’s Method   118
3.4.4 Conjugate Gradient Method   120
3.4.5 Variable-metric Method (DFP Method)   124
3.5 Summary  128
References  129
Problems  130
Computer Program   134

4. Constrained Optimization Algorithms...............................143–262

4.1 Kuhn-Tucker Conditions   144
4.2 Lagrangian Duality Theory   151
4.3 Transformation Methods   154
4.3.1 Penalty Function Method   154
4.3.2 Method of Multipliers   162
4.4 Sensitivity Analysis   167
4.5 Direct Search for Constrained Minimization   173
4.5.1 Variable Elimination Method   173
4.5.2 Complex Search Method   177
4.5.3 Random Search Methods   182
Contents ix

4.6 Linearized Search Techniques   185

4.6.1 Frank-Wolfe Method   186
4.6.2 Cutting Plane Method   192
4.7 Feasible Direction Method   203
4.8 Quadratic Programming   212
4.8.1 Sequential Quadratic Programming   218
4.9 Generalized Reduced Gradient Method   224
4.10 Gradient Projection Method   232
4.11 Summary   239
References  242
Problems  243
Computer Program  253

5. Specialized Algorithms.......................................................263–291
5.1 Integer Programming   264
5.1.1 Penalty Function Method   265
5.1.2 Branch-and-Bound Method   270
5.2 Geometric Programming   278
5.3 Summary  288
References    288
Problems  289

6. Nontraditional Optimization Algorithms...........................292–368

6.1 Genetic Algorithms   292
6.1.1 Working Principles   293
6.1.2 Differences between GAs and Traditional Methods   298
6.1.3 Similarities between GAs and Traditional Methods   301
6.1.4 GAs for Constrained Optimization   311
6.1.5 Other GA Operators   314
6.1.6 Real-coded GAs   315
6.1.7 Multi-objective GAs   319
6.1.8 Other Advanced GAs   323
6.2 Simulated Annealing   325
6.3 Global Optimization   330
6.3.1 Using the Steepest Descent Method   330
6.3.2 Using Genetic Algorithms   332
6.3.3 Using Simulated Annealing   334
6.4 Summary  335
References  336
Problems  340
Computer Program   348

Appendix:  Linear Programming Algorithms...................369–415

Index............................................................................417–421
Preface

The first edition of this book which was published in 1995 has been well
tested at IIT Kanpur and at many other universities over the past 17
years. It is unusual to have the second edition of a book being published
after so many years, but it is the nature of the book that prompted me to
wait till there is enough feedback from students and teachers before I was
sitting down to revise the first edition. The optimization algorithms laid
out in this book do not change with time, although their explanations and
presentations could have been made better. But the feedback I received from
several of my students and a large number of instructors has been positive
and I had not much motivation to revise the book in a major way. The
simplified presentation of optimization algorithms remains as a hallmark
feature of this book. Purposefully, a few topics of optimization were left out
in the first edition, which I have now included in this edition. Specifically, a
section on quadratic programming and its extension to sequential quadratic
programming have been added. Genetic algorithms (GAs) for optimization
have been significantly modified in the past 17 years, but if I have to
provide an account of all the current methods of GAs, it will be a book of
its own. But I could not resist to include some details on real-parameter
GAs and multi-objective optimization. Readers interested in knowing more
about GAs are encouraged to refer to most recent books and conference
proceedings on the topic.
A major modification has been made to the Linear Programming (LP)
chapter in the Appendix. Several methods including sensitivity analysis
procedures have been added so that students can get a comprehensive idea
of different LP methods. While making the modifications, the simplicity
of the algorithms, as it was presented in the first edition, has been kept.
Finally, more exercise problems are added not only to this chapter, but to
all previous chapters of this revised book.

xi
xii   Preface

I sincerely hope the second edition becomes more useful in getting a

proper understanding of different optimization algorithms discussed in this
book. I would appreciate very much if any typing error or comments can
be directly sent to my email address: [email protected] or kalyanmoy.deb@
gmail.com.

Kalyanmoy Deb
Preface to the First Edition

Many engineers and researchers in industries and academics face difficulty

in understanding the role of optimization in engineering design. To many
of them, optimization is an esoteric technique used only in mathematics
and operations research related activities. With the advent of computers,
optimization has become a part of computer-aided design activities. It
is primarily being used in those design activities in which the goal is
not only to achieve just a feasible design, but also a design objective. In
most engineering design activities, the design objective could be simply to
minimize the cost of production or to maximize the efficiency of production.
An optimization algorithm is a procedure which is executed iteratively by
comparing various solutions till the optimum or a satisfactory solution
is found. In many industrial design activities, optimization is achieved
indirectly by comparing a few chosen design solutions and accepting
the best solution. This simplistic approach never guarantees an optimal
solution. On the contrary, optimization algorithms begin with one or more
design solutions supplied by the user and then iteratively check new design
solutions in order to achieve the true optimum solution. In this book, I
have put together and discussed a few popular optimization algorithms and
demonstrated their working principles by hand-simulating on a simple
example problem. Some working computer codes are also appended for
limited use.
There are two distinct types of optimization algorithms which are in
use today. First, there are algorithms which are deterministic, with specific
rules for moving from one solution to the other. These algorithms have
been in use for quite some time and have been successfully applied to
many engineering design problems. Secondly, there are algorithms which are
stochastic in nature, with probabilistic transition rules. These algorithms
are comparatively new and are gaining popularity due to certain properties
which the deterministic algorithms do not have. In this book, probably
for the first time, an attempt has been made to present both these types
xiii
xiv   Preface to the First Edition

of algorithms in a single volume. Because of the growing complexity in

engineering design problems, the designer can no longer afford to rely on a
particular method. The designer must know the advantages and limitations
of various methods and choose the one that is more efficient to the problem
at hand.
An important aspect of the optimal design process is the formulation
of the design problem in a mathematical format which is acceptable to an
optimization algorithm. However, there is no unique way of formulating
every engineering design problem. To illustrate the variations encountered
in the formulation process, I have presented four different engineering
design problems in Chapter 1. Optimization problems usually contain
multiple design variables, but I have begun by first presenting a number
of single-variable function optimization algorithms in Chapter 2. The
working principles of these algorithms are simpler and, therefore, easier to
understand. Besides, these algorithms are used in multivariable optimization
algorithms as unidirectional search methods. Chapter 3 presents a number
of algorithms for optimizing unconstrained objective functions having
multiple variables. Chapter 4 is an important one in that it discusses a
number of algorithms for solving constrained optimization problems—most
engineering design optimization problems are constrained. Chapter 5 deals
with two specialized algorithms for solving integer programming problems
and geometric programming problems. Two nontraditional optimization
algorithms, which are very different in principle than the above algorithms,
are covered in Chapter 6. Genetic algorithms—search and optimization
algorithms that mimic natural evolution and genetics—are potential
optimization algorithms and have been applied to many engineering design
problems in the recent past. Due to their population approach and parallel
processing, these algorithms have been able to obtain global optimal
solutions in complex optimization problems. Simulated annealing method
mimics the cooling phenomenon of molten metals. Due to its inherent
stochastic approach and availability of a convergence proof, this technique
has also been used in many engineering design problems. Chapter 6 also
discusses the issue of finding the global optimal solution in a multioptimal
problem, where the problem contains a number of local and global optimal
solutions and the objective is to find the global optimal solution. To
compare the power of various algorithms, one of the traditional constrained
optimization techniques is compared with both the nontraditional
optimization techniques in a multioptimal problem.
Some algorithms in Chapter 4 use linear programming methods, which
are usually taught in operations research and transportation engineering
related courses. Sometimes, linear programming methods are also taught
in first or second-year undergraduate engineering courses. Thus, a detailed
discussion of linear programming methods is avoided in this book. Instead,
a brief analysis of the simplex search technique of the linear programming
method is given in Appendix A.
 Optimization For Engineering Design
Algorithms And Examples

25%
OFF

Author : Deb And

Publisher : PHI Learning ISBN : 9788120346789
Kalyanmoy

Type the URL : http://www.kopykitab.com/product/10271

Get this eBook