AM 221 : Advanced Optimization

Week 1

Mon 01/25 Introduction: Basic terminology, examples: linear regression, LASSO, sparse regression [pdf]
Wed 01/27 Elements of convex geometry: Convex sets, convex functions, separating hyperplanes, linear classification, perceptron, neural networks [pdf]
Wed 01/27 Section 1 [pdf]

Week 2

Mon 02/01 Linear programming: Definition, canonical and standard form, modelization examples [pdf]
Wed 02/03 Duality theory: Farkas lemma, weak duality, strong duality [pdf]
Wed 02/03 Section 2 [pdf]

Week 3

Mon 02/08 Applications of duality: Game theory, Nash equilibrium, minimax theorem [pdf]
Wed 02/10 Applications of duality: Learning theory, boosting [pdf]
Wed 02/10 Section 3 [pdf]

Week 4

Mon 02/15 Presidents' day: no class
Wed 02/19 Simplex method: Extreme points, basic feasible solutions, simplex method [pdf]
Wed 02/19 Section 4 [pdf]

Week 5

Mon 02/22 Convexity and multivariate analysis: Taylor expansions, properties of convex functions, necessary and sufficient conditions for optimality [pdf]
Wed 02/24 Gradient descent algorithm: Strong convexity, analysis of convergence [pdf]
Wed 02/24 Section 5 [pdf]

Week 6

Mon 02/29 Steepest descent and Newton's method: steepest descent, coordinate descent, Newton's method [pdf]
Wed 03/02 Online convex optimization: prediction from experts, weighted majority (aka multiplicative weights) algorithm, online convex optimization, online learning, online gradient descent [pdf]
Wed 03/02 Section 6 [pdf]

Week 7

Mon 03/07 Duality: Lagrangian duality, Slater's condition [pdf]
Wed 03/09 Application of Lagrangian duality: Support Vector Machines [pdf]
Wed 03/09 Section 7 [pdf]

Week 8

Mon 03/14 Spring break: no class
Wed 03/16 Spring break: no class
Wed 03/16 Spring break: no section

Week 9

Mon 03/21 Strong duality: Duality gap, complimentary slackness, KKT conditions [pdf]
Wed 03/23 Optimization with erroneous oracles: Absolute and relative erroneous oracles, approximation algorithms, value oracles, probabilistic constructions, Chernoff bounds [pdf]
Wed 03/23 Section 8 [pdf]

Week 10

Mon 03/28 Discrete optimization: Maximum matching, minimum spanning trees, greedy algorithms
Wed 03/30 Knapsack: Approximation algorithms, the greedy algorithm, LP relaxation, dynamic programming, FPTAS [pdf]
Wed 03/30 Section 9 [pdf]

Week 11

Mon 04/04 Submodularity: Maximum-cover, the greedy algorithm, properties of submodular functions, maximizing influence in social networks [pdf]
Wed 04/06 Submodularity under matroid constraints: Matroids, the greedy algorithm, combinatorial auctions
Wed 04/06 Section 10 [pdf]

Week 12

Mon 04/11 Non-monotone submodularity: Examples of submodular maximization, Max-Cut problem, local search algorithm, randomized algorithm for non-monotone maximization [pdf]
Wed 04/13 Rounding techniques: Minimum-Set Cover, greedy algorithm, randomized rounding, simple rounding [pdf]
Wed 04/13 Section 11

Week 13

Mon 04/18 Pipage rounding: randomized and concave relaxations of Max-Cover, pipage rounding [pdf]
Wed 04/20 Relaxations of submodular functions: Multilinear relaxations, concave and convex closures, submodular minimization, matroid polytopes
Wed 04/20 Section 12

Week 14

Mon 04/25 The continuos greedy algorithm [pdf]
Wed 04/27 Poster session