Instructor :  Professor Andrej Cherkaev, Department of Mathematics  Office: JWB 225  Email: cherk@math.utah.edu Tel : +1 801 - 581 6822  Fax: +1 801 - 581 4148	Search for the Perfection:  The image from Bridgeman Art Library

The desire for optimality (perfection) is inherent for humans. The search for extremes inspires mountaineers, scientists, mathematicians, and the rest of the human race. A beautiful and practical mathematical theory of optimization (i.e. search-for-optimum strategies) is developed since the sixties when computers become available. Every new generation of computers allows for attacking new types of problems and calls for new methods. The goal of the theory is the creation of reliable methods to catch the extremum of a function by an intelligent arrangement of its evaluations (measurements). This theory is vitally important for modern engineering and planning that incorporate optimization at every step of the complicated decision making process.

This course discusses classical direct search-for-optimum methods, such as Golden Mean, Conjugate Gradients, Modified Newton Method, methods for constrained optimization, including Linear and Quadratic Programming, and others. We will also briefly review genetic algorithms that mimic evolution and stochastic algorithms that account for uncertainties of mathematical models. The course work includes several homework assignments that ask to implement the studied methods and a final project, that will also be orally presented in the class.

The textbook Practical optimization by Philip Gill, Walter Murray, and Margaret H. Wright is interesting and readable (a British colleague of my recommended it as "a bloody good book"); the authors are among the top experts in the field. The book discusses pros and cons of various methods, often in the context of specific applications. The review part of the course will use the instructor's notes.

Prerequisite: Calculus, ODE, elementary programming.

To learn more about the course, please visit instructor's website www.math.utah.edu/~cherk

Contents. Preliminary Plan

1. Introduction (2 weeks) Modeling and Optimization.

Types of problems and methods, examples. Course projects.
2. Extremum of a function of one variable (2 weeks)

Fibbonacci and Golden Mean method, Secant method, Newton method.
HW 1
3. Unconstrained optimization (3 weeks)

Gradient search, Newton method and its modifications, Conjugate Gradient method, flip-flop type methods. Example: Mean Square approximation and its modifications.
HW 2
4. Constrained optimization (4 weeks)

Lagrangians and Augmented Lagrangian Methods. Linear Programming. Quadratic programming. Nonlinear programming. Duality.
HW 3
5. Review of various methods (2 week)

Stochastic search. Genetic algorithms. Discrete methods. Game approach.
HW 4
6. Projects presentations (1 week)

 
The final grade is composed as follows: 60% - the homework, 40% - the project.

---

Some Frivolous Remarks on Optimization

---

The inherent human desire to optimize is cerebrated in the famous Dante quotation:  All that is superfluous displeases God and Nature All that displeases God and Nature is evil. In engineering, optimal projects are considered beautiful and rational, and the far-from-optimal ones are called ugly and meaningless. Obviously, every engineer tries to create the best project and he/she relies on optimization methods to achieve the goal.

---

The general principle by Maupertuis proclaims:  If there occur some changes in nature, the amount of action necessary for this change must be as small as possible.   This principle  proclaims that the nature always finds the "best" way to reach a goal. It leads to an interesting inverse optimization problem: Find the essence of optimality of a natural "project."

---

Optimization theory is developed by ingenious and creative people, who regularly appeal to vivid common sense associations, formulating them in a general mathematical form. For instance, the theory steers numerical searches through canyons and passes (saddles), towards the peaks; it fights the curse of dimensionality, models evolution, gambling, and other human passions. The optimizing algorithms themselves are mathematical models of intellectual and intuitive decision making.


---

The essence of an optimization problem is: Catching a black cat in a dark room in minimal time. (A constrained optimization problem corresponds to a room full of furniture.) A light, even dim, is needed: Hence optimization methods explore assumptions about the character of response of the goal function to varying parameters and suggest the best way to change them. The variety of a priori assumptions corresponds to the variety of optimization methods. This variety explains why there is no silver bullet in optimization theory.