everything.study
ECE 602

Introduction to Optimization

Graduate

Winter 2023

Topics

  • Part I: Continuous optimization

Readings

  • S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004 (freely available online at http://stanford.edu/~boyd/cvxbook/)
    unspecified
  • D. P. Bertsekas, Network Optimization: Continuous and Discrete Models , Athena Scientific, 1998 (freely available online at http://web.mit.edu/dimitrib/www/net.html)
    unspecified
  • The students will be provided with copies of lecture slides developed based on:
    unspecified
Spring 2023

Topics

  • Part I: Continuous optimization

Readings

  • S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004 (freely available online at http://stanford.edu/~boyd/cvxbook/)
    unspecified
  • D. P. Bertsekas, Network Optimization: Continuous and Discrete Models , Athena Scientific, 1998 (freely available online at http://web.mit.edu/dimitrib/www/net.html)
    unspecified
  • The students will be provided with copies of lecture slides developed based on:
    unspecified
Winter 2017

Topics

  • 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.
  • 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
  • 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.

Readings

  • S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004 (freely available online.
    unspecified
  • D. P. Bertsekas, Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998 (freely available online).
    unspecified
  • The students will be provided with copies of lecture slides developed based on:
    unspecified
Sources