ENGR598F: Convex Optimization
UBC – Okanagan Campus
Summer Short Course 2018
|
Instructor: |
Lectures: |
|
Professor Wei Yu |
August 20-31, 2018, Monday-Friday Monday-Friday: 9am-12noon |
|
Email: weiyu@comm.utoronto.ca |
Tutorials: Monday-Friday: 1pm-2pm TA: Yanjie Dong |
Textbook: Convex Optimization
Authors: Stephen Boyd and Lieven
Vandenberghe, Cambridge University Press, 2004
The great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity - R. Tyrell Rockafellar (SIAM Review '93)
This course provides a comprehensive coverage of the theoretical foundation and numerical algorithms for convex optimization. Topics include:
The topics covered in this course may be of interests to students in all areas of engineering and computer science.
Pre-requisite: Vector calculus. Linear algebra. A fair level of mathematical maturity is expected.
Lecture Schedule:
|
Date |
Topics |
Text Reference |
Assignments |
|
8/20 |
Introduction; Motivating Example: Data Fitting. Basic Concepts: Vector Space, Norm, Vector Calculus, Linear Algebra. Gradient and Hessian of functions. Functions of matrices. |
Chapter 1 Appendix A |
|
|
8/21 |
Convex Sets. Convex functions. First-order and Second-order conditions for differentiable convex functions. |
Chapter 2 |
Due Aug 24 |
|
8/22 |
Properties of Convex Functions. Convex optimization problems. Local and global optimal solutions of convex optimization problems. |
Chapter 3 Chapter 4 |
|
|
8/23 |
Linear Programming. Quadratic programming. Quadratically constrained quadratic programming. Second-order cone programming. Robust linear programming. |
Chapter 4 |
|
|
8/24 |
Least-square problems. Geometric programming. Semi-definite programming. SDP relaxation. |
Chapter 4 |
Due Aug 28 |
|
|
|
||
|
8/27 |
Theory: Lagrangian. Dual optimization problem. Duality gap. Slater’s condition. Sensitivity analysis. Economics and Pricing Interpretation. Saddle points. Game theory. Duality theory for minimax optimization. |
Chapter 5, Rockafellar: |
|
|
8/28 |
Duals of LP. Duals of QP. Dual of $l_p$ optimization. Duality theory for optimization problem with generalized inequality. SDP relaxation. |
Chapter 5, Rockafellar: |
Due Aug 31 |
|
8/29 |
Complementary slackness condition. Karush-Kuhn-Tucker (KKT) Conditions. Interpretation of the KKT condition. Regularity condition for local optimality. Generalized inequalities. |
Bertsekas |
|
|
8/30 |
Algorithms: Descent methods. Newton's method. Equality Constrained Minimization. Infeasible-start Newton's Method. Interior-point method for constrained optimization. |
Chapter 9, Chapter 10 Chapter 11 |
|
|
8/31 |
Interpretation of Interior-point method via KKT condition. Primal-Dual Interior-Point Method. Generalized Inequality. Analytic Centering. Ellipsoid method. Subgradient method for non-differentiable functions. Dual Decomposition. |
Chapter 11 |
Due Sept 4 |
|
|
Final Exam: Sept 5. |
|
|
Grades: Homework (40%), Final Exam (60%).
TA: Yanjie Dong
References:
Last Updated:1/9/2018