15.084J / 6.252J Nonlinear Programming

Spring 2004

A convex function to be optimized. (Graph courtesy of Prof. Robert Freund.)

Course Highlights

Nonlinear Programming features videos of three key lectures in their entirety. A set of comprehensive lecture notes are also available, which explains concepts with the help of equations and sample exercises.

Course Description

This course introduces students to the fundamentals of nonlinear optimization theory and methods. Topics include unconstrained and constrained optimization, linear and quadratic programming, Lagrange and conic duality theory, interior-point algorithms and theory, Lagrangian relaxation, generalized programming, and semi-definite programming. Algorithmic methods used in the class include steepest descent, Newton's method, conditional gradient and subgradient optimization, interior-point methods and penalty and barrier methods.

Special Features

• Sample video lectures

Technical Requirements

Special software is required to use some of the files in this course: .rm.

*Some translations represent previous versions of courses.

Syllabus

When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

Description

This course introduces students to the fundamentals of nonlinear optimization theory and methods. Topics include unconstrained and constrained optimization, linear and quadratic programming, Lagrange and conic duality theory, interior-point algorithms and theory, Lagrangean relaxation, generalized programming, and semi-definite programming. Algorithmic methods used in the class include steepest descent, Newton's method, conditional gradient and subgradient optimization, interior-point methods and penalty and barrier methods.


Required Text

Bertsekas, Dimitri P. Nonlinear Programming. 2nd ed. Athena Scientific Press, 1999. ISBN: 1886529000.


Recommended Alternate Text

Bazaraa, Mokhtar S., Hanif D. Sherali, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. New York: John Wiley & Sons, 1993. ISBN: 0471557935.


Course Requirements

1. Weekly Problem Sets (about 12).
   
   
2. Midterm Examination (in-class, closed book).
   
   
3. Final Examination (3-hour exam).
   
   
4. Computer Exercises.
   
   

Grading

Grading will be based on the following:

ACTIVITY PERCENTAGE Midterm Exam 25% Final Exam 50% Problem Sets 25%

Calendar

LEC # TOPICS 1 Unconstrained Optimization Optimality Conditions 2 Convex Unconstrained Optimization Optimality Conditions 3 Newton's Method 4 Quadratic Forms 5 Steepest Descent Method 6 Constrained Optimization Optimality Conditions I 7 Constrained Optimization Optimality Conditions II 8 Constrained Optimization Optimality Conditions III 9 Projection Methods for Equality Constrained Problems 10 Projection Methods/Penalty Methods 11 Penalty Methods 12 Barrier Methods, Conditional Gradient Method 13 Midterm Exam 14 Interior-Point Methods for Linear Optimization I 15 Interior-Point Methods for Linear Optimization II 16 Analysis of Convex Sets 17 Analysis of Convex Functions 18 Duality Theory I 19 Duality Theory II 20 Duality Theory III 21 Duality Theory IV 22 Generalized Programming and Subgradient Optimization  23 Semidefinite Optimization I 24 Semidefinite Optimization II 25 Semidefinite Optimization III 26 Extensions and Wrap-up

Readings

When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

Required Text

Bertsekas, Dimitri P. Nonlinear Programming. 2nd ed. Athena Scientific Press, 1999. ISBN: 1886529000.


Recommended Alternate Text

Bazaraa, Mokhtar S., Hanif D. Sherali, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. New York: John Wiley & Sons, 1993. ISBN: 0471557935.


Background Reading in Linear Programming and Real Analysis

Linear Programming

For those students who have not had any exposure to linear programming, it is recommended that you read the following sections from one of the following two texts:

Luenberger, David G. Linear and Nonlinear Programming. 2nd ed. Reading, MA: Addison Wesley, 1984. ISBN: 0201157942.

• Chapter 2: Sections 2.1-2.5
  
  
• Chapter 3: Sections 3.1-3.5, 3.7
  
  
• Chapter 4: Sections 4.1-4.4
  
  

Or: Bertsimas, Dimitris, and John Tsitsiklis. Introduction to Linear Optimization. Athena Scientific Press, 1997. ISBN: 1886529191.

