Math 565
Continuous Optimization
Fritz Keinert
Spring 2015

Announcements

(May 11) Final scores are posted in Blackboard. I will return the last assignments to the mailboxes in the Math Department, for the students who have one. If you send me a campus address, I can return the assignments there. Otherwise, give me a call or email if you want to stop by and pick it up.

Have a good summer!

Homework

Links will become active when the homeworks are available. Solutions to homeworks, and current scores, will be posted in Blackboard.

HW 1, due Thursday, Jan 29
HW 2, due Thursday, Feb 19
HW 3, due Thursday, Mar 12 elnino.dat extra credit
HW 4, due Thursday, Apr 9
HW 5, due Thursday, Apr 30
Final HW, due Thursday, May 7, at 2pm optimization projects truss

Instructor

Fritz KeinertFritz Keinert
464 Carver
294-5223
keinert@iastate.edu
Office hours: Tu noon-2pm, Th 10am-noon, or by appointment
Class meetings: TuTh 2:10-3:30pm, Carver 132

Min WangGrader: Min Wang
487 Carver
(no phone)
mwang@iastate.edu
Office hours: Wed 3-5pm
The grader's office hours are for questions about homework problems and grading.

About Math 565

Math 565 is a one-semester course on constrained and unconstrained optimization (this means, finding a minimum of a function of one or several variables, possibly with additional constraints). A companion course Math 566 covers discrete optimization (traveling salesman, integer programming, etc.) These two courses can be taken in either order.

After completion of this course, students will be able to solve standard optimization problems using Matlab or other software. They will be aware of the limitations of various algorithms, and able to estimate errors. They will be prepared for more advanced courses or research in other parts of numerical analysis, or in engineering and other applied sciences.

Necessary background includes calculus in one and more dimensions (Math 165/166/265), linear algebra, and some basic familiarity with computer programming.

Catalog Entry:

MATH 565. Continuous Optimization.

(3-0) Cr. 3. S. Prereq: MATH 265 and one of MATH 317, 507, 510
Theory and methods for constrained and unconstrained optimization. Steepest-descent, conjugate gradient, Newton and quasi-Newton, line search and trust-region, first and second order necessary and sufficient conditions, quadratic and general nonlinear programming.

Textbook

cover of Nocedal/Wright book

Textbook:

Jorge Nocedal and Stephen Wright
Numerical Optimization, 2nd edition 2006
ISBN: 978-0-387-40065-5 (e-book)
ISBN: 978-0-387-30303-1 (printed)
errata


 

Homeworks, Exams, Grades

I will assign homework problems and collect them every 3 weeks, for a total of 5 homeworks. Note that the last homework is due during Dead Week.

You will have to use Matlab for some assignments. If the use of Matlab is not specified, I will accept solutions based on any software (hand calculator, Mathematica, Excel spreadsheet, ...)

I will accept late homework until we discuss the solutions in the following class, but you will lose 10% of your score for every day that it is late.

There will be a longer assignment due during Finals Week (twice as long as the other homeworks).

There will not be any in-class exams.

I don't take regular attendance, but I do notice when people stay away for weeks at a time. I rexerve the right to lower a grade because of lack of attendance. This is a classroom course, not distance education. If you want to get an A in this course, you need to attend on a regular basis.

Outline of the semester

We will cover chapters 1-6,9,10,12-17 in the textbook, probably skipping some of the subsections. The following is a tentative outline. I will fill in more details as we go along.

Week and Dates Tuesday Thursday
Week 1 (Jan 12-16)
Chapters 1, 2, Appendices
Overview of Optimization
Convexity
Review of Linear Algebra
Numerical Analysis Basics
Intro to Matlab
Week 2 (Jan 19-23)
Chapter 3
Taylor Polynomials in Higher Dimensions
Behavior of f Near a Local Minimum
Root Finding versus Optimization
One-Dimensional Root Finding Algorithms
Line Search Methods
One-Dimensional Optimization Algorithms
Modifications to Parabolic Interpolation for Use in Line Search
Week 3 (Jan 26-30)
Chapters 3, 4
Wolfe Conditions
Convergence Results for Line Search Methods
Steepest Descent
Overview of Trust Region Methods
HW 1 due
Week 4 (Feb 2-6)
Chapters 4, 5
Trust Region Methods Conjugate Gradient Methods
Week 5 (Feb 9-13)
Chapters 5, 6
Conjugate Gradient Methods Quasi-Newton Methods
Week 6 (Feb 16-20)
Chapters 6, 9
Quasi-Newton Methods
Matlab demo
Derivative-Free Methods
HW 2 due
Week 7 (Feb 23-27)
Chapters 9, 10
Derivative-Free Methods Least Squares Problems
Week 8 (Mar 2-6)
Chapters 10, 12
Least Squares Problems Constrained Optimization
Week 9 (Mar 9-13)
Chapter 12
Constrained Optimization Constrained Optimization
HW 3 due
 
Spring Break
Spring Break
Week 10 (Mar 23-27)
Chapters 12, 13
Constrained Optimization
Matlab demo
Linear Programming
Polytopes
Week 11 (Mar 30-Apr 3)
Chapters 13, 14
Linear Programming:
Simplex Method
Linear Programming:
Interior Methods
Week 12 (Apr 6-10)
Chapter 16
Quadratic Programming Quadratic Programming
HW 4 due
Week 13 (Apr 13-17)
Chapters 17,18
Penalty Methods
Optimization Project
Sequential Quadratic Programming
Week 14 (Apr 20-24)
Chapter 19
Nonlinear Interior Methods Norm Minimization
Cone Programming
Semidefinite Programming
Week 15 (Apr 27-May 1)

Semidefinite Programming

Catch Up/Review
HW 5 due
Finals Week (May 4-8)   Final Assignment due

