Continuous Optimization Algorithms, Course Outline
Soft. Eng. and Comp. Sci. 4TE3 and 6TE3, Term I, 2009-2010
CES 723 / Algorithms for Unconstrained Optimization (first half), Term I, 2009-2010
CES 722 / Algorithms for Constrained Optimization (second half), Term I, 2009-2010
News:
If circumstances beyond my control disrupt campus activities, the number, schedule and type of assignments and exams may change, and may include assignments submitted electronically, group presentations and oral exams.
Given the likelihood that there will be no class lists, it is very important that you submit any written assignment in person and show your McMaster ID card.
I'm working on minor revisions, so if you let me know what kind of applications you are interested in, I may be able to include them in the course.
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 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 problems will illustrate the power of continuous optimization techniques.
Context
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
Instructor
Christopher Anand, ITB 213, ext: 24895.
Office hours: by appointment, or ask for instant messenger details
Teaching Assistant
Zhenghua Nie, ITB 229, Office hours: Monday, 12:30-13:30, ITB 229
Schedule
Lectures:
Tuesday, Wednesday, Friday, 12:30-13:20, BSB/136
Tutorials
Wednesday 10:30-11:20, JHE/326H.
Lecture Notes
Lecture 1: Fundamentals ps, pdf.
Lecture 2: Line Search Methods ps,pdf.
Lecture 3: Unconstrained Optimization ps, pdf.
Lecture 4: Search Directions 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.
Lecture 10: Interior Point Methods paper1,
paper2,
slides.
Lecture 11: Cone Constraints pdf.
Assignments
Assignment Cover Sheet
Assignment 1 [pdf][ps] [Solution(pdf) [Solution(ps)] [Code: ass1q6.m ass1q6_newton.m ass1q6_obj.m] (due October 7)
Assignment 2
ps, pdf (due November 11)
Matlab functions to be completed bfgs.m.
Sample function files ffunc.m,
gfunc.m and hfunc.m for Rosenbrock's banana function.
Assignment 2 Solutions ps, pdf
Assignment 3 [pdf] [ps] (due Novermber 30)
Assignment 3 Solutions ps, pdf
Graduate Students Project
Project Description (for graduate students only!!!)
Tutorials
Labs
- Lab 1
For the bonus, in addition to passing by the huckleberry bush and apple tree, we also have to stop at the cow, at location (-3,-3), and avoid hitting the tree at location (-2,-2), before going back home.
- Lab 2
Textbooks and References
These books are availble in the bookstore.
Additional Resources
E. de Klerk, C. Roos, and T. Terlaky, Nonlinear
Optimization (pdf) (ps), 1999-2004, Delft.
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.
- raded assignments and midterm will be returned in
the class or can be picked up at the drop-in centre ITB-101.
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 |
The instructor reserves the right to conduct any deferred exams orally.
Assignments 2008
Assignment 1
ps, pdf
(due October 6)
Assignment 1 Solutions ps, pdf
Assignment 2
ps, pdf (due November 10, the deadline is postponed till November 13)
Matlab functions to be completed descentgolden.m,
trustregion.m and bfgs.m.
Sample function files ffunc.m,
gfunc.m and hfunc.m for Rosenbrock's banana function.
The table for question 4: as2q4table.pdf or as2q4table.rtf.
Assignment 3
ps, pdf
(due November 26, postponed till December 1)
In question 1(b) you can skip computing the null-space formulation and use the unconstrained reformulation from 1(ab) in question 1(c)
Download AMPL Student Edition with MINOS solver
Download Student Version of LOQO solver
Examples of calling MINOS and LOQO solvers from AMPL can be found here
Solution to Exams 2009/2010
- Midterm solutions [pdf] [ps]
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.