Some good books on nonlinear optimization:
1. Boris T. Polyak, Introduction to Optimization
The field of nonlinear optimization has benefited from several important
ideas developed in the Soviet Union. Some of these ideas underwent a
parallel development in the West, but others received inadequate attention
in English language textbooks. For this reason the publication of the
present book by a principal Soviet contributor is particularly valuable.
It represents what is probably the first comprehensive synthesis of the
nonlinear programming methodologies that are popular in the West and the
Soviet Union.
The reader will find here a systematic treatment of both classical
subjects, and topics little covered elsewhere—such as nondifferentiable
optimization, degenerate problems, and stochastic optimization methods.
Beyond this, however, this text has many significant merits. It gives
careful attention to both mathematical rigor and practical relevance. The
convergence analysis of numerical methods is done in a unified manner. A
systematic effort is made to chart the limits of the methodology by
providing performance analysis on difficult problems. There is a thoughtful
discussion of the practical solution process. A wealth of new or little
known material is included in the text and the exercises. Above all, the
book is written by a true expert with a refined understanding of the nature,
purpose, and limitations of nonlinear optimization and applied mathematics
in general.
2. Olvi L. Mangasarian, Nonlinear Programming
Twenty-five years have passed since the original edition of this book appeared; however, the topics covered are still timely and currently taught at the University
of Wisconsin as well as many other major institutions. At Wisconsin
these topics are taught in a course jointly listed by the Computer
Sciences, Industrial Engineering, and Statistics departments. Students
from these and other disciplines regularly take this course. Each
year I get a number of requests from the United States and abroad
for copies of the book and for permission to reproduce reserve
copies for libraries. I was therefore pleased when SIAM approached
me with a proposal to reprint the book in its Classics series. I believe
that this book is an appropriate choice for this series inasmuch as
it is a concise, igorous, yet accessible account o ' the fundamentals
of constrained optimization theory that is useful to both the beginning
student as well as the active researcher. I am appreciative that SIAM
has chosen to publish the book and to make the corrections that I
supplied. I am especially grateful to Vickie Kearn and Ed Block for their friendly and professional handling of the publication process. My hope is that the mathematical
programming community will benefit from this endeavor.
3. David G. Luenberger, Linear and Nonlinear Programming
This book is intended as a text covering the central concepts of practical optimization
techniques. It is designed for either self-study by professionals or classroom work at
the undergraduate or graduate level for students who have a technical background
in engineering, mathematics, or science. Like the field of optimization itself,
which involves many classical disciplines, the book should be useful to system
analysts, operations researchers, numerical analysts, management scientists, and
other specialists from the host of disciplines from which practical optimization applications
are drawn. The prerequisites for convenient use of the book are relatively
modest; the prime requirement being some familiarity with introductory elements
of linear algebra. Certain sections and developments do assume some knowledge
of more advanced concepts of linear algebra, such as eigenvector analysis, or some
background in sets of real numbers, but the text is structured so that the mainstream
of the development can be faithfully pursued without reliance on this more advanced
background material.
Although the book covers primarily material that is now fairly standard, it
is intended to reflect modern theoretical insights. These provide structure to what
might otherwise be simply a collection of techniques and results, and this is valuable
both as a means for learning existing material and for developing new results. One
major insight of this type is the connection between the purely analytical character
of an optimization problem, expressed perhaps by properties of the necessary conditions,
and the behavior of algorithms used to solve a problem. This was a major
theme of the first edition of this book and the second edition expands and further
illustrates this relationship.
As in the second edition, the material in this book is organized into three
separate parts. Part I is a self-contained introduction to linear programming, a key
component of optimization theory. The presentation in this part is fairly conventional,
covering the main elements of the underlying theory of linear programming,
many of the most effective numerical algorithms, and many of its important special
applications. Part II, which is independent of Part I, covers the theory of unconstrained
optimization, including both derivations of the appropriate optimality conditions
and an introduction to basic algorithms. This part of the book explores the
general properties of algorithms and defines various notions of convergence. Part III
extends the concepts developed in the second part to constrained optimization problems. Except for a few isolated sections, this part is also independent of Part I.
It is possible to go directly into Parts II and III omitting Part I, and, in fact, the
book has been used in this way in many universities. Each part of the book contains
enough material to form the basis of a one-quarter course. In either classroom use
or for self-study, it is important not to overlook the suggested exercises at the end of
each chapter. The selections generally include exercises of a computational variety
designed to test one’s understanding of a particular algorithm, a theoretical variety
designed to test one’s understanding of a given theoretical development, or of the
variety that extends the presentation of the chapter to new applications or theoretical
areas. One should attempt at least four or five exercises from each chapter. In
progressing through the book it would be unusual to read straight through from
cover to cover. Generally, one will wish to skip around. In order to facilitate this
mode, we have indicated sections of a specialized or digressive nature with an
asterisk∗.
There are several features of the revision represented by this third edition. In
Part I a new Chapter 5 is devoted to a presentation of the theory and methods
of polynomial-time algorithms for linear programming. These methods include,
especially, interior point methods that have revolutionized linear programming. The
first part of the book can itself serve as a modern basic text for linear programming.
Part II includes an expanded treatment of necessary conditions, manifested by
not only first- and second-order necessary conditions for optimality, but also by
zeroth-order conditions that use no derivative information. This part continues to
present the important descent methods for unconstrained problems, but there is new
material on convergence analysis and on Newton’s methods which is frequently
used as the workhorse of interior point methods for both linear and nonlinear
programming. Finally, Part III now includes the global theory of necessary conditions
for constrained problems, expressed as zero-th order conditions. Also interior
point methods for general nonlinear programming are explicitly discussed within
the sections on penalty and barrier methods. A significant addition to Part III is
an expanded presentation of duality from both the global and local perspective.
Finally, Chapter 15, on primal–dual methods has additional material on interior
point methods and an introduction to the relatively new field of semidefinite
programming, including several examples.
We wish to thank the many students and researchers who over the years have
given us comments concerning the second edition and those who encouraged us to
carry out this revision.
4. A. D. Ioffe, V. M. Tikhomirov, Theory of Extremal Problems
In recent years, the efforts of many mathematicians have been directed
toward investigating the subject of extremal problems from a unified
viewpoint, selecting common features in the methods for treating these
problems, and developing the necessary mathematical apparatus. As a
result, it has become possible to speak of the development of the general
theory of extremal problems.
Three topics in this theory have now acquired fully developed outlines.
These are the questions of the mathematical foundations of the theory, the
necessary conditions for an extremum, and - although to a lesser extent -
the existence of solutions. The part of the theory that is devoted to
numerical optimization methods is rapidly developing. The theory of
sufficient conditions has not yet reached its finished stage, although there
too certain results of a general nature have been obtained.
In this book, we tbuch upon all of the above mentioned basic topics in
the theory of extremal problems except numerical methods. The first five
chapters of the book are devoted to the mathematical apparatus and to
necessary conditions for an extremum. Sufficient conditions are studied in
the seventh chapter. In the eighth and ninth chapters, we present theorems
on the existence of solutions of problems in the calculus of variations and
optimal control, together with the mathematical apparatus necessary for
the proofs of these theorems. In the sixth chapter, we derive from the
general theory developed in the preceding chapters consequences for
classes of problems with special structure, namely, for linear, convex,
quadratic, and discrete problems. The last, tenth chapter is devoted to
certain applications of the theory to the solution of specific problems. We
have also included a separate collection of problems, many of which are
given with solutions In choosing the material, we did not try to encompass all the latest
results. The main purpose of the book is to explain and review the methods
that have arisen in the theory of extremal problems, and to show how these
methods are applied in particular areas, such as mathematical programming,
calculus of variations and optimal control.
The initial stimulus to create a general theory of extremal problems was
provided by the efforts to place the Pontrjagin maximum principle within
an abstract framework. These efforts brought about the investigation of
problems with a mixed, partly smooth and partly convex, structure. In this
book, problems of this type are investigated in detail. There are also other
possible approaches to these problems, and time will show which of them
will prove to be most fruitful.
This book is intended primarily for graduate and postgraduate students,
and for scientists who work in the area of solving optimization problems. In
writing it, we have utilized the experience of teaching in the Department of
Mathematics and Mechanics at Moscow State University. We hope that the
book can be used as a text in VF-;OUS courses related to optimization given
in universities and technical colleges.
In order to fully understand all parts of the book, one should have a
university course in functional analysis, but much of its contents are
intended for a broader audience.
The point is that the formulations of a majority of the most important
theorems, which give recipies for solving problems, can be mastered with
substantially less mathematical background than required for the understanding
of proofs. Therefore, we have tried to organize the presentation in
such a way that the formulations of the main results, the general remarks
concerning them, and the solutions of prablems, be separate from the
proofs.
It is not necessary to read the chapters in their given order. Many
subjects can be studied independently of the other material. Let us indicate
several such possibilities. Sections 2.1, 2.2,2.4, and 6.4 form an elementary
course in the calculus of variations. In essence, these sections are based
only on facts from classical analysis. An initial course in linear and convex
programming is contained in 000.3, 1.3, 6.1, and 7.3. Chapter 1 and
007.1-7.3 are devoted to the subject “Necessary and sufficient conditions
for an extremum in minimization problems in linear spaces.” Sections
2.1-2.3, 6.3, 7.4, 10.4, and Subsection 9.2.4 form an extended course in the
calculus of variations, although insufficient attention is given here to
Hamilton-Jacobi theory. In Chapter 8 and 449.1 a d 9.2, we treat the
questions of the existence of a solution to optimal control problems.
Chapter 8 together with 49.3 gives an idea of duality methods in optimal
control theory. Chapters 1-5, 8, and 9 form an extended course in optimal
control theory. Finally, Chapters 3, 4, and 8 contain a reasonably detailed
introduction to infinite-dimensional convex analysis.
At first, we planned to include in the book a number of other subjects,
such as extensions of variational problems, sliding and singular regimes,
and numerical methods. However, we have been unable to treat these
matters for lack of space. We should also mention several other problems
of importance which are not touched upon in the book. These concern
primarily the relationships between the calculus of variations and classical
mechanics, Hamilton-Jacobi theory, and dynamic programming.
In the remarks which conclude the Introduction, we indicate monographs
and articles that pertain to subjects which remain outside the scope
of this book.
In conclusion, we would like to express our gratitude to B.T. Poljak, who
kindly provided certain materials that helped in the development of our
approach to the classification of extremal problems. Our thanks go to M.A.
Krasnosel’skii, who looked over the manuscri,pt and made a number of
useful suggestions, and to V.M. Alekseev and S.V. Fomin, with whom we
discussed various matters related to the presentation of the material.
Numerous discusdons with A.A. Miljutin were of great importance to us.
We are grateful to A.V. Barykin, B. Luderer, G.G. Magaril-Il’jaev, E.S.
Polovinkin, M.A. Rvachev, V.M. Safro, M.I. Stesin, and to M. Tagiev, who
helped us with the preparation of the manuscript.