CS416-15 Optimisation Methods

Academic year
24/25
Department
Computer Science
Level
Undergraduate Level 4
Module leader
Fanghui Liu
Credit value
15
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry

Download as PDF

Introductory description

At their core, many real-world problems involve optimisation problems that are complex and challenging, and they require principled mathematical and algorithmic solutions. Companies such as Google and Facebook use powerful algorithmic primitives such as gradient descent to solve a host of challenging problems. These primitives in turn are based on a beautiful mathematical theory developed in the context of convex and discrete optimisation.

Module aims

The aim is to learn the mathematical and algorithmic foundations underpinning optimization problems that are ubiquitous in applications in machine learning, data analysis, and scientific computing.

There are several interrelated aims of this module:
(1) to expose students to optimisation methods that have found significant applications,
(2) to develop a toolkit of mathematical methods that can be used to tackle real-world problems, and
(3) to rigorously analyse these methods.

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

Some of the following topics will be discussed. The selection of topics may vary from year to year.

Convex optimisation methods and their applications. Gradient descent, the multiplicative weights update method, the Frank-Wolfe gradient descent algorithm.
Discrete and combinatorial optimisation methods and their applications. Submodular functions, submodular minimisation via the ellipsoid method and gradient descent. Submodular maximisation via the Greedy algorithm.
Algorithms for linear algebra and their applications. The power method, singular value decompositions, principal component analysis, spectral clustering, least squares and linear regression.

Learning outcomes

By the end of the module, students should be able to:

Indicative reading list

Please see Talis Aspire link for most up to date list.

View reading list on Talis Aspire

Subject specific skills

  1. Learn basic optimisation methods which are ubiquitous in applications in machine learning, data analysis and scientific computing.
  2. Strengthen the mathematical background in analysis and algebra.
  3. Learn how to analyse optimisation methods with mathematical rigor.
  4. Get programming experience by developing these methods in software and see different scenarios of application

Transferable skills

  1. Develop analytical thinking by working with mathematical concepts.
  2. Develop research & problem solving skills, particularly for mathematical problems. Students are exposed to some paradigms of optimisation, and later they develop their own approach to solve problems.
  3. Communication skills - Learn how to express themselves with mathematical precision.

Study time

Type Required
Lectures 20 sessions of 1 hour (13%)
Seminars 10 sessions of 1 hour (7%)
Practical classes 10 sessions of 1 hour (7%)
Private study 110 hours (73%)
Total 150 hours

Private study description

Private study and revision.

Costs

No further costs have been identified for this module.

You do not need to pass all assessment components to pass the module.

Students can register for this module without taking any assessment.

Assessment group D4
Weighting Study time Eligible for self-certification
Practical Assignment 1 15% Yes (extension)

Lab Exercise
Practical assignment 2 15% Yes (extension)

Lab Exercise
In-person Examination 70% No

CS416 exam

  • Answerbook Pink (12 page)
  • Students may use a calculator
Assessment group R2
Weighting Study time Eligible for self-certification
In-person Examination 100% No

CS416 resit examinations

  • Answerbook Pink (12 page)
  • Students may use a calculator
Feedback on assessment

Past exam papers for CS416

Pre-requisites

We shall assume the standard general background that 3rd year Computer Science and Discrete Mathematics students have.

Courses

This module is Optional for:

  • Year 5 of UCSA-G504 MEng Computer Science (with intercalated year)
  • Year 4 of UCSA-G503 Undergraduate Computer Science MEng

This module is Option list B for:

  • Year 4 of UCSA-G4G3 Undergraduate Discrete Mathematics
  • Year 5 of UCSA-G4G4 Undergraduate Discrete Mathematics (with Intercalated Year)