Course Objectives

  • Computer basics and review of prerequisites
    • computer arithmetic
    • rounding errors
    • condition number
    • basic Matlab
    • review of calculus and linear algebra
  • One-dimensional root finding and optimization
    • bisection
    • fixed point iteration
    • Newton's method for root finding
    • secant method
    • golden section search
    • Newton's method for optimization
    • parabolic interpolation
  • Unconstrained Optimization
    • Line search methods
    • Trust region methods
    • Conjugate gradient method
      • linear
      • nonlinear
    • Quasi-Newton methods
    • Derivative-free methods
      • Nelder-Mead
    • Least squares problems
      • linear
      • nonlinear
  • Constrained Optimization
    • Necessary and Sufficient Conditions
    • Duality
    • Linear Programming
      • Simplex method
      • Interior methods
    • Quadratic Programming
    • Penalty functions

Notes


Official Math Department Policies

The following are the official policies of the Mathematics Department, which all instructors have to follow.

Academic Misconduct

Each Mathematics class follows Iowa State University’s policy on academic dishonesty. Anyone suspected of academic dishonesty will be reported to the Dean of Students Office.

Disability Accommodation

Iowa State University complies with the Americans with Disabilities Act and Sect 504 of the Rehabilitation Act. If you have a disability and anticipate needing accommodations in this course, please contact your primary instructor to set up a meeting within the first two weeks of the semester or as soon as you become aware of your need. Before meeting with your instructor, you will need to obtain a SAAR form with recommendations for accommodations from the Disability Resources Office, located in Room 1076 on the main floor of the Student Services Building. Please call them at 515-294-7220 or email disabilityresources@iastate.edu . Requests for accommodations that are retroactive to an assessment will not be honored.

Make up Examinations

The Mathematics Department has very specific guidelines regarding the opportunity to make up an exam. The Department requires that all Mathematics instructors follow the Faculty Handbook for exam make up policies and procedures that occur during the regular semester weeks and defines “excusable absences” below. Specifically, the policy of the Mathematics Department allows a student to make up an exam occurring mid semester only under one of the five following circumstances. Official documentation is required and must be provided at least 10 days in advance of the request, except when such notice is not possible. In these cases, an instructor must provide an opportunity for a student to make up a missed exam  in a reasonable time frame around the original exam time. The content of a make up exam is discussed below.
  1. Medical excuse - student's own medical emergency.
  2. Medical excuse - a member of the student's family has a medical emergency.
  3. Extra curricular activities as a representative of Iowa State University (e.g., sponsored sports, band, etc.).
  4. Armed forces deployment (military duty).
  5. Officially mandated court appearances, including jury duty.

Please note that conflicts arising due to employment are not normally grounds to request a make up exam.

If an instructor gives three or more hour exams during the semester (including a departmental midterm) and discards the lowest hour exam score for the course grade calculations, then the instructor is not required to give a make-up exam for a missed exam, even in the case of the excusable absences.The Final exam must always be taken and cannot be dropped.

Final Exams. Make up for final examinations have strict policies that all University instructors must follow. Permission to change the time of final exam may be given only by the Dean of the College of Liberal Arts and Sciences. If an instructor elects not to give an exam, the class is required to meet at the scheduled final exam period for other educational activity. If a student has two special group exams that have a time conflict, the student should contact the instructor of the group exam listed first on the final exam schedule and that instructor is responsible for accommodating a make up final exam for the student. Mathematics has special group exams in Math 140, 142, 151, 165, 166, and 265. If a student has three final exams on one day, the instructor of the course that has the smallest number of students in it, which includes the sum from all sections of that course, will be responsible for providing a make up exam for the student. Any other unusual circumstances that involve a request for a student to change the time of their final exam must be approved by the Associate Chair of the Mathematics Department.

High school students taking Iowa State University Mathematics courses will receive the same treatment with regards to excusable absences, with extra curricular activities as a representative of their high school qualifying for regular exemptions.

A complete description of the University’s policies and procedures on exams may be found here.

Should a make up examination be required, an exam that is different from the original exam will be created. The content of the exam will allow the student to be evaluated by the same standards as the other students in the class, will be proctored by a Mathematics instructor, and will be given at a time convenient to both the student and instructor. Make-up exams must be different for each time instance offered.

Dead Week

Each Mathematics class follows the Iowa State University Dead Week guidelines.

Student Behavior in Class.

Students are expected to avoid the use of all electronic devices while class is in session. Exceptions include circumstances where the device is an official part of the class required by the instructor (clickers, presentations, etc.), or for accommodation of a disability for which the official paperwork is in place. Continued disruptions of the class by a student may result in a request by the instructor for the student to leave the class. Private conversations during lecture are not normally appropriate.

Harassment and Discrimination

Iowa State University strives to maintain our campus as a place of work and study for faculty, staff, and students that is free of all forms of prohibited discrimination and harassment based upon race, ethnicity, sex (including sexual assault), pregnancy, color, religion, national origin, physical or mental disability, age, marital status, sexual orientation, gender identity, genetic information, or status as a U.S. veteran. Any student who has concerns about such behavior should contact his/her instructor, Student Assistance at 515-294-1020 or email dso-sas@iastate.edu, or the Office of Equal Opportunity and Compliance at 515-294-7612.

Religious Accommodation

If an academic or work requirement conflicts with a student's religious practices and/or observances, the student may request reasonable accommodations. The request must be in writing at least 10 days in advance if possible, and the course instructor or supervisor will review the request. The student or the instructor may also seek assistance from the Dean of Students Office or the Office of Equal Opportunity and Compliance.

Contact Information

If you are experiencing, or have experienced, a problem with any of the above issues, email academicissues@iastate.edu.

Last Updated: May 11, 2015