|
|
|||||||||||||||||
Course Catalog 2012-2013
MAT-41126 Optimization Theory 1, 7 cr |
Additional information
Suitable for postgraduate studies
Will not be lectured year 2012-2013
Person responsible
Robert Piche, Risto Silvennoinen
Requirements
Midterm exam and final exam; weekly homework problems
Completion parts must belong to the same implementation
Learning outcomes
The course focuses on the formulation of linear and nonlinear continuous-variable optimization problems, their solution using computer algorithms, and mathematical analysis of the algorithms. Linear programming: After completing this course the student will be able to mathematically formulate linear optimization problems given a verbal problem description. The student will become familiar with typical linear optimization application problems such as transportation and network flow problems. The student will be able to identify if a given linear optimization problem is in standard form and will be able to establish the standard form if necessary. The student will be able to apply the simplex algorithm to solving linear optimization problems. The student will be able to establish the dual form of a linear optimization problem and will be able to interpret the solutions of the primal and dual problem. Nonlinear programming: The student will be able to derive optimality conditions for constrained and unconstrained optimization problems. The student will be able to classify various notions of convergence. The student will be able to implement basic optimization algorithms for constrained and unconstrained problems in Matlab/Octave.
Content
| Content | Core content | Complementary knowledge | Specialist knowledge |
| 1. | Linear programs: standard form, basic solutions, fundamental theorem of linear programming | ||
| 2. | Simplex method: optimality condition theorem, computational procedure, two-phase method | geometrical interpretation of the simplex method; matrix form of the simplex method; | revised simplex method |
| 3. | Duality: formulating the dual problem, geometric interpretation of the dual problem, duality theorem, simplex method for the dual problem; dual simplex method | Interpretation of dual variables: sensitivity and complementary slackness | primal-dual algorithm |
| 4. | Interior-point methods: iterative algorithms and complexity, barrier functions, analytic center, central path | Primal-barrier method | |
| 5. | Applications: transportation problems, transportation algorithm | Network flow problems | |
| 6. | Unconstrained problems: first and second order necessary optimality conditions; sufficient optimality conditions; minimization and maximization of convex functions | zero-order necessary conditions; global convergence of descent algorithms; speed of convergence | |
| 7. | Basic descent methods: Fibonacci and Golden section search; steepest descent method; Newton's method; Conjugate gradient method | ||
| 8. | Constrained problems: first and second order necessary optimality conditions; KKT conditions | ||
| 9. | Feasible direction method; active set method | ||
| 10. | Penalty methods; barrier methods; cutting plane methods |
Evaluation criteria for the course
The course grade will be based on a midterm and final exam, and weekly homework assignments. If the student demonstrates thorough understanding of the core content, s/he may pass the course with the grade 3. In order to achieve grade 4, the student must also demonstrate competency in the points specified in the column 'Complementary knowledge'. The student may achieve grade 5, if s/he demonstrates good command of the points specified in column 'Specialist knowledge'. If there are minor shortcomings regarding the core content, the student may receive the grade 1 or 2, depending on the number of flaws. If there are significant shortcomings regarding the core content, the student will not pass the course.
Assessment scale:
Numerical evaluation scale (1-5) will be used on the course
Partial passing:
Study material
| Type | Name | Author | ISBN | URL | Edition, availability, ... | Examination material | Language |
| Book | Linear and Nonlinear Programming | David G. Luenberger & Yinyu Ye | The full text of this book is freely available on-line at www.spingerlink.com | English |
Additional information about prerequisites
Linear algebra, multivariable calculus, Matlab/Octave
Prerequisite relations (Requires logging in to POP)
Correspondence of content
| Course | Corresponds course | Description |
|
|
|
Documents
Lecture_5.pdf Lecture_6.pdf HW3.pdf Lecture_7.pdf Lecture_8.pdf HW4.pdf Lecture_1.pdf HW1.pdf Lecture_2.pdf Lecture_3.pdf Lecture_4.pdf HW2.pdf