Autumn, MW 8:30-9:50, Winter, TTH 8:30-9:50, 2001-2002
Optimization is concerned in general with a wide range of situations in
which the maximum or minimum of a function is sought over some set specified by
side conditions. It's one of the areas
of modern mathematics in which "pure" and "applied" are
most closely linked. There is continual interaction between computation,
modeling, and frontier developments in analysis --- called "variational
analysis"--- which are essential because classical analysis never was
confronted with the issues that now arise, and it can't cope with them. Researchers have had to develop properties
of convexity, the tangent and normal cone geometry of sets with nonsmooth
boundaries, "subgradients" of functions not having gradients, and
even the "subdifferentiation" of set-valued mappings.
The 514 course doesn't itself get into much of the "variational
analysis" (that comes more in 515), but it does serve as an excellent example
of the breadth of the subject while focusing on a particular area of major
interest. Networks, also known as
directed graphs, are basic tool for modeling many situation such as finding optimal
paths from one "state" (or "location") to another under
constraints, or even ascertaining the existence of such a path. But they also support a vast array of
applications that, often in ingenious ways, can be viewed in terms of the
optimization of "flows" or "potentials". The subject revolves in part around discrete
analogs of familiar concepts in calculus such as flows across boundaries of
regious, or line integrals, but also it relies on modern ideas like duality in
optimization.
The organization of the material is largely algorithmic": virtually
every proof is articulated in the form of an iterative, constructive procedure. The algorithms fit within each other as
modules, just as one theorem can be derived by way of another. Students get valuable experience with the
algebraic way of thinking that goes into the statement and justification of
algorithms, but also in the way that rigorous mathematical concepts can be
applied to a multitude of practical applications. This is a fine way to learn about mathematics in its broader
scope of organizing our thinking about complex issues, moreover ones that don't
only come out of traditional themes in mathematics itself.
The 514 course uses a textbook:
Network Flows and Monotropic Optimization (Rockafellar), which can be
perused in the Math Library. A
selection of material in Chapters 1 -- 8 is covered. Grades are based on weekly assignments of exercises from this
book.
An advantage of 514, especially for those interested in trying something
a bit different, is that there are no course prerequisites; all that's needed is the ability for
rigorous mathematical thinking along with the desire to understand more deeply
what mathematics is all about.
Networks: nodes and arcs, incidences, flows and divergence, potentials and tension, circulations and augmentation, dynamic flows.
Paths and cuts:
incidences, connectedness, existence of paths, painted network algorithm
and its theoretical implications.
Flows and capacities: capacity intervals, flux across a cut, max
flow problem and algorithm, max flow min cut theorem, feasible flows, feasible
distribution theorem and algorithm.
Analysis of flows:
integrality theorem and its applications, conformal realization, trees,
extreme flows.
Matching theory and assignment problems:
matching with a compatibility relation, matching algorithm via max flow,
existence and optimality of combinatorial assignments, bottleneck optimization.
Potentials and spans: optimal
paths, max tension min path theorem, min path algorithm, max tension models,
feasible potentials, feasible differential algorithm.
Optimal flows and potentials:
optimal distribution problem and algorithm, optimal differential problem
and algorithm, duality with respect to convex costs.
The purpose of this course is to provide an introduction to general
problems of maximizing or minimizing a function of several or very many
variables relative to a set defined by various constraints: finite-dimensional "continuous"
optimization. The emphasis is on issues
connected with properly formulating a problem and characterizing its possible
solutions. This partly involves
studying concepts in analysis like convexity and nonsmoothness, which can make
a big difference in approaches to computation.
It also involves getting acquainted with a range of applications of
optimization, and gaining experience from working with some specific
examples. Although numerical methods are
not fully addressed until the follow-up course, 516, basic ideas of how such
methods operate are covered in order to furnish an overview. Computers are used by students to solve
certain problems arising from the examples, but this is a matter of entering
data and invoking existing software (Matlab) rather than programming anything
new. Concepts of game theory are used
to highlight the important phenomenon of duality, where solving a given
minimization problem of convex type is equivalent to solving a certain
maximization problem in a different set of variables.
There is no textbook for the the 515 course; rather, there is a highly
developed set of lecture notes, which will be made available to the
students. Grades are based on weekly
assignments of exercised designed to bring out all aspects of the
material. NOTE: It is not necessary to have taken 514 in
order to take 515.
Examples of applications:
engineering design, management of systems, identification of parameters,
variational principles, optimal control; a variety of models in linear and
quadratic programming.
Problem formulation:
equality and inequality constraints, objectives, feasible and optimal
solutions, format classification, penalties, nonsmoothness; questions of
existence and stability of solutions.
Unconstrained optimization: concepts of local information, directions of descent, line search;
conditions for local optimality, the role of convexity; questions of
convergence.
Constraint geometry:
tangent and normal vectors, characterization of solutions over simple sets;
convex sets, polyhedral sets and boxes.
Minimization subject to smooth constraints: optimality conditions under a constraint
qualification, Lagrangian function and Lagrange multipliers, saddle point
expressions of optimality in the presence of convexity.
Games and duality:
elementary introduction to game theory and its use in interpreting Lagrange
multipliers; dual problems of optimization, the duality theorem of linear
programming, decentralization and Lagrangian decomposition.
Composite optimization:
penalty expressions, alternative problem formats for handling hard versus soft
constraints, extensions of basic results to this setting.