Über die Autorin bzw. den Autor

Jan Brinkhuis is Associate Professor of Finance and Mathematical Methods and Techniques at the Econometric Institute of Erasmus University, Rotterdam. Vladimir Tikhomirov holds the Chair of Optimal Control in the Department of Mechanics and Mathematics at the Lomonosov Moscow State University.

Von der hinteren Coverseite

"Well written and well organized. The book's examples are highly varied, interesting and well thought out."--Steinar Hauan, Carnegie Mellon University

"An extremely interesting introduction to the field of mathematical optimization. I know of no other book in the field that offers so many illustrations of the applicability of deep theoretical issues in optimization. It will command a broad audience, from beginners to experts."--Kees Roos, Delft University of Technology

Aus dem Klappentext

"Well written and well organized. The book's examples are highly varied, interesting and well thought out."--Steinar Hauan, Carnegie Mellon University

"An extremely interesting introduction to the field of mathematical optimization. I know of no other book in the field that offers so many illustrations of the applicability of deep theoretical issues in optimization. It will command a broad audience, from beginners to experts."--Kees Roos, Delft University of Technology

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Optimization: Insights and Applications

PRINCETON UNIVERSITY PRESS

Contents

Preface..................................................................................xiNecessary Conditions: What Is the Point?.................................................1Chapter 1. Fermat: One Variable without Constraints......................................3Chapter 2. Fermat: Two or More Variables without Constraints.............................85Chapter 3. Lagrange: Equality Constraints................................................135Chapter 4. Inequality Constraints and Convexity..........................................199Chapter 5. Second Order Conditions.......................................................261Chapter 6. Basic Algorithms..............................................................273Chapter 7. Advanced Algorithms...........................................................325Chapter 8. Economic Applications.........................................................363Chapter 9. Mathematical Applications.....................................................391Chapter 10. Mixed Smooth-Convex Problems.................................................417Chapter 11. Dynamic Programming in Discrete Time.........................................441Chapter 12. Dynamic Optimization in Continuous Time......................................475Appendix A. On Linear Algebra: Vector and Matrix Calculus................................503Appendix B. On Real Analysis.............................................................519Appendix C. The Weierstrass Theorem on Existence of Global Solutions.....................537Appendix D. Crash Course on Problem Solving..............................................547Appendix E. Crash Course on Optimization Theory: Geometrical Style.......................553Appendix F. Crash Course on Optimization Theory: Analytical Style........................561Appendix G. Conditions of Extremum from Fermat to Pontryagin.............................583Appendix H. Solutions of Exercises of Chapters 1–4.................................601Bibliography.............................................................................645Index....................................................................................651

Chapter One

When a quantity is the greatest or the smallest, at that moment its flow is neither forward nor backward. I. Newton

? How to find the maxima and minima of a function f of one variable x without constraints?

1.0 SUMMARY

You can never be too rich or too thin. W. Simpson, wife of Edward VIII

One variable of optimization. The epigraph to this summary describes a view in upper-class circles in England at the beginning of the previous century. It is meant to surprise, going against the usual view that somewhere between too small and too large is the optimum, the "golden mean." Many pragmatic problems lead to the search for the golden mean (or the optimal trade-off or the optimal compromise). For example, suppose you want to play a computer game and your video card does not allow you to have optimal quality ("high resolution screen") as well as optimal performance ("flowing movements"); then you have to make an optimal compromise. This chapter considers many examples where this golden mean is sought. For example, we will be confronted with the problem that a certain type of vase with one long-stemmed rose in it is unstable if there is too little water in it, but as well if there is too much water in it. How much water will give optimal stability? Usually, the reason for such optimization problems is that a trade-off has to be made between two effects. For example, the height of houses in cities like New York or Hong Kong is determined as the result of the following trade-off. On the one hand, you need many people to share the high cost of the land on which the house is built. On the other hand, if you build the house very high, then the specialized costs are forbidding.

Derivative equal to zero. All searches for the "golden mean" can be modeled as problems of optimizing a function f of one variable x, minimization (maximization) if f(x) represents some sort of cost (profit). The following method, due to Fermat, usually gives the correct answer: "put the derivative of f equal to zero," solve the equation, and – if the optimal x has to be an integer – round off to the nearest integer. This is well known from high school, but we try to take a fresh look at this method. For example, we raise the question why this method is so successful. The technical reason for this is of course the great strength of the available calculus for determining derivatives of given functions. We will see that in economic applications a conceptual reason for this success is the equimarginal rule. That is, rational decision makers take a marginal action only if the marginal benefit of the action exceeds the marginal cost; they will continue to take action till marginal benefit equals marginal cost.

Snellius's law. The most striking application of the method of Fermat is perhaps the derivation of the law of Snellius on the refraction of light on the boundary between two media—for example, water and air. This law was discovered empirically. The method of Fermat throws a striking light on this technical rule, showing that it is a consequence of the simple principle that light always takes the fastest path (at least for small distances).

1.1 INTRODUCTION

Optimization and the differential calculus. The first general method of solution of extremal problems is due to Pierre de Fermat (1608–1665). In 1638 he presented his idea in a letter to the prominent mathematicians Gilles Persone de Roberval (1602–1675) and Marin Mersenne (1588–1648). Scientific journals did not yet exist, and writing a letter to learned correspondents was a usual way to communicate a new discovery. Intuitively, the idea is that the tangent line at the highest or lowest point of a graph of a function is horizontal. Of course, this tangent line is only defined if the graph has no "kink" at this point.

The exact meaning became clear later when Isaac Newton (1642/43–1727) and Gottfried von Leibniz (1646–1716) invented the elements of classical analysis. One of the motivations for creating analysis was the desire of Newton and Leibniz to find general approaches to the solution of problems of maximum and minimum. This was reflected, in particular, in the title of the first published work devoted to the differential calculus (written by Leibniz, published in 1684). It begins with the words "Nova methodus pro maximis et minimis ...."

The Fermat theorem. In his letter to Roberval and Mersenne, Fermat had—from our modern point of view—the following proposition in mind, now called the (one-variable) Fermat theorem (but he could express his idea only for polynomials): if x is a point of local minimum (or maximum) of f, then the main linear part of the increment is equal to zero. The following example illustrates how this idea works.

Example 1.1.1 Verify the idea of Fermat for the function f(x) = x².

Solution....