Linear & Quadratic Programming [9 Lectures]

- Intro: setting up AI/ML problems as optimization [1]
- ex: maximum likelihood
- ex: most likely explanation in an HMM or MRF
- ex: misclassification error + structural risk for classification
- ex: propositional planning

- linear programs and QPs [2]
- 2d LP Applet
- ex: value of a shortest path MDP
- ex: QP: SVM
- ex: QP: LASSO
- ex: minimax equilibria in matrix games; regret

- duality of LPs and QPs [2]
- Lagrange multipliers
- ex: value/policy of a shortest path MDP
- ex: QP: SVM
- ex: mincut, maxflow

- semi-infinite (or just big) programs [1]
- constraint generation, column generation, separation oracles
- ex: constraining largest singular value <= 1 by adding linear constraints
- ex: finding support vectors in SVMs

- combining dynamic programming and LPs [1]
- ex: Viterbi, max-product for maximum margin Markov networks

- ellipsoid algorithm [1]
- Blackwell's theorem

- gradient and subgradient descent [1]
- ex: structured margin/ maximum margin Markov nets

Mon., Jan. 11:

- Lecture: Setting up AI/ML problems as optimization (Carlos)

[Slides] [Annotated]

Wed., Jan. 13:

- Lecture: Linear programs - problem statement and geometry of
LPs (Geoff)

[Slides] [Annotated] - Relevant readings: B&V p1-7 (optimization and LPs), p21-42 (convexity)

Wed., Jan. 20:

- Lecture: Linear program geometry, the simplex algorithm (Geoff)

[Slides] [Annotated] - Relevant readings: Bertsimas and Tsitsiklis - Chapter 2 and 3

Mon., Jan. 25:

- Lecture: Geometry of LP solutions, convex sets (Carlos)

[Slides] [Annotated] - Relevant readings: BV 2.1 - 2.3

Wed., Jan. 27:

