Linear and Nonlinear Optimization
Yinyu Ye
Department of Management Science and Engineering
Stanford University
Stanford, CA 94305, U.S.A
.
http://www.stanford.edu/~yyye
http://www.stanford.edu/class/msande211/
Yinyu Ye, Stanford, MS&E211 Lecture Notes #1
1
1
st
Day Questions
• 6 Homework (best five), 1 Midterm, 1 Final
– Regular Students: 35%*H + 25%*M + 40%*F
– Project Students: 35%*H + 25%*M + 40%*F + Project 20%
– No difference on taking 3 or 4 units
• No formula for cutoff between A/B etc.
• The more fun we all have, the more A’s I will give out.
• Textbook: Linear and Nonlinear Programming (LY 4
th
edition)
• Website: ??? & stanford.edu/class/msande211
• Programming ≠ Computer Science. The software use will help: Matlab, Excel
Solver or public free software. It is mostly a “PAPER AND PENCIL” class!
• Two projects: one on online LP model and one on LP algorithm implementation
• Friday’s problem sessions
• Form a study group
• My CA team
Yinyu Ye, Stanford, MS&E211 Lecture Notes #1
2
Introduction to Optimization
• Often consider the common goal of management science & engineering.
• Maximize or Minimize f(x)
for all x ϵ some set X
• Applications in:
– Applied Science, Engineering, Economics, Finance, Medicine,
Statistics, Business
– General Decision and Policy Making
• The famous Eighteenth Century Swiss mathematician and physicist
Leonhard Euler (1707-1783) proclaimed that “…nothing at all takes place
in the Universe in which some rule of maximum or minimum does not
appear.”
Yinyu Ye, Stanford, MS&E211 Lecture Notes #1
3
The Prototypical Optimization Problem
Minimize: f(x)
Subject to:
h
1
(x) = 0
...
h
m
(x) = 0
g
1
(x) < 0
...
g
r
(x) < 0
The Function could be:
x
1
+2x
2
, x
2
+2xy+2y
2
, xln(x)+e
y
, |x|+max{x,y}, etc
Yinyu Ye, Stanford, MS&E211 Lecture Notes #1
4
An Example: Maximum Flow
Yinyu Ye, Stanford, MS&E211 Lecture Notes #1
5
A B
6
11
12
5
10
13
4
5
How much flow can travel from A to B, given that each of the directed
connecting routes have flow limits?
