ECE 602 - Introduction To Optimization
Instructor
Professor
Oleg
Michailovich
Room:
EIT
4127
Telephone
extension:
38247
Office
hours:
To
be
determined.
Email:
olegm@uwaterloo.ca
Lecture schedule
Thursdays, 8:30 - 11:20 AM, RCH 308
Course Outline
Control systems, communication and networking, electronic circuit design, data analysis and modelling, statistics, signal and image processing, and finance are only a few among numerous areas of modern engineering and science, which routinely depend on the methods of numerical optimization. Whether one is prototyping an electronic circuit or developing an investment portfolio, the desired solution can often be associated with an extremum of a specially designed function, known as a cost or objective function. Consequently, the task of finding an optimal solution can often be cast in the form of finding a point, at which such function reaches its minimum (or, alternatively, maximum) value. Naturally, how tractable and realizable the above task is depends on the properties of the cost function at hand as well as its domain and range, both of which can be either continuous or discrete. Accordingly, the fundamental objective of this course is to introduce some principal concepts of optimization theory along with its key numerical techniques. Throughout the course, students will gain valuable background in optimization methods applicable to a wide range of engineering problems along with experience in solving optimization problems of their own choice.
Syllabus
Part I: Continuous optimization
-
Mathematical
preliminaries
(3
hours)
Vectors, norms, distances, open and closed sets, continuous functions, closed functions, derivative and gradient, Hessian, definiteness and matrix inequalities, singular value and eigenvalue decompositions, pseudo-inverse, algorithm complexity, solution of linear equations. -
Convex
sets
and
functions
(3
hours)
Convex sets, cones, hyperplanes and halfspaces, polyhedra, operations preserving convexity, separating and supporting hyperplanes, convex functions, first and second order optimality conditions, sub-level sets and epigraph. -
Convex
optimization
problems
(3
hours)
Basic terminology, standard form of convex optimization problems, local and global optima, optimality criteria, linear optimization problems, quadratic optimization problems, second- order cone programming, semi-definite programming, the Lagrangian, the Lagrange duality, saddle-point theorem, primal vs dual problems. -
Algorithms:
Unconstrained
minimization
(3
hours)
Quadratic minimization and least squares, descent methods, line search, backtracking, gradient descent method, steepest descent method, Newton’s method, non-linear least squares, Gauss-Newton method, implementation, practical considerations, and examples. -
Algorithms:
Equality
constrained
minimization
(3
hours)
Primal and dual feasibility conditions, equality constrained quadratic minimization, Newton’s method with equality constraints, infeasible start Newton method, convex-concave games, implementation, practical considerations, and examples. -
Algorithms:
Inequality
constrained
minimization
(3
hours)
The barrier method, feasibility and phase I methods, phase II methods, primal-dual interior point methods, implementation, practical considerations, and examples. -
Applications
of
convex
optimization
(6
hours)
Approximation and fitting, least-norm problems, regularized approximation, robust approxi- mation, maximum-likelihood estimation, logistic regression, maximum-a-posteriori probabil- ity estimation, optimal detection and hypothesis testing, robust detectors, experiment design, extremal volume ellipsoids, centring, classification, location problems with path constraints.
Part II: Discrete optimization
-
Graphs
and
network
flow
problems
(3
hours)
Graphs and flows, examples of network flow models, an overview of network flow algorithms, algorithm complexity (good, bad, and polynomial algorithms). -
Shortest
path
problems
(3
hours)
Problem formulation and applications, a generic shortest path algorithm, label setting (Dijkstra) methods, label correcting methods, single origin/single destination methods, auction algorithms, dynamic programming. -
The
max-flow
and
the
min-flow
cost
problems
(3
hours)
Cuts in a graph, the max-flow/min-cut theorem, the maximal and minimal saturated cuts, decomposition of infeasible network problems, the Ford-Fulkerson algorithm, transformations and equivalences, duality. -
Network
problems
with
integer
constraints
(3
hours)
Basic formulation, branch-and-bound, Lagrangian relaxation, cutting plane methods, local search methods, genetic algorithm, simulated annealing, rollout algorithms.
Course Textbooks
The students will be provided with copies of lecture slides developed based on:
- S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004 (freely available online.
- D. P. Bertsekas, Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998 (freely available online).
Marking Scheme
- Home Assignments (5 assignments × 5 points): 25%
- Course project (implementation and analysis of a given algorithm): 25%
- Final Exam: 50%