Skip to main content

Linear and Nonlinear Optimization

Overview

Module description

This module is designed to 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 the 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 module 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

Learning objectives

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

  • knowledge and understanding of the mathematical theory underlying the main classes of constrained optimization problems: linear and nonlinear programming problems, network optimization problems and integer programming problems
  • knowledge and understanding of 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
  • the ability to formulate and solve fairly complex optimization problems in the context of practical applications
  • the ability to incorporate the results of a technical analysis into clearly written report form that may be understood by a non-specialist
  • the ability to abstract the essentials of a practical problem and formulate it in a way that facilitates its analysis and solution
  • the ability to use advanced mathematical software for the solution of constrained optimization problems
  • the ability to interpret the results of a constrained optimization problem, explore the solution, carry out a sensitivity analysis and draw conclusions in context.