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.
The following refers to the notes. Please make sure to have read the material thoroughly (including proofs!) before the lecture.
1. March 6 1.1-1.5
2. March 13 2.1-2.2
3. March 20 2.3-2.4
4. March 27 3.1-3.5
No lecture, April 10
5. April 17 4.1-4.2
6. April 26 5.1-5.2
7. May 1 5.3
8. May 8 6.1-6.2.1
9. May 15 6.2.2
10. May 22 6.3-7.4
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 integrity means being honest in your studying and assessments. It is the basis for ethical decision-making and behaviour in an academic context. Academic integrity is informed by the values of honesty, trust, responsibility, fairness, respect and courage.
Academic misconduct is seeking to gain for yourself, or assisting another person to gain, an academic advantage by deception or other unfair means. The most common form of academic misconduct is plagiarism.
Academic misconduct in relation to work submitted for assessment (including all course work, tests and examinations) is taken very seriously at the University of Otago.
All students have a responsibility to understand the requirements that apply to particular assessments and also to be aware of acceptable academic practice regarding the use of material prepared by others. Therefore it is important to be familiar with the rules surrounding academic misconduct at the University of Otago; they may be different from the rules in your previous place of study.
Any student involved in academic misconduct, whether intentional or arising through failure to take reasonable care, will be subject to the University’s Student Academic Misconduct Procedures which contain a range of penalties.
If you are ever in doubt concerning what may be acceptable academic practice in relation to assessment, you should clarify the situation with your lecturer before submitting the work or taking the test or examination involved.
Types of academic misconduct are as follows:
The University makes a distinction between unintentional plagiarism (Level One) and intentional plagiarism (Level Two).
- Although not intended, unintentional plagiarism is covered by the Student Academic Misconduct Procedures. It is usually due to lack of care, naivety, and/or to a lack to understanding of acceptable academic behaviour. This kind of plagiarism can be easily avoided.
- Intentional plagiarism is gaining academic advantage by copying or paraphrasing someone elses work and presenting it as your own, or helping someone else copy your work and present it as their own. It also includes self-plagiarism which is when you use your own work in a different paper or programme without indicating the source. Intentional plagiarism is treated very seriously by the University.
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 students answers should be in their own words. If you are not sure if collaboration is allowed, check with your lecturer..
Impersonation is getting someone else to participate in any assessment on your behalf, including having someone else sit any test or examination on your behalf.
Falsiﬁcation is to falsify the results of your research; presenting as true or accurate material that you know to be false or inaccurate.
Use of Unauthorised Materials
Unless expressly permitted, notes, books, calculators, computers or any other material and equipment are not permitted into a test or examination. Make sure you read the examination rules carefully. If you are still not sure what you are allowed to take in, check with your lecturer.
Assisting Others to Commit Academic Misconduct
This includes impersonating another student in a test or examination; writing an assignment for another student; giving answers to another student in a test or examination by any direct or indirect means; and allowing another student to copy answers in a test, examination or any other assessment.