|Module Title ||Nonlinear Programming I and Heuristic Optimisation|
|Department || Mathematics|
|Module Code || 06 19590 |
|Module Lead ||Sandor Nemeth|
|Level || Honours Level |
|Credits || 20 |
|Semester|| Full Term|
LI Linear Algebra & Linear Programming - (06 25765)
Integer Programming and Combinatorial Optimisation - (06 21624)
|Restrictions || Compulsory for MSci Mathematics with Business Management; Optional for BSc Mathematics with Business Management, All MSci programmes including Mathematics, BSc Mathematical Sciences, BSc Mathematical Sciences with Study in Continental Europe, All programmes including a Major in Mathematics |
Total: 56 hours
|Exclusions || |
|Description || Many decision problems arising in managerial decision making in the public as well as in the private sector are inherently nonlinear, and the same holds for various problems occurring in science and engineering. Tackling highly realistic nonlinear problems leads to solution methods totally different from those of linear programming. In the first part of this module essential theory of unconstrained and constrained nonlinear optimization, including optimality conditions, will be presented. Based on this, some essential solution techniques, such as gradient methods, Newton’s method, penalty, barrier and SQP methods will be introduced.
Many problems from management mathematics (discrete or continuous) are NP-hard. In other words, optimisation problems that arise in industry or in public sector could not be solved exactly in reasonable computing time, even with modern computers. Therefore, when traditional mathematics techniques fail to give fast answers, one should rely on near-optimal solution methods or heuristics. Ideas of classical heuristics (several from: greedy, constructive, A* search, relaxation, local search, divide and conquer, dynamic programming, Lagrangean etc) will be studied first. A modern heuristic (metaheuristics) or general frameworks for building heuristics, usually gives rules of escaping from the so-called "local optima trap". Some modern heuristics, such as Genetic algorithms, Tabu search, Simulated Annealing, Variable neighbourhood search, Neural Networks, Ant Colony etc. will be presented.
|Learning Outcomes || By the end of the module the student should be able to:
- Understand and explain the basic concepts of nonlinear programming, the role of convexity in optimisation, the importance of optimality conditions.
- Understand and explain the basic algorithms of nonlinear programming, both unconstrained and constrained. Understand and explain why and when heuristic optimisation techniques are useful in management mathematics.
- Understand and explain the basic concepts of classical and modern heuristic optimisation techniques; design data structure for the computer code and apply rules of heuristics for that problem.
19590-01 : Raw Module Mark : Coursework (0%)
19590-05 : Final Module Mark : Coursework (100%)
|Assessment Methods & Exceptions || Assessments: 90% on one three hour examination; 10% from coursework and/or class tests. |
|Other || |
Luenberger. Introduction to Linear and Nonlinear Programming. Addison Wesley.
Burke, E & Kendall, G (eds). 2005. Introductory Tutorials in Optimisation, Search and Decision Support Methodology. Kluwer.
Nonlinear Programming Frequently Asked Questions: http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html