• Chapter 1: Sections 1.1, 1.2, 1.4
  
  
• Chapter 2: Sections 2.1, 2.2
  
  
• Chapter 3: Sections 3.1, 3.2, 3.5
  
  
• Chapter 4: Sections 4.1, 4.2, 4.3
  
  

Analysis

For those students who have not had any exposure to real analysis, you should read the following sections of the text:

Rudin, Walter. Principles of Mathematical Analysis. 3rd ed. McGraw-Hill, 1976. ISBN: 007054235X.

• Chapter 2: pp. 24-43 (the whole chapter)
  
  
• Chapter 3: pp. 47-61
  
  
• Chapter 4: pp. 83-95
  
  

Lecture Notes

LEC # TOPICS 1 Unconstrained Optimization Optimality Conditions (PDF) 2 Convex Unconstrained Optimization Optimality Conditions 3 Newton's Method (PDF) 4 Quadratic Forms (PDF) 5 Steepest Descent Method (PDF - 2.2 MB) 6 Constrained Optimization Optimality Conditions I (PDF) 7 Constrained Optimization Optimality Conditions II 8 Constrained Optimization Optimality Conditions III 9 Projection Methods for Equality Constrained Problems (PDF) 10 Projection Methods/Penalty Methods (PDF) 11 Penalty Methods 12 Barrier Methods, Conditional Gradient Method (PDF) 13 Midterm Exam 14 Interior-Point Methods for Linear Optimization I (PDF) 15 Interior-Point Methods for Linear Optimization II 16 Analysis of Convex Sets (PDF) 17 Analysis of Convex Functions 18 Duality Theory I (PDF) 19 Duality Theory II 20 Duality Theory III 21 Duality Theory IV (PDF) 22 Generalized Programming and Subgradient Optimization (PDF) 23 Semidefinite Optimization I (PDF) 24 Semidefinite Optimization II 25 Semidefinite Optimization III 26 Extensions and Wrap-up

 

Recitations

Note that there were no recitations during the weeks of the midterm exam (week 7), spring break (week 8), or Sloan Innovation Period (week 9).

WEEK # TOPICS RECITATIONS 1 The Basic Problem Basic Definitions Weirstrass Theorems Necessary and Sufficient Conditions for Optimality (PDF) 2 Newton's Method When Newton's Method Fails Rates of Convergence Quadratic Forms Eigenvectors/Eigenvalues/Decompositions (PDF) 3 Method of Steepest Descent Why this Method is Good Why this Method is Bad Line Search Algorithm (PDF) 4 Separating Hyperplanes Theorem of The Alternative (Farkas Lemma) Necessary Conditions for Optimum of Constrained Problem Finding Optima (PDF) 5 When is KKT Necessary Sufficient Conditions Steepest Descent for Constrained Problems (PDF) 6 Penalty/Barrier Methods Quiz Review (PDF) 10 Importance of Duality Lagrangian Dual Approach Features of The Dual Column-Geometry Dual Approach Weak Duality Strong Duality (PDF)

Exams

This course includes a closed-book midterm exam, held during lecture 13 for 90 minutes, and a three-hour final exam, given after the course has finished. A sample midterm, used in the 1998 version of this course, is available.

Midterm Exam (PDF)

Video Lectures

RealOne™ Player software is required to run the .rm files in this section.

The three video lectures available below illustrate the content and teaching style of this course.

LEC # TOPICS    VIDEOS    3 Newton's Method (RM - 56k)   (RM - 80k) (RM - 220k) 18 Duality Theory I (RM - 56k)   (RM - 80k) (RM - 220k) 23 Semidefinite Optimization I (RM - 56k)   (RM - 80k) (RM - 220k)

---

留下您對本課程的評論 標題： 您目前為非會員，留言名稱將顯示「匿名非會員」 只能進行20字留言 留言內容：

標籤 現有標籤： 新增標籤：

---

有關本課程的討論

課程討論
先說聲抱歉,如果打擾到您們。 誠摯告訴您一個機會：　 你想致富嗎? 相信我 ! 這是一個已被眾多名人保證最有效, 低 門 檻 的 創 業 -> http://azyyeayzz.weebly.com/

workonet, 2010-10-13 14:54:09