Numerical Optimization (Springer Series in Operations Research and Financial Engineering) 
asked by caramel on November 18, 2006 7:01 AM
Numerical Optimization presents a comprehensive and up-to-date description of the most effective methods in continuous optimization. It responds to the growing interest in optimization in engineering, science, and business by focusing on the methods that are best suited to practical problems.
For this new edition the book has been thoroughly updated throughout. There are new chapters on nonlinear interior methods and derivative-free methods for optimization, both of which are used widely in practice and the focus of much current research. Because of the emphasis on practical methods, as well as the extensive illustrations and exercises, the book is accessible to a wide audience. It can be used as a graduate text in engineering, operations research, mathematics, computer science, and business. It also serves as a handbook for researchers and practitioners in the field. The authors have strived to produce a text that is pleasant to read, informative, and rigorous - one that reveals both the beautiful nature of the discipline and its practical side.
There is a selected solutions manual for instructors for the new edition.
Reviews
0%
0%
This books focuses on practical methods for continuous unconstrained
and constrained optimization. It does not cover problem
formulation. In all methods, the presentation tries to motivate the
approach using basic principles, rather than throw a mechanical
algorithm to the user. Thus the algorithms all make intuitive
sense. This is best demonstrated in the presentation of the KKT
conditions for constrained optimization. Below are a list of topics
covered.
Unconstrained optimization looks for a point with gradient 0. In
terms of search directions, most importantly are two: steepest
descent, Newton direction. Newton direction is based on a quadratic
approximation, and the direction is obtained by solving for the
gradient to be 0 using Newton method. We also know quasi-Newton and
Conjugate gradient. The control is in line search and trust region
method to make sure that for each step there is sufficient
descent. Line search modifies Hessian to make it positive definite.
Constrained optimization is based on KKT condition on Lagrangian
function. KKT just says that at the solution, the gradient of the
objective function is a linear combination of the gradients of the
active constraints. All interior point method form the KKT equation
and solve it using Newton equation method. Inequality constrains become
equality by adding slack variables and simple bounds on the slack
variables. The solver will make the solution to balance the total
reduction (because of the complementarity constraints) of all
variables, and the closeness to the boundary (one variable become 0).
The active set method tries to guess a set of active constraints,
minimize it by ignoring the reset of the constraints, try to update to
the minimizer. If this makes an inactive constraint become active, add
it into the active set. Once we are at the minimizer of the current
active set, we calculate the Lagrange Multipliers, if an inequality
active constraint's multiplier is negative, it is dropped from the
active set and the next iteration begin. Under some assumptions, the
next iteration will be able to reduce the objective function. Because
the subproblem only has equality constraint, can be solved using KKT
equation directly or null space method. For linear programming
problem, the addition of a constraint and dropping a constraint from
the active set happens at the same time. Each active set corresponds
to a basic feasible point.
There are also penalty, barrier, modified multiplier method to convert
the problem to solving a series of unconstrained problem. The
sequential quadratic programming method is to approximate the
objective function by quadratic model and use linear approximation to
the constraints. Solve the resulting QP subproblem using either active
set/interior point/direct KKT/gradient projection. The search
direction is safeguarded in line search by following the Wolfe
condition.
and constrained optimization. It does not cover problem
formulation. In all methods, the presentation tries to motivate the
approach using basic principles, rather than throw a mechanical
algorithm to the user. Thus the algorithms all make intuitive
sense. This is best demonstrated in the presentation of the KKT
conditions for constrained optimization. Below are a list of topics
covered.
Unconstrained optimization looks for a point with gradient 0. In
terms of search directions, most importantly are two: steepest
descent, Newton direction. Newton direction is based on a quadratic
approximation, and the direction is obtained by solving for the
gradient to be 0 using Newton method. We also know quasi-Newton and
Conjugate gradient. The control is in line search and trust region
method to make sure that for each step there is sufficient
descent. Line search modifies Hessian to make it positive definite.
Constrained optimization is based on KKT condition on Lagrangian
function. KKT just says that at the solution, the gradient of the
objective function is a linear combination of the gradients of the
active constraints. All interior point method form the KKT equation
and solve it using Newton equation method. Inequality constrains become
equality by adding slack variables and simple bounds on the slack
variables. The solver will make the solution to balance the total
reduction (because of the complementarity constraints) of all
variables, and the closeness to the boundary (one variable become 0).
The active set method tries to guess a set of active constraints,
minimize it by ignoring the reset of the constraints, try to update to
the minimizer. If this makes an inactive constraint become active, add
it into the active set. Once we are at the minimizer of the current
active set, we calculate the Lagrange Multipliers, if an inequality
active constraint's multiplier is negative, it is dropped from the
active set and the next iteration begin. Under some assumptions, the
next iteration will be able to reduce the objective function. Because
the subproblem only has equality constraint, can be solved using KKT
equation directly or null space method. For linear programming
problem, the addition of a constraint and dropping a constraint from
the active set happens at the same time. Each active set corresponds
to a basic feasible point.
There are also penalty, barrier, modified multiplier method to convert
the problem to solving a series of unconstrained problem. The
sequential quadratic programming method is to approximate the
objective function by quadratic model and use linear approximation to
the constraints. Solve the resulting QP subproblem using either active
set/interior point/direct KKT/gradient projection. The search
direction is safeguarded in line search by following the Wolfe
condition.
reviewed by shirley49 on November 19, 2006 7:56 PM
0%
0%
Within the range that this intends to cover, it is an outstnading reference. The first two chapters lay out the mathematical preliminaries, and get the book off to a fast start. The next four chapters discuss basic classes of algorithms for nonlinear optimization and choices of stopping criteria. This includes conjugate gradient methods adapted from the CG method for solving linear systems - since, in nearly all cases, non-linear optimization breaks down into iterations over locally linear approximations.
The emphasis thoughout is on practical algorithms and efficient computation. First and second derivatives are used heavily throughout this book, but symbolic differentiation of the nonlinear functions is usually unavailable. As a result, significant emphasis goes into approximation techniques, and into the common cases of sparse systems. Despite its heavily mathematical orientation, this really is a book about the practicalities of computation.
A bit further on, Nocedal and Wright get to the topic that brought me to this book in the first place: nonlinear least squares. As always, the presentation is clear but very dense. Other topics follow, including solutions of nonlinear equations (i.e. minimizing the error in approximating the exact solution), simplex and polynomial-order techniques for linear systems, and more.
This is a book for someone who's completely at home with differential calculus and linear algebra, and who's willing to spend time extracting the full meaning from terse descriptions. It's also for a reader who is comfortable translating dense notation into working numerical code - not a task to be undertaken lightly. That reader will be rewarded with wide-ranging and very practical discussions of many problems and the techniques used for each. As it says in the introduction, this doesn't address the whole world of optimization problems - combinatorics, discrete problems, and jagged search spaces are not the subject here. If, however, this book touches on your topic, you'll find it handled very well. This has my highest recommendation.
//wiredweird
The emphasis thoughout is on practical algorithms and efficient computation. First and second derivatives are used heavily throughout this book, but symbolic differentiation of the nonlinear functions is usually unavailable. As a result, significant emphasis goes into approximation techniques, and into the common cases of sparse systems. Despite its heavily mathematical orientation, this really is a book about the practicalities of computation.
A bit further on, Nocedal and Wright get to the topic that brought me to this book in the first place: nonlinear least squares. As always, the presentation is clear but very dense. Other topics follow, including solutions of nonlinear equations (i.e. minimizing the error in approximating the exact solution), simplex and polynomial-order techniques for linear systems, and more.
This is a book for someone who's completely at home with differential calculus and linear algebra, and who's willing to spend time extracting the full meaning from terse descriptions. It's also for a reader who is comfortable translating dense notation into working numerical code - not a task to be undertaken lightly. That reader will be rewarded with wide-ranging and very practical discussions of many problems and the techniques used for each. As it says in the introduction, this doesn't address the whole world of optimization problems - combinatorics, discrete problems, and jagged search spaces are not the subject here. If, however, this book touches on your topic, you'll find it handled very well. This has my highest recommendation.
//wiredweird
reviewed by geri1956 on November 22, 2006 3:13 AM
0%
0%
With a simple language gives a very good description of the theory of constrained and unconstrained optimization.
The algorithms are described in a simple manner without excessive mathematical charge. Very good for the new learners of optimization theory, and also useful for the readers with skills in optimization.
The algorithms are described in a simple manner without excessive mathematical charge. Very good for the new learners of optimization theory, and also useful for the readers with skills in optimization.
reviewed by formula on November 28, 2006 6:28 PM
0%
0%
The book does a very good job in teaching non-discrete mathematical programming techniques. But, it is not an introductory book. The reader is supposed to know linear algebra and numerical analysis to a certain extent. Most of the modern techniques are presented, but the layout is a little chaotic- the sequence of subjects could be made better. So, I would have preferred to give it 4.5 stars (which is impossible). However, that does not take away the fact that the book is excellent. I have used it primarily for modelling financial portfolios, and I am sure it can be used as a guide for other applications.
Conclusion: A little difficult, but well worth the time and money involved
reviewed by savvy on November 29, 2006 10:39 AM
0%
0%
This book by Nocedal and Wright has several attractive features. For one, it is probably the most "state-of-the-art" of the existing texts in optimization and as such covers most of the modern methods. It also has a nice section on LP (simplex as well as interior point methods) for someone interested in a course on optimization as opposed to NONLINEAR optimization (which is what I was looking for). Another strength is that it covers many of the algebra-related details very well. My only major complaint is that it seems to not get into any of the methods designed specifically for convex programs - these while admittedly less general are often very powerful. For example, there is NO mention even of Geometric Programming which has wide application in design. The convex simplex method also isn't mentioned anywhere. Finally,I wonder why there is no mention of the generalized reduced gradient (GRG) method.
All in all, a good book to own I think...
reviewed by macfan on November 29, 2006 2:51 PM