Mathematics 164 Lecture 1 - Fall 2005

Optimization

• Time and place: MWF 11:00am in MS 6627.
• Instructor: Xinwei Yu (xinweiyu@math.ucla.edu).
• Office hours: MWF 9:30am – 10:30am at MS 7360.
• Teaching Assistant: Kree Cole-Mclaughlin (kree@math.ucla.edu). Office hours: T 10:00am – 12:00am in MS 2943.
• Discussion section: R 11:00am in MS 6627.
• Textbook: S. Nash and A. Sofer, Linear and Nonlinear Programming. Please check the errata here.
• Syllabus: We will follow the general course outline. Here is the first handout of the class.
• Grading Policy: 20% homework, 30% midterm, 50% final.
  • The worst homework grade will be dropped.
  • In case of missing midterm, 80% will be assigned to the final.
• Exams:
  • Midterm: Friday November 4, 2005, 11:00am – 12:00am. Location: Hershey 1651.
  • Final: Wednesday December 14, 2005, 8:00am – 11:00am.
  • Make ups for the midterm and final are permitted only under exceptional circumstances, as outlined in the UCLA student handbook.
• Prerequisites: Will be gone over in the first discussion section (09/29). Here is a list of prerequisites and some problems for self-test. 
• Lectures and Homeworks:
  • I will try to put drafts of one week’s lecture notes online before every Monday. They will receive constant minor revisions (for typos etc) throughout the course. The last revision date will be shown here so you can judge whether you would like to download a new version. These lecture notes will be in pdf format. You can download free reader at http://www.adobe.com/.
  • Homework will be assigned every Friday in class, collected every Thursday at the beginning of the discussion section, and returned the next Thursday.
    • Please do not copy, but discussion is encouraged.
    • Please write solutions in detail and clearly.
    • Late homework will not be accepted.
  • Programming problems may be assigned now and then.
    • Please email your program code as well as instruction on how to run your code to reproduce your result to the TA before handing in your homework.
    • You may want to set up accounts in PIC labs: Boelter Hall 2817 and Mathematical Sciences 3970  http://www.pic.ucla.edu/piclab/ .
    • How to use Matlab: Getting started with MATLAB , MATLAB Documentation (thanks to Prof. C. Anderson, UCLA) .

 

• Supplemental Notes: Some notes about various things that we don't have time to explain in the class. Hopefully some of them will help understanding the materials in the lecture notes. (Disclaimer: These notes are very crude and not as well-checked as the lecture notes. The results in these notes should not be used when doing homeworks or exams. )
  
  • Miscellaneous about the Simplex method (partially finished). Understanding pivoting; cycling and anti-cycling; the tableau; the simplex method is not polynomial; introduction to the ellipsoid method.
  • Introduction to the interior point method. (A very nice and readable introduction is lecture 16 of David P. Williamson's CS 361B lecture notes. Available on the author's webpage which can be found by google)
    
• Further Readings: These are review papers and lecture notes somehow related to our class. Read them if you are interested and have some spare time to kill. 
  • Tamara G. Kolda, Robert Michael Lewis, Virginia Torczon. Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods. SIAM Review, 45(3): 385-482. 2003.

In our class, all object functions are differentiable, and we use the derivative information extensively. What if the object function is not differentiable? What if it is just a “black box” and has no explicit formulation for us to use?

• Anders Forsgren, Philip E. Gill, Margaret H. Wright. Interior Methods for Nonlinear Optimization. SIAM Review, 44(4): 525-597. 2002.

     This is the methods that connects linear and nonlinear programming.

• Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press. (The link contains a pdf version freely available online).

Focus on methods and techniques taking advantage of the convexity of the objective function. Having many practical examples. Reading the book page by page is time devouring though, especially due to the large amount of exercises, some of which are pretty tough technically. However it is an eye-opening book, covers a broad range of topics.

• R. Tyrrell Rockafellar. Convex Analysis. Princeton Landmarks in Mathematics. Princeton University Press, 1997.

Contains more than most people need to know. However very hard to read (except the first few sections) because of a myriad of definitions.