COMP/MATH 380 OPTIMIZATION Syllabus
The textbook for this
course is Practical Optimization Methods:
With Mathematica®
Applications, by M. Asghar Bhatti (Springer-Verlag TELOS, 2000). Notes and handouts (through hardcopy and
file access) will also be used. You
will have access to all the files in our COMP 380 course folder (subdirectory)
on the Q-Drive during this course.
Selected class assignments, sample programs and data, and other guidelines
will be stored in this folder. A recommended text for this course is Schaum’s Outlines - Mathematica, by
Eugene R. Don. It is published by
McGraw Hill, 2001. It will be used for
the Mathematica material in it. You
will be using several tools during this course including: Mathematica®
(using packages and the author’s Optimization Toolbox CD/ROM), a (TI) graphing
calculator, and possibly a high-level language (e.g., C++, Fortran).
NOTES:
·
Wittenberg has a site license for fifteen (15)
simultaneous users of Mathematica® and this is monitored through the
use of a batch file.
·
This course is a combination of applied computer science
and applied mathematics. The theory
and practice learned in previous courses is extensively used here.
A discipline-related maturity is assumed (i.e., if you don't understand
something immediately, you will work until you do understand it). If you still are unable to understand, then
it is assumed that you will go over the material with the instructor well
before the material appears on an examination.
·
All work on assignments, quizzes and exams is normally
to be done only by the student himself or herself; there is to be no
collaboration unless specifically indicated.
All classes are to be attended and any necessary problem clarifications
will be made in class.
·
Attendance is mandatory and all lab work will be done at
the scheduled time. Collaboration with
other students in this course is normally permitted at all times. Each student is still responsible for
understanding all of the components of each solution, however.
·
You will find that the use of a graphing calculator and
Mathematica will be necessary for your problem analysis and understanding of
the material in this course. (Everyone
is responsible for their own copy of the CD/ROM code that comes with the
textbook. Wittenberg does not have a
site license for it. A Mathematica handout will be provided (it
is the student's responsibility to learn the needed constructs). Mathematica 4.2 is now installed on the C-Drive
of many of the PCs in the Science Building.
·
All
the references below are to the textbook unless otherwise indicated. Since one prerequisite for this course is
COMP 150, it is assumed that you are familiar with using high-level programming
language constructs through the topics of 1-D and 2-D arrays. The other prerequisite is MATH 201 (Calculus
I) and will be continually used throughout this course. It is also assumed that you will be familiar
with important concepts of vector and matrix algebra (although this will be
reviewed). The course has a
co-requisite of MATH 205.
PART I: RECOGNIZING AN OPTIMIZATION PROBLEM AND ITS
SOLUTION
Chapter 1: Optimization Problems - Mathematical
Programming (MP) Problems
Mathematical Modeling and
Optimization Problem Formulation
Unconstrained vs. Constrained
Problems
Standard Forms of MP Problems
Solutions of MP Problems
Appendix: An Introduction to Mathematica®
Basic
Manipulations in Mathematica
Mathematica Notebooks
Types of Arithmetic - Exact vs.
Floating-Point DP
Lists (Matrices and Vectors)
Eigenvalues and Eigenvectors of
Matrices
Solving Equations
Differential Calculus (Regular and
Partial Derivatives - First and Second)
Plotting in Mathematica
Programming in Mathematica
Packages in Mathematica
Other Languages: C++ and FORTRAN
Programming
Style and Documentation
Chapter 2: Graphical Optimization
Procedure
for Graphical Optimization
Optimization
Toolbox Routines
GraphicalSolution Function
Graphical
Optimization Examples
Chapter 3: Mathematical Preliminaries
Scalars, Vectors and Matrices
Hyperplanes and Half-Spaces
Vector
and Matrix P-Norms (P=1,2,¥)
Solving Linear Equations and
Nonlinear Equations
Matrix Inverses
N-Dimensional Functions: Regular and
Contour Plots
Regular and Partial Derivatives
Gradient Vector and Hessian Matrix
Quadratic Forms
Convex and Concave Functions
Convex
Regions
Convex Programming (CP) Problems
Exam 1
Chapter 4: Optimality Conditions
Optimality Conditions for
Unconstrained Problems
Karush-Kuhn-Tucker (KKT or KT)
Conditions and their Geometry
Sensitivity Analysis
Optimality Conditions for Convex
Problems
Second-Order Sufficient Conditions
Lagrangian Duality
PART II: DETERMINING THE SOLUTION TO AN OPTIMIZATION
PROBLEM
Chapter 5: Unconstrained Problems
Unconstrained
Minimization Strategy: Direction Vector and Step Length
Univariate
Minimization
N-Dimensional
Minimization
Descent
Direction
Line
Search Techniques - Step Length Calculations
Unconstrained
Minimization Techniques
Concluding
Remarks
Chapter 6: Linear Programming (LP) Problems
LP Minimization Formulation
Solving a Linear System
Basic Solutions of an LP Problem
Simplex Method and Graphical
Interpretation
Special Situations
Post-Optimality and Sensitivity
Analysis
Duality
Assignment and Transportation
Problems
Integer and Mixed-Integer Problems
Concluding Remarks
Exam 2
Chapter 7: Interior Point Methods
Optimality Conditions for LP
Primal-Dual Methods
Chapter 8: Quadratic Programming (QP)
Karush-Kuhn-Tucker Conditions
Specialized QP Methods
Frank Wolfe Method
Applications
Chapter 9: Constrained Nonlinear Problems - Nonlinear
Programming (NLP)
Convex and Non-convex Programming
Normalization
Barrier and Penalty Methods
Sequential Unconstrained
Minimization Techniques (SUMT)
Linearization of a Nonlinear Problem
Sequential Linear and Quadratic
Programming (SLP and SQP) Strategies
Applications
Exam 3
Final Exam (Comprehensive)
INSTRUCTOR:
James
L. Noyes. Office: Room 329B Science.
Hours: Regular hours are posted
on office door; also by appointment.
Telephone: 327-7858 (Office).
E-Mail: jnoyes@wittenberg.edu (normally checked
3-4 times daily on weekdays).
For more information, see
the instructor’s home page on the Web.
COURSE
GOALS:
·
Learning about mathematical optimization problem
forms, models, and applications.
·
Gaining insight into optimization problems and
the way in which algorithms work.
·
Learning how to identify local and global
optimal solutions to a given problem.
·
Learning how to develop and apply
optimization-related theorems.
·
Understanding which algorithms should be used
for a given problem.
·
Learning how to derive and use some of the more
fundamental algorithms.
·
Learning how to estimate the solution accuracy
and convergence rates.
·
Effectively and efficiently developing computer
science code implementations of algorithms.
·
Effectively using Mathematica in analyzing and
solving problems and checking solutions.
CLASS MEETINGS:
Classes will normally meet in Room 316 in Science
Hall MWF 3:00p.m.-4:00p.m. for lectures and Tuesday 9:00a.m.-11:10a.m. for the
laboratory. Final Exam time for this
class is Monday morning, December 16, 2002, from 8:00am until 11:00am. It will not be given at a different time. You are expected to attend all classes
and labs and to participate with both ideas and questions.
ASSIGNMENTS
(INCLUDING POSSIBLE PROJECTS):
There will be two
types of assignments: programming assignments that implement or use algorithms
and analytical assignments to analyze properties of problems, algorithms, their
accuracy, and their convergence properties (Mathematica should be used for
both). Good code design, style and documentation
are (still) important in all of the coding assignments. Clear and precise logical steps and writing
are important in all of the analytical assignments. However, the main grading criteria is correctness. If you
have a question on any of the material you should raise it in class as soon as
possible. Assignments will be accepted
in class. They may also be turned in at
the instructor’s office by 5:00pm on the day assigned with no penalty. After that, up to 10% of the total points
possible will be DEDUCTED per day
late (including weekends). Assignments
will not be accepted after three (3) days unless there is some type of emergency
situation or special arrangements are made ahead of time. If the instructor is not in the office, the
assignments should be slid under the office door (or under the department door,
if it is locked) - be sure the instructor’s name is on it.
LABS:
Students ARE
permitted to work with other students on laboratory assignments, but each
student must hand in his or her own work by the end of the period and be sure
that they can explain ALL of it.
Typically all assignments will be in the form of annotated Mathematica
notebooks.
TESTS (EXAMS,
QUIZZES, AND FINAL):
Exams and quizzes are typically (although not
always) based upon what has been covered by lecture notes, assignments,
handouts, and text material. Exams,
labs and quizzes CANNOT be taken
later without a legitimately excused absence (e.g., death in the family,
personal illness, class field trip, or a necessary official Witt-sponsored
activity). This excuse must be in
writing via e-mail, and the instructor must be notified as far in ADVANCE as possible.
GRADING (ALL POINT VALUES
ARE APPROXIMATE):
The grade for this
course will be based upon assignments (including projects), labs, and exams (up
to approximately 1000 points). These
consist of: assignments (approximately 300 points), labs (approximately 200
points), three equally-spaced tests (100 points each), and a comprehensive
final examination (200 points). Some of
these points may also be obtained from unannounced quizzes. Assignments will be
due by 5:00pm on the day assigned with up to 10% of the total points possible
DEDUCTED per day late; assignments will not be accepted after three (3) days
unless special arrangements have been made.
Lab work is only accepted at the end of the period. Quizzes are typically unannounced and cannot
be taken later. Exams cannot be taken
later without advance notice and an official excused absence. All programming assignments MUST initially
be submitted with a new 3.5" diskette with a signed listing with the class
account, date and time shown. The
diskette will contain the code itself as shown in the listing, and any
appropriate data and I/O (e.g., in a Mathematica notebook). Class attendance and participation is very
important and will have a positive effect on your grade. The final grade for this course will be
based upon the individual class average relative to the rest of the class. If the score distribution starts in the 90%‑100%
range, then a ten‑point spread will probably be used (e.g., 90% and above
would be A-, A, or A+, 80% up to 90% is B-, B, B+, etc.).
ACADEMIC DISHONESTY:
Academic dishonesty of any kind on homework
or exams is not acceptable. This
includes, but is not limited to, plagiarism or collaboration with another
student on homework assignments, projects, or tests. At a minimum it will typically result in a reduced score
(typically 0) for all parties involved and it could result in a failing grade
for this course. In addition, there may
be other University sanctions. See your Student
Handbook for additional details regarding academic dishonesty.