MyOOPS開放式課程
請加入會員以使用更多個人化功能
來自全球頂尖大學的開放式課程,現在由世界各國的數千名義工志工為您翻譯成中文。請免費享用!
課程來源:MIT
     
15.084J / 6.252J Nonlinear Programming

Spring 2004

A bowl-shaped function plotted as a three-dimentional graph.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

Technical Requirements

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




*Some translations represent previous versions of courses.





Syllabus

Amazon logo 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

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


Recommended Alternate Text

Amazon logo 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

Amazon logo 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

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


Recommended Alternate Text

Amazon logo 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:

Amazon logo 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: Amazon logo 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:

Amazon logo 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字留言

留言內容:

驗證碼請輸入6 + 0 =

標籤

現有標籤:1
新增標籤:


有關本課程的討論

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

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

Creative Commons授權條款 本站一切著作係採用 Creative Commons 授權條款授權。
協助推廣單位: