Continuous Optimization Algorithms, Course Outline
Software Engineering and Computer Science 4TE3 and 6TE3, Term I, 2011-2012
CES 723 / Algorithms for Unconstrained Optimization (first half), Term I, 2011-2012
CES 722 / Algorithms for Constrained Optimization (second half), Term I, 2011-2012
News:
Midterm Solution is Posted!
Calendar Description
Fundamental algorithms and general duality concepts of continuous optimization.
Special attention will be paid to the applicability of the algorithms, their information requirements and computational costs.
Practical engineering, business and financial problems will illustrate the power of continuous optimization techniques.
Aims
To learn fundamental algorithms and general duality concepts of continuous optimization.
Special attention will be paid to the applicability of the algorithms, their information requirements and computational costs.
Some practical engineering, business and financial problems will illustrate the power of continuous optimization techniques.
Content
Fundamentals:
- Generic frame of optimization algorithms
- Elementary convex analysis
- Classification of continuous optimization problems
Unconstrained optimization:
- Derivative-free (black-box) algorithms
- Line-search methods
- Gradient methods
- Newton and trust region methods
- Algorithms based on conjugate directions
Constrained optimization:
- Linear optimization:
- Pivoting algorithms
- Interior point methods
- Convex quadratic optimization
- General nonlinear optimization problems:
- Duality theory
- Reduced gradient methods
- Barrier methods
Applications:
- Engineering
- Business and finance
- Health care
Instructor
Christopher Anand, ITB 213, ext: 24895.
Office hours: I will stay after class every day to answer questions, but you can also make an appointment..
Teaching Assistant
Shefali Kulkarni-Thaker,Office hours: TBA
Schedule
Lectures/Tutorial:
Tuesday 11:30-12:20, Thursday 11:30-12:20, Friday 10:30-12:20, ABB/271
Lecture Notes
Lecture 1: Fundamentals ps, pdf.
Lecture 2: Line Search Methods ps, pdf.
More on Line Search Methods pdf.
Pros and cons of the Netwton's Method ps, pdf.
Goldstein-Armijo line-search ps, pdf.
Lecture 3: Unconstrained Optimization ps, pdf.
Lecture 4: Search Directions ps, pdf.
Midterm-preparation handout ps, pdf.
Lecture 5: Conjugate Gradient ps, pdf.
Lecture 6: Solving Sparse Systems with Low-Rank-Update ps, pdf.
Lecture 7: DFO-Trust Region Interpolation Algorithm ps, pdf.
Lecture 8: Duality ps, pdf.
Lecture 9: Algorithms for constrained NLO ps, pdf.
Reduced gradient handout ps, pdf.
Lecture 10: Interior Point Methods paper1,
paper2,
slides.
Final-preparation handout ps, pdf.
Optimization Problem Examples
Assignments
Assignment Cover Sheet
Assignment 1 (PDF)
Assignment 1 Sample Solution (PDF)
Assignment 2 (PDF) Wolfe-Line Search
Graduate Students Project
Project Description (for graduate students only!!!)
Tutorials
Textbooks and References
Recommended books:
- I. Griva, S.G. Nash and A. Sofer: Linear and Nonlinear Optimization, SIAM (2008). Available in the bookstore.
- S. Boyd and L. Vandenberghe, Convex Optimization, CUP. Available online.
- Philip E. Gill, Walter Murray and Margaret H. Wright:
Practical Optimization, Elsevier Academic Press (2004).
- G.N. Vanderplaats: Numerical
Optimization Techniques for Engineering Design With Applications,
VMA Engineering (1996).
- D.P. Bertsekas: Nonlinear
Programming, Athena Scientific (1999).
- Jorge Nocedal, Stephen J.Wright: Numerical
Optimization, Springer Series in Operations Research (1999).
Additional Resources
E. de Klerk, C. Roos, and T. Terlaky, Nonlinear
Optimization (pdf) (ps), 1999-2004, Delft.
V. Vinogradov, A Cook-Book of Mathematics, 1999, Prague.
Engineering Applications of Optimization
Software
- AMPL. To download AMPL, please click
AMPL. To look at examples for AMPL, please click examples.
- XPRESS
- MATLAB
Instructor's notice
- ONE letter size sheet (two sided) with your OWN HANDWRITTEN NOTES
will be permitted at the midterm and the final exam.
- You are strongly encouraged to solve the problems alone and in
time. If you use information from other sources (books, journals,
internet, private communication), you should make references in your
assignments. Not giving proper reference of sources imly a cas eof
academic dishonesty and results in a zero grade of the
assignment/project.
- Assignments must be handed in to the instructor or to the TA on
or before the due date. Late assignments will be marked with a late
penalty of 20% per day.
- Graded assignments and midterm will be returned in
the class or can be picked up at my office (ITB 220) or from the TA (ITB-116).
No responsibility for loss of assignments can be assumed by either
instructor or the Teaching Assistant.
- Any complains about grading should be done within two weeks of the
return date.
- If you do not write an exam or assignment and do not provide an
acceptable medical doctor's notice to the Associate Dean's office, the
exam or assignment will be marked with 0. No late medical doctor's
notices will be accepted.
Special Requirements for Graduate Students
Graduate students are required to
complete a project related to one of the main topics in the course
write a two-page review of a journal paper (only graduate students taking the course on the 700-level).
- Format of paper review:
- Free text, try to avoid to use much formulas;
- Discuss which kind of algorithm is studied in the paper;
- What kind of problems are solvable by using the algorithm;
- How it relates to the course material;
- What are the main theoretical results;
- If the algorithm was implemented or not;
- If it was implemented, evaluate the computational results;
- Practical applicability.
- Schedule of paper review:
- Go to the library to identify a suitable paper ASAP.
- See me at office hour to dicuss if the paper is indeed suitable
on or before October 26.
- Deliver your two page review by or before November 30.
- Project: Project Description.
Grading Scheme:
| Level |
400 |
600 |
700 |
| Assignments |
18 |
15 |
15 |
| Midterm |
32 |
25 |
20 |
| Final |
50 |
40 |
35 |
| Project |
-- |
20 |
15 |
| Review |
-- |
-- |
15 |
Note: the instructor reserves the right to conduct any deferred exams orally.
Solution to Exams 2011/2012
Examples of Previous Exams
Disabilities
Students with disabilities can receive accommodations to assist them
in the completion of assignments and exams. Please contact the Centre
for Student Development (http://csd.mcmaster.ca) for advice and for
arranging assistance. Students are also encouraged to talk to the
instructor about this issue.
Discrimination
"The Faculty of Engineering is concerned with ensuring an environment
that is free of all adverse discrimination. If there is a problem that
cannot be resolved by discussion among the persons concerned
individuals are reminded that they should contact the ir Department
Chair, the Sexual Harassment/Anti-Discrimination Officer (SHADO) or the
Human Rights Consultant, as soon as possible."
Academic Dishonesty
"Students are reminded that they should read and comply with the
Statements on Academic Ethics and the Senate Resolutions on Academic
Dishonesty as found in the Senate Policy Statements distributed at
registrations and available in the Senate Office."
Possible Changes
The instructor and university reserve the right to modify elements of the course during the term. The university may change the dates and deadlines for any or all courses in extreme circumstances. If either type of modification becomes necessary, reasonable notice and communication with the students will be given with explanation and the opportunity to comment on changes. It is the responsibility of the student to check their McMaster email and course websites weekly during the term and to note any changes.