- Lecture: Convex sets (cont'd, Carlos), Convex Functions (Geoff)

[Convex Sets Annotated] [Convex Fns Slides] [Convex Fns Annotated] - Relevant readings: BV 3.1 - 3.5

Mon., Feb. 1:

- Lecture: Quadratic programs (Geoff)

[Slides] [Annotated] - Relevant readings: Readings - BV 4.4 and BV 8.6 (SVMs)

Wed., Feb. 3:

- Lecture: Quadratic programs, duality (Geoff)

[QP Slides] [Duality Slides] [QP Annotated] [Duality Annotated] - Relevant readings: Vazirani Chapter 12, Bertsimas and Tsitsiklis Chapter 4, and BV - 5.2

Mon., Feb. 8:

- Lecture canceled due to snow!

Wed., Feb. 10:

- Lecture canceled due to snow!

Thu., Feb. 11 (special make-up lecture: 5PM in Hammerschlag B103):

- Lecture: SVMs and Duality (Geoff)

[SVM and Duality Slides] [SVM and Duality Annotated] - Relevant readings: BV 5.1-5.4

Mon., Feb. 15:

- Lecture: Duality continued (Geoff)

[Slides] [Annotated slides] - Relevant readings: BV 5.7

Wed., Feb. 17:

- Lecture: Duality continued (Geoff); and

Semi-infinite (or just big) programs: Constraint Generation (Carlos)

[Duality Slides] [Constraint Generation Slides]

[Annotated Duality Slides] [Annotated Slides on Max Flow]

Mon., Feb. 22:

- Lecture: Semi-infinite (or just big) programs: Constraint
Generation (Carlos)

We will be continuing on the slides from Feb 17. [Constraint Generation Annotated Slides]

Wed., Feb. 24:

- Lecture:
Constraint Generation for Maximum Margin Markov Networks (Carlos)

[M3Ns Slides] [M3Ns Annotated Slides] - Original M3Ns paper

Mon., Mar. 1:

- Lecture: Subgradient algorithms (Geoff)

[Subgradient slides] [Annotated slides] - Relevant readings: BV 9.3, Rockafellar (Convex analysis textbook) Chapter 23 for subgradient calculus

Wed., Mar. 3:

- Lecture: Subgradient algorithms (Geoff)

[Slides] [Annotated] - Relevant readings: For convergence analysis and other topics
- Pegasos paper
- SVM inverse dependence on training set size paper

Mon., Mar. 15:

- Lecture: Subgradient; ellipsoid (Geoff)

[Subgradient slides] [Ellipsoid slides] [Subgradient Annotated] [Ellipsoid Annotated] - Relevant readings: BV 8.4, and Appendix B for the minimum volume ellipsoid problem
- Bertsimas and Tsitsiklis - Chapter 8 for the ellipsoid algorithm

[Top]

Convex Optimization [10 Lectures]

- convex sets, functions and programs [4]
- ex: piecewise linear object functions
- ex: approximating convex functions by piecewise linear functions
- ex: Logistic regression
- ex: SDP: largest/smallest eigenvalue
- ex: SDP: semidefinite embedding
- ex: equilibria and regret in convex games
- ex: experimental design
- ex: transformation-invariant SVMs

- duality of functions and sets [1]
- norms, support functions

- convex programs and duality of CPs [2]
- ex: maxent vs MLE in Gibbs
- ex: SOCP: LP with uncertain constraints, bounded probability of failure
- ex: SDP: largest/smallest eigenvalue
- ex: SDP: finding the fastest-mixing policy in an MDP
- ex: SDP: semidefinite embedding

- Newton's method [1]
- ex: finding analytic center of polyhedron

- interior-point methods for solving CPs [1]
- barriers, self-concordance
- central path
- poly-time algorithms for CPs

- online optimization [1]
- online convex programs
- online regret
- no-regret algorithms
- ex: adaptive data structures
- ex: margin perceptron

Wed., Mar. 17:

- Lecture: Convex functions [Slides] [Annotated] [Ellipsoid Annotated]
- Relevant readings: BV 3.1

Mon., Mar. 22:

- Lecture: Convex programs [Slides] [Annotated]

Wed., Mar. 24:

- Lecture: Convex programs [Slides] [Annotated]

Mon., Mar. 29:

- Lecture: Convex duality [Slides] [Annotated]

Wed., Mar. 31:

- Lecture: Convex program duality [Slides] [Annotated]

Mon., Apr. 5:

- Lecture: Second-order (Newton's) solver for convex problems [Slides] [Annotated]

Wed., Apr. 7:

- Lecture: Second-order (Newton's) solver for convex problems (cont.)
- Analysis, equality constraints, general constrained optimization [Slides] [Annotated]

Mon., Apr. 12:

- Lecture: Second-order (Newton's) solver for constrained convex problems [Slides] [Annotated]

[Top]

Combinatorial and Mixed Optimization [9 Lectures]

- Mixed integer linear programs [1.5]
- review of complexity classes
- Totally Unimodular Problems
- ex: finding optimal tours / Hamiltonian paths / coverings with tours or paths
- ex: scheduling
- ex: task assignment / matching
- ex: set cover
- ex: clearing combinatorial exchanges
- ex: stochastic programs with recourse (e.g., Steiner)

- stochastic hillclimbing [1.5]
- dist'n over neighborhood, exploring v. increasing moves
- random restarts
- example: MaxSAT search (MaxWalkSAT)

- cutting planes, branch & bound, branch & cut [1]
- approximation algorithms [2.5]
- rounding & duality
- ex: simple randomized rounding for 0/1 SVMs
- ex: Goemans/Williamson randomized rounding for MAXSAT and mincuts
- ex: minimum balanced cut for image segmentation

- submodularity [2.5]
- ex: set partition based on mutual information
- ex: most informative observations
- ex: information cascades
- ex: minimax Kriging, robust experimental design

Wed., Apr. 14:

- Intro to integer programs

[Slides] [Annotated]

Mon., Apr. 19:

- Lecture: Integer programs continued; Approximation algorithms; Rounding

[IP Annotated] [Rounding Slides] [Annotated]

Wed., Apr. 21:

- Lecture: rounding, continued [Rounding Slides] [Annotated]

Mon., Apr. 26:

- Lecture: Approximation algorithms (cont.), Submodularity [Slides] [Annotated]

Wed., Apr. 28:

- Lecture: Submodularity, cont. [Slides] [Annotated]

[Top]

Additional Topics

- Use of bounds in optimization
- coordinate ascent
- EM algorithm
- ex: k-means, Baum-Welch

- variational bounding
- ex: tree-reweighted BP

- Fisher scoring
- games and equilibria as optimization problems
- ex: equilibria in extensive-form games; sequence form
- ex: equilibria in convex games; transformation regret
- ex: finding Nash equilibria in matrix games

[Top]