Linear and Nonlinear Optimization

• Credit value: 15 credits at Level 7
• Convenor: Dr Richard Pymar
• Assessment: to be confirmed

In this module we introduce you to ideas of mathematical modelling and optimization in the context of problems in industry, business and science. The methods covered are all deterministic.

The aim is to develop your ability to formulate fairly complex optimization problems in the context of practical problems, and to provide an understanding of the main classes of problems that are practically solvable and a detailed coverage of some of the most important solution methods. The coverage of constrained optimization is not comprehensive but aims to give you a firm foundation in the theory, on which you can build more detailed knowledge in areas of particular interest in your work. Examples are used throughout to illustrate the theory and the range of its practical application.

Indicative syllabus

• Outline of the history and scope of operational research
• Problem formulation
• Nonlinear optimization: convexity and concavity, constrained and unconstrained optimization, conditions for optimality, introduction to optimization algorithms
• Algorithms for one-dimensional optimization
• Newton and quasi-Newton methods
• Lagrangian methods and the Kuhn-Tucker conditions
• The Generalised Reduced Gradient Method
• Steepest descent (and its limitations)
• Quadratic programming problems and their solution
• Introduction to penalty functions
• Application of techniques to some practical problems
• Network optimization: introduction to optimization problems on networks, in particular maximum flow problems, and their relationship with linear programming, shortest path and minimal connector problems
• Integer programming: introduction to the wide variety of contexts in which practical problems can be formulated as integer or mixed integer programming problems
• The branch-and-bound approach

By the end of this module, you should be able to:

• understand the mathematical theory underlying the main classes of constrained optimization problems: linear and nonlinear programming problems, network optimization problems and integer programming problems
• understand the most important algorithms and solution methods for constrained optimization problems, including the simplex algorithm, steepest descent and conjugate gradient methods, network algorithms, cutting plane and branch-and-bound
• formulate and solve fairly complex optimization problems in the context of practical applications
• incorporate the results of a technical analysis into clearly written report form that may be understood by a non-specialist
• abstract the essentials of a practical problem and formulate it in a way that facilitates its analysis and solution
• use advanced mathematical software for the solution of constrained optimization problems
• interpret the results of a constrained optimization problem, explore the solution, carry out a sensitivity analysis and draw conclusions in context.