MSC 380.8 – unique # 03705
ORI 391Q.1 – unique # 17580
Fall 2003
Instructor
Leon S. Lasdon
Office Phone: 471-9433
E-Mail: lasdon@mail.utexas.edu
Office: CBA North 5.244
Office hours: MW 2:15-3:30, TTh 3:30-4:30, or by appointment
Teaching Assistant: Wei Chen
TA office: CBA 1.308C
TA office hours: TTh 2:30-530P
TA e-mail:
wei.chen@phd.bus.utexas.edu
Course web page: www.utexas.edu/courses/lasdon
Course Objectives
A. Theory: Derivation and uses of the Kuhn-Tucker first order necessary conditions for optimality, second order optimality conditions, saddle points, and the Lagrangian dual problem. Basic theorems on convex functions, sets, and problems. Convergence and rate of convergence results for various algorithms. Principles of search heuristics and branch and bound and outer linearization methods for mixed integer problems. Basic concepts of global optimization.
B. Algorithms: understand the derivation and comparative advantages of the following classes of algorithms:
· Generalized Reduced Gradient (GRG)
· Successive Quadratic Programming (SQP)
· Successive Linear Programming (SLP)
· Penalty and Barrier Methods, Exact and Inexact
Use given implementations of these algorithms, observe and analyze the results.
C. Applications
a. Learn to use stand-alone Fortran or C NLP solvers to solve problems coded in Fortran or C.
b. Learn to use the Excel Solver and GAMS.
c. Understand the relative advantages and limitations of the above tools.
d. Learn about several important current NLP application areas, including
- gasoline blending, refinery models
- electric power: hydroelectric planning, optimal load flows
- financial applications: Markowitz asset allocation, multi-period models, robust optimization
- optimal control
- water resources models
- others of interest to the class.
e. Improve your skills as a modeler by
formulating a variety of problems in several modeling languages, solving, and
analyzing and understanding the solution.
Learn principles of good modeling as well as things to avoid.
Instructional
Methods
The basic approach is to learn by doing. We will organize small learning groups, that work together to solve problems in class. These problems are stated on the plan for each class. Last years plans are on the course website, and are a reasonable guide to those used in the current year. We then discuss the problem solutions. This is interspersed with lecture segments when needed. There will also be occasional outside speakers, who will explain how they use course topics in their work.
TEXT: LINEAR and NONLINEAR PROGRAMMING by S. Nash and A. Sofer, McGraw-Hill, 1996.
Supplementary Readings: Readings packet at Paradigm Publishing, corner of 24th St. near Guadalupe
WEBSITES: This year's syllabus and last year's session plans are available at www.utexas.edu/courses/lasdon, and this years syllabus and session plans will be on the class website on the University’s “Blackboard” system.
Beginning
Fall 2001, web-based, password-protected class sites
will be available for all accredited courses taught at The University. Syllabi,
handouts, assignments and other resources are types of information that may be
available within these sites. Site activities could include exchanging
e-mail, engaging in class discussions and chats, and exchanging files. In
addition, class e-mail rosters will be a component of the sites. Students
who do not want their names included in these electronic class rosters must
restrict their directory information in the Office of the Registrar, Main
Building, Room 1. For information on restricting
directory information see: http://www.utexas.edu/student/registrar/catalogs/gi00-01/app/appc09.html.
You will also visit several optimization websites as part of this class, and will be asked to
report on what you found in the next class. Some of these sites are listing in readings
packet 3
Midterm Exam 1/3, Final Exam 1/3, Homework and Cases 1/3. Exams will be take-home exams, done individually, due in one week. Homework and cases will be done in groups of three, who will work cooperatively, hand in a single solution, and all receive the same grade on that solution.
Class Schedule and
Assigned Readings
See the class plans on the course website for a detailed schedule of each of last years classes. This years will differ somewhat. A summary for this year is provided below.
|
Class |
Topic |
Readings (T=Text, R=Readings Packet) |
|
1-2 |
Introduction to NLP, convexity, Basic NLP algorithm, |
T chap. 1-2, R 1-4 |
|
3-4 |
Unconstrained optimization: Newton's method, line search and trust region methods to ensure convergence |
T chap. 10, R 5,9 |
|
5-6 |
Unconstrained optimization: trust regions, steepest descent and its convergence and convergence rate, matrix condition number |
T chap. 11-12, R 6-8, R10 |
|
7-8 |
quasi-Newton and conjugate gradient methods |
T chap 11-12 |
|
9 |
Spreadsheet optimization |
Use of Excel Solver, R 24 |
|
10-11 |
The GAMS modeling language |
R 31 |
|
12-14 |
Constrained problems-necessary and sufficient conditions |
T 14.5, R 11-12 |
|
15 |
Hand out take-home midterm, Saddle points and duality |
|
|
16 |
Saddle points, duality, Lagrangian relaxation |
T 14.8, R 13 |
|
17 |
Reduced gradient methods |
R 14-16 |
|
18 |
Penalty and Barrier methods |
T chap. 16, R17 |
|
19 |
Successive quadratic programming (SQP) |
T 15.5, R 18-19 |
|
20 |
Successive linear programming (SLP), algorithm comparison |
R20-21
|
|
21-22 |
NLP applications including financial asset allocation using mean-variance models |
T chap. 17, R 29 |
|
23-25 |
Mixed integer nonlinear programming models and algorithms |
R30 |
|
26 |
Piece-by piece approach, global optimization |
R26 |
|
27-28 |
Global optimization, NLP applications, hand out take--home final exam |
R27-28 |