Optimization is a core tool of applied mathematics, computational modelling, statistics, operation research, finance, engineering, indeed almost any application of the mathematical sciences. In this module we focus on convex optimization, where both the function and feasible set are convex. Roughly speaking, convex optimization problems lie at the boundary between what we know we can solve efficiently, and what we suspect we can't.
The course will be particularly valuable for anyone wanting to work in applied or industrial areas, and would be suitable for Mathematics, Physics or Statistics students with an appropriate mathematical background. It will assumed that the students have some prior familiarity with mathematical or statistical computing, though this is not absolutely essential.
The paper is based on the text Convex Optimization by Stephen Boyd and Lieven Vandenberghe. You can download a free (and legal) copy of the text here, as well as slides, lecture videos. The text has heaps of exercises to work through (and you can find solutions online in 20 seconds with an internet search).
One of the major advances in optimization in the past few decades has been the discovery of polynomial time algorithms for optimization problems like lineage programming and convex optimization. The new algorithms have had a significant impact on this, and other fields, with implications for both continuous and discrete optimization (and operations research, big data, statistical inference, etc.). A goal of the course is to go from an introduction to optimization right through to an example of such an algorithm, with proof of convergence.
Along the way we will look at applications of convex optimization in areas of geometry, statistical inference, finance and analysis.
It will assumed that the students have some prior familiarity with mathematical or statistical computing, though this is not absolutely essential. We will carry out a few lectures in the computer lab, mainly to see first-hand how algorithms perform in practice. The emphasis, however, will be on the fundamental algorithms, rather than particular implementations.
2018, Semester 1.
MATH202 and MATH203 or equivalent; 300-level MATHs or STAT380.
David Bryant (Room 514, phone 479 7889, email: firstname.lastname@example.org)
Overall, the first half of the paper will focus on convex analysis, covering the mathematical foundation of the methods. The second half will focus on the methods, proofs of their convergence properties, and applications.
- Convex analysis: convex sets, functions and their properties.
- Convex optimization: definitions, transformations of problems, conditions for optimality, examples.
- Duality: The Lagrangian, Lagrangian dual problems, multicriterion problems, KKT conditions
- Unconstrained optimization: Descent methods in general, gradient descent, Newtons method, proofs of convergence for strictly convex and self-concordant functions.
- Equality constrained optimization: elimination of variables, Newton's method, convergence analysis and primal-dual problems, infeasible start methods.
- Interior points methods: barrier method, phase I and II methods, convergence analysis, applications to linear and quadratic programming.
- These will be scattered throughout the paper.
There will be a three-hour exam.
Your final mark F in the paper will be calculated according to this formula:
F = 0.3A + 0.7E
- E is the Exam mark
- A is the Assignments mark
and all quantities are expressed as percentages.
Students must abide by the University’s Academic Integrity Policy
Academic endeavours at the University of Otago are built upon an essential commitment to academic integrity.
The two most common forms of academic misconduct are plagiarism and unauthorised collaboration.
Academic misconduct: Plagiarism
Plagiarism is defined as:
- Copying or paraphrasing another person’s work and presenting it as your own.
- Being party to someone else’s plagiarism by letting them copy your work or helping them to copy the work of someone else without acknowledgement.
- Using your own work in another situation, such as for the assessment of a different paper or program, without indicating the source.
- Plagiarism can be unintentional or intentional. Even if it is unintentional, it is still considered to be plagiarism.
All students have a responsibility to be aware of acceptable academic practice in relation to the use of material prepared by others and are expected to take all steps reasonably necessary to ensure no breach of acceptable academic practice occurs. You should also be aware that plagiarism is easy to detect and the University has policies in place to deal with it.
Academic misconduct: Unauthorised Collaboration
Unauthorised Collaboration occurs when you work with, or share work with, others on an assessment which is designed as a task for individuals and in which individual answers are required. This form does not include assessment tasks where students are required or permitted to present their results as collaborative work. Nor does it preclude collaborative effort in research or study for assignments, tests or examinations; but unless it is explicitly stated otherwise, each student’s answers should be in their own words. If you are not sure if collaboration is allowed, check with your lecturer.