Skip to main content
main-content

Über dieses Buch

This textbook presents a wide range of tools for a course in mathematical optimization for upper undergraduate and graduate students in mathematics, engineering, computer science, and other applied sciences. Basic optimization principles are presented with emphasis on gradient-based numerical optimization strategies and algorithms for solving both smooth and noisy discontinuous optimization problems. Attention is also paid to the difficulties of expense of function evaluations and the existence of multiple minima that often unnecessarily inhibit the use of gradient-based methods. This second edition addresses further advancements of gradient-only optimization strategies to handle discontinuities in objective functions. New chapters discuss the construction of surrogate models as well as new gradient-only solution strategies and numerical optimization using Python. A special Python module is electronically available (via springerlink) that makes the new algorithms featured in the text easily accessible and directly applicable. Numerical examples and exercises are included to encourage senior- to graduate-level students to plan, execute, and reflect on numerical investigations. By gaining a deep understanding of the conceptual material presented, students, scientists, and engineers will be able to develop systematic and scientific numerical investigative skills.

Inhaltsverzeichnis

Frontmatter

Basic optimization theory

Frontmatter

Chapter 1. INTRODUCTION

Formally, Mathematical Optimization is the process of
(i)
the formulation and
 
(ii)
the solution of a constrained optimization problem of the general mathematical form:
 
$$\begin{aligned} \mathop {{{\mathrm{minimize\, }}}}_{\mathrm{w.r.t.\ }{} \mathbf{x}}f(\mathbf{x}),\ \mathbf{x}=[x_1,x_2,\dots , x_n]^T\in {\mathbb R}^n \end{aligned}$$
subject to the constraints:
$$\begin{aligned} \begin{array}{ll} g_j(\mathbf{x})\le 0,&{}j=1,\ 2,\ \dots ,\ m\\ h_j(\mathbf{x})=0,&{}j=1,\ 2,\ \dots ,\ r \end{array} \end{aligned}$$
where \(f(\mathbf{x})\), \(g_j(\mathbf{x})\) and \(h_j(\mathbf{x})\) are scalar functions of the real column vector \(\mathbf{x}\). Mathematical Optimization is often also called Nonlinear Programming, Mathematical Programming or Numerical Optimization. In more general terms Mathematical Optimization may be described as the science of determining the best solutions to mathematically defined problems, which may be models of physical reality or of manufacturing and management systems. The emphasis of this book is almost exclusively on gradient-based methods. This is for two reasons. (i) The authors believe that the introduction to the topic of mathematical optimization is best done via the classical gradient-based approach and (ii), contrary to the current popular trend of using non-gradient methods, such as genetic algorithms GA’s, simulated annealing, particle swarm optimization and other evolutionary methods, the authors are of the opinion that these search methods are, in many cases, computationally too expensive to be viable. The argument that the presence of numerical noise and multiple minima disqualify the use of gradient-based methods, and that the only way out in such cases is the use of the above mentioned non-gradient search techniques, is not necessarily true as outlined in Chapters 6 and 8.
Jan A. Snyman, Daniel N. Wilke

Chapter 2. LINE SEARCH DESCENT METHODS FOR UNCONSTRAINED MINIMIZATION

Over the last 40 years many powerful direct search algorithms have been developed for the unconstrained minimization of general functions. These algorithms require an initial estimate to the optimum point, denoted by \(\mathbf{x}^0\). With this estimate as starting point, the algorithm generates a sequence of estimates \(\mathbf{x}^0\), \(\mathbf{x}^1\), \(\mathbf{x}^2\), \(\dots \), by successively searching directly from each point in a direction of descent to determine the next point. The process is terminated if either no further progress is made, or if a point \(\mathbf{x}^k\) is reached (for smooth functions) at which the first necessary condition in, i.e. \({\varvec{\nabla }} f(\mathbf{x})=\mathbf{0}\) is sufficiently accurately satisfied, in which case \(\mathbf{x}^*\cong \mathbf{x}^k\). It is usually, although not always, required that the function value at the new iterate \(\mathbf{x}^{i+1}\) be lower than that at \(\mathbf{x}^i\).
Jan A. Snyman, Daniel N. Wilke

Chapter 3. STANDARD METHODS FOR CONSTRAINED OPTIMIZATION

Consider the general constrained optimization problem:
$$\begin{aligned} {\mathop {{{\mathrm{minimize\,}}}}_\mathbf{x}}&f(\mathbf{x})\nonumber \\ \text {such that }&g_j(\mathbf{x})\le 0\ \ j=1,2,\dots , m\\&h_j(\mathbf{x})=0\ \ j=1,2,\dots , r.\nonumber \end{aligned}$$
The most simple and straightforward approach to handling constrained problems of the above form is to apply a suitable unconstrained optimization algorithm to a penalty function formulation of constrained problem. Unfortunately the penalty function method becomes unstable and inefficient for very large penalty parameter values if high accuracy is required. A remedy to this situation is to apply the penalty function method to a sequence of sub-problems, starting with moderate penalty parameter values, and successively increasing their values for the sub-problems. Alternatively, the Lagrangian function with associated necessary Karush-Kuhn-Tucker (KKT) conditions and duality serve to solve constrained problems that has led to the development of the Sequential Quadratic Programming (SQP) method that applies \(\text {Newton's}\) method to solve the KKT conditions.
Jan A. Snyman, Daniel N. Wilke

Chapter 4. BASIC EXAMPLE PROBLEMS

An extensive set of worked-out example optimization problems are presented in this chapter. They demonstrate the application of the basic concepts and methods introduced and developed in the previous three chapters. The reader is encouraged to attempt each problem separately before consulting the given detailed solution. This set of example problems is not only convenient for students to test their understanding of basic mathematical optimization, but also provides models for easily formulating additional optimization exercises.
Jan A. Snyman, Daniel N. Wilke

Chapter 5. SOME BASIC OPTIMIZATION THEOREMS

This chapter supplies the proofs for a number of theorems on which Chapters 1 to 4 have extensively relied on. In total nineteen proofs are presented of theorems that cover the characterization of unconstrained and constrained minima, saddle point conditions, conjugate gradient and Quasi-Newton methods.
Jan A. Snyman, Daniel N. Wilke

Gradient-based algorithms

Frontmatter

Chapter 6. NEW GRADIENT-BASED TRAJECTORY AND APPROXIMATION METHODS

In spite of the mathematical sophistication of classical gradient-based algorithms, certain inhibiting difficulties remain when these algorithms are applied to real-world problems. This is particularly true in the field of engineering, where unique difficulties occur that have prevented the general application of gradient-based mathematical optimization techniques to design problems. Difficulties include high dimensional problems, computational cost of function evaluations, noise, discontinuities, multiple local minima and undefined domains in the design space. All the above difficulties have been addressed in research done at the University of Pretoria over the past twenty years. This research has led to, amongst others, the development of the new optimization algorithms and methods discussed in this chapter.
Jan A. Snyman, Daniel N. Wilke

Chapter 7. SURROGATE MODELS

A Taylor series expansion of a function allows us to approximate a function \(f(\mathbf {x})\) at any point \(\mathbf {x}\), based solely on information about the function at a single point \(\mathbf {x}^{i}\). Here, information about the function implies zero order, first order, second order and higher order information of the function at \(\mathbf {x}^{i}\). Surrogate modelling offers an alternative approach to Taylor series for constructing approximations of functions. Instead of constructing approximations based on ever higher and higher order information at a single point, surrogate modelling approximates functions using lower order information at numerous points in the domain of interest. The advantage of such an approach is that it is (i) computationally inexpensive to approximate zero and first order information of the function at additional points in the domain, and that (ii) lower order information can be computed in parallel on distributed computing platforms. Hence, the approximation functions can be exhaustively optimized, while the computationally demanding evaluations of the actual function can be distributed over multiple cores and computers. We consider surrogates constructed using only function values, function values and gradients, and only gradients.
Jan A. Snyman, Daniel N. Wilke

Chapter 8. GRADIENT-ONLY SOLUTION STRATEGIES

Care is usually taken during the mathematical modelling and numerical computation of the scalar function \(f(\mathbf{x})\) to ensure that it is smooth and twice continuously differentiable. As highlighted in Section 6.5, the presence of numerical noise in the objective function is sometimes an unintended consequence of the complicated numerical nature frequently associated with the computation of the output function of a multi-disciplinary design optimization model. Numerical noise can also be the consequence of a deliberate computational savings strategy employed by a design engineer. This chapter is dedicated to explore alternative formulations and solution strategies when specifically dealing with piece-wise smooth discontinuous objective functions (Wilke et al. (2013b)). In essence, this chapter elaborates and formalizes the concepts and ideas introduced and hinted to in Section 6.5, that includes the handling of noisy objective functions and the use of gradient-only optimization.
Jan A. Snyman, Daniel N. Wilke

Chapter 9. PRACTICAL COMPUTATIONAL OPTIMIZATION USING PYTHON

Python is a general purpose computer programming language. An experienced programmer in any procedural computer language can learn Python very quickly. Python is remarkable in that it is designed to allow new programmers to efficiently master programming. The choice of including Anaconda Python for application of our mathematical programming concepts is motivated by the fact that Anaconda Python supports both symbolic and numerical mathematical operations as part of the installation. Python allows for an intuitive engagement with numerical computations. It is freely available and allows for additional functionality to be developed and extended. All algorithms in this text are made available in Python so as to allow the reader the use of the developed algorithms from the onset. This chapter is not an exhaustive treatise on Python and programming in general, but rather the minimum subset of Python required to implement formulated optimization problems and to solve them.
Jan A. Snyman, Daniel N. Wilke

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Wie können Sie Stress im Fernstudium bewältigen?

Ein Fernstudium erfordert ein hohes Maß an Selbstorganisation und Disziplin. Das bedeutet oft Stress - Prüfungsstress, Abgabetermine, Zeitdruck… Stress wird dann zum Problem, wenn wir ihn nicht mehr im Griff haben. Wenn wir die Ursachen und auch Auswirkungen von Stress verstehen, ist das ein wichtiger Schritt hin zu einem erfolgreichen Stressmanagement. Lesen Sie in diesem Auszug aus dem Fachbuch "Stressmanagement im Fernstudium" wie Sie Ihren Stress effektiv bewältigen können. Inklusive Selbsttest.
Jetzt gratis downloaden!

Bildnachweise