Linear Optimization - Lecture Notes and Videos

Math 464 (Spring 2018)  - Lecture Notes and Videos on Linear Optimization

Scribes from all lectures so far (as a single big file)

Lec # Date Topic(s) Scribe Panopto
1 Jan  9 syllabus, optimization in calculus, solving \(A\mathbf{x} = \mathbf{b}\) using EROs, linear program example: Dude's Thursday problem scribe video
2 Jan 11 no class
3 Jan 16 general form of a linear program (LP), feasible and optimal solutions, standard form, conversion to std form, excess/slack variables scribe video
4 Jan 18 LP formulations, diet problem, solution in AMPL, road lighting problem, exceeding illumination limits, currency exchange LP scribe video
5 Jan 23 convex function, piecewise linear (PL) convex (PLC) functions, max of convex functions is convex, PLC functions in LP scribe video
6 Jan 25 \(|x_i| \to x_i^+, x_i^-\), lighting problem: get "close to" \(I_i^*\), inventory planning LP, graphical solution in 2D, feasible region, slide \(\mathbf{c}^T\mathbf{x}\) line scribe video
7 Jan 30 cases of LP, unique and alternative optimal solutions, unbounded LP, infeasible LP, subspace, affine spaces, polyhedron, halfspace scribe video
8 Feb   1 polyhedron is convex, bounded set, convex hull, active constraint, extreme point, vertex, basic and basic feasible solution (bfs) scribe video
9 Feb   6 proof of extreme point \(\Leftrightarrow\) vertex \(\Leftrightarrow\) bfs, adjacent basic solutions and bfs's, polyhedron \(P\) in standard form, basic solutions of \(P\) scribe video
10 Feb   8 finding basic solutions in Octave, correspondence of corner points and bfs's, degenrate basic bfs, degeneracy and representation scribe video
11 Feb 13 degeneracy in standard form, \(P\) has no line \(\Leftrightarrow P\) has vertex, existence of optimal vertex, shape of standard form polyhedron scribe video
12 Feb 15 simplex method, feasible direction at \(\mathbf{x}\): \(\mathbf{x}+\theta\mathbf{d} \in P \mbox{ for } \theta > 0, j\)th basic direction at bfs \(\mathbf{x}\), reduced cost \(\mathbf{c}'^T = \mathbf{c}^T - \mathbf{c}_B B^{-1} A \) scribe video
13 Feb 20 hints for problems from Hw6, LP optimality conditions in standard form: basis \(B\) optimal if \(B^{-1}\mathbf{b} \geq \mathbf{0}\) and \(\mathbf{c}^T - \mathbf{c}_B B^{-1} A \geq \mathbf{0}^T\) scribe video
14 Feb 22 entering/leaving variable, min-ratio test: \(\theta^* = \min_{\{i \in \scr{B}|d_{B(i)} < 0\}} \,(-x_{B(i)}/d_{B(i)}) \), an iteration of the simplex method, Octave session scribe video

Last modified: Thu Feb 22 22:26:37 PST 2018