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