TMA4180
OPTIMERINGSTEORI
(Optimization Theory)
Våren/Spring
2010
Latest News:
May 30: Exam May 21
Results (Official results will come in a few days).
May 26: Exam
Solution (slightly revised).
May 11: A propos convex
optimization - http://online.qmags.com/SIPR0510/Default.aspx#pg1
May 10: List of students
registered for the exam.
Please note
the following:
- The exam is May 21, 0900-1300
(4 hours)
- Aids at the exam limited to
approved calculator and Rottman
- Problems will only be given in
English
- Answer in English or Norwegian
April 26: Last lecture this morning. Do not hesitate to take
contact up towards the exam (Some supplementary notes and presentation added.
They are not part of the curriculum.
April 25: The 2010 curriculum and a set of review
questions are found here (and below):
April
23: Monday 26 April is the last
lecture. The theme for the lecture will be to derive the optimal way to prepare
for the exam, and consider a set of problems related to summer and various
sport activities: Variational
Calculus and Sport. Curriculum and review questions will be ready shortly.
April 18: Old exams
available for training below.
April 12: A small
note about moving the derivative inside the integral sign is found below.
April 6: The theory for rest of the course
will be taken from the book of John L. Troutman. Some copies of the book are
available at Tapir, but the book is otherwise permanently out of print.
Copies of Part I will be
available from IMF’s office at the 7th floor in Sentralbygg II, sold
at net copying costs and charges (low resolution may also be obtained from HEK.
Send e-mail).
The first 42 pages may also
be viewed at Google books.
March 25: GOD PÅSKE! 
March 17: The results of the Midterm Test are found here.
March 11: All slides from today’s lecture are available
below.
March 4: The midterm test is over, and here is the solution Mid Term Test - Solution (may be changed after checking your answers). On Monday we continue with LP and discuss the famous Simplex algorithm.
February 28: I’m very sorry that something has happened to
this web page: I just discovered that the top of the file, from the title to
the end of Latest News log, has simply vanished (Most probably just an
unintended cut, but may also be some incompability between Open Office Sweb,
and MS Word web-editors). However, it does not seem that it contained anything
essential, but please note the following:
The Mid Term Test will be held March 4, 10:15 – 12:00 in Auditorium
S6. Please enter the room so that we may
start on time.
· Aids: No written material is allowed (You will not need a calculator or
a mathematical formula dictionary).
· The test only counts positive in the
final grade.
No exercise this week, but Exercise Hour as usual on
Tuesday afternoon. Please consider the previous MTT you find below.
Also,
inform me if you miss anything important on this page after the crash.
Lectures
Monday
8:15 – 10:00, Aud. R54,
Thursday 10:15 – 12:00. Aud. F2.
Exercise
hour: Tuesday 18:15 – 19:00. Aud. F6
Lecturer:
Harald
E. Krogstad, Room 1146, Sentralbygg II, tel. 73 59 35 36, e-mail: harald.krogstad-at-math.ntnu.no
Assistant:
Ph.D. student Simone Cifani, Room 1104, Sentralbygg II, tel. 73 59 35 46, e-mail: cifani-at-math.ntnu.no
Exercises
Old Midterm and Exam Problems
|
Problems |
Solutions |
Feasible
problems |
|
X2009 Not available |
|
|
|
|
All |
|
|
|
All |
|
|
All |
||
|
|
All |
|
|
All |
||
|
|
1,2 – b), 3, 4 |
|
|
|
All (?) |
|
|
1- c),2,3,4,5 |
||
|
|
|
|
|
All |
||
|
|
|
|
|
1,3,4,5 |
Lecture Notes
NB!
All notes may undergo revisions during the progress of the course
1. Basic Mathematical Tools (2008 revision)
2. Low-dimensional, unconstrained problems (2008 revision)
3. The Trust Region Quadratic Problem
4. Comments about the Conjugate Gradient Method
6. MATLAB Optimization Toolbox (unconstrained)
7.
Karush-Kuhn-Tucker
Theorem Example
for the KKT Theorem
8. Linear Programming Tutorial (minor revisions, March 8)
9. Slides about LP and optimal network flow
10. Quadratic Programming Basics QP Overheads Examples from Matlab Opt. Toolbox
11. Penalty and Barrier Methods (minor revisions, March 21)
12. Note about Inverse Problems Inverse Problems (OHs)
13. Moving the Derivative Inside the Integral Sign
14. Minimum transit time - The Brachistochrone
15. The Frechet Derivative and Classical Mechanics (not part of the curriculum!)
Lecture Survey and Log
Exam
and Curriculum
Date for the Exam: May 21, 4 hours.
Aids: Only approved calculator and Formula Collection (Rotmann).
Test will only be given in English. Answers in English or Norwegian.
Course Description
The objective of the course is to provide an introduction to optimization theory, including common analysis techniques and algorithms. There will be an emphasis on mathematical understanding rather than algorithmic details, but so that numerical software may be used in an intelligent and quality conscious manner. The last part of the course will be an introduction to Variational Calculus or Discrete Optimization (depending on available resources).
The course requires some background in linear algebra and analysis. This is well covered in the course TMA4145 Linear methods, but that course is not a requirement here, since the textbooks and notes also provide the necessary background.
With some justification one can say
that all real world problems may be formulated as optimization problems, and
optimization occurs in a variety of different situations. Optimization of
production, transport and distribution are well-known examples, along with
optimal control. Within statistics, optimization is an essential part of
maximum likelihood and entropy methods and Bayesian techniques. Optimal signal
processing deals with optimal filtering and encoding of signals. A frequently
occurring problem in practice is to fit a complicated model to a limited set of
observations. This leads to so-called inverse problems, where
additional information related to our general knowledge of the solution is
mixed with the data in an optimization formulation. Variational Calculus is
optimization problems with functions instead of vectors as variables. In
physics, a number of principles (e.g. Huygens' principle in optics and
Optimization is a huge field, as is obvious from Wikipedia Optimization Site.
Contents
(Tentative)
1. Non-linear optimization without constraints
· Necessary and Sufficient Conditions for Extrema
· Convexity
· Optimization in Hilbert space
· Algorithms
· Speed of Convergence
· Search Methods for Low-dimensional Problems
·
Steepest Descent, Conjugate
Gradient and
· Quasi-Newton methods
·
2. Nonlinear Optimization with Constraints
· Necessary and Sufficient Conditions for Extrema
· Lagrange multipliers
· Karush-Kuhn-Tucker conditions
· convex problems
3. Brief
overview of linear optimization
· Reduction to Standard Form and Basic Solutions
· The Fundamental Theorem
· Simplex method
· Duality
· Optimizing Network Flow
4. Algorithms
· Direct methods
· Penalty and Barrier methods
5. Inverse problems
· What is an inverse problem
· Examples
· Regularization
· algorithms
· Applications
6. Introduction to Variational Calculus
· Optimizing functionals
· Gâteaux-derivative
· Convex functional
· Euler-Lagrange Equations
· Applications
Textbooks
1. J. Nocedal and S. Wright: Numerical Optimization, 2nd Edition. Springer, 2006. Numerical Optimization, 2nd Ed.
2. J. L. Troutman: Variational Calculus and Optimal Control, 2nd Ed. Springer, 1996. Variational Calculus and Optimal Control, 2nd Ed.
(Legal
copies of relevant pages from Troutman will be sold at net cost)
3. Lecture notes are distributed at no cost throughout the course.