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
15 Feb 27 simplex method will terminatate, $$\mathbf{x'} = \mathbf{x} + \theta\mathbf{d}$$ is a bfs, options for pivot selection, checking $$c'_j$$ one at a time, naive implementation scribe video
16 Mar  1 make-up lecture: revised simplex method, updating $$B^{-1}$$ using EROs: $$\begin{bmatrix} B^{-1} \,|\,-\mathbf{d}_B \end{bmatrix} \rightarrow \begin{bmatrix} B'^{-1} \,|\, \mathbf{e}_{\ell} \end{bmatrix}$$, full illustration of the method scribe video
17 Mar  6 hints for problems from Homework 7, full tableau implementation of simplex method, example, use of $$-\mathbf{c}^T_B \mathbf{x}_B$$ in $$(0,0)$$-element scribe video
18 Mar  8 tableau simplex on popular LP example in Octave, example of cycling in simplex method shown in Octave scribe video
19 Mar 20 lexicographic ordering, lex-positive, lexicographics pivoting to avoid cycling, Bland's rule, big-M method, example in Octave scribe video
20 Mar 22 detect infeasibility using big-M, two-phase simplex, a full example using big-M (Octave), comparing revised and tableau simplex scribe video
21 Mar 27 project, LP duality, Lagrangian, dual LP of a general form LP, table of primal-dual relationships, normal variables and constraints scribe video
22 Mar 29 make-up lecture: duality in matrix form, weak duality, (P) unbounded $$\Rightarrow$$ (D) infeasible, strong duality, (P) and (D) both infeasible scribe video
23 Apr   3 complementary slackness conditions, constraint inactive $$\Rightarrow$$ dual var $$=0$$, mechanical analogy for LP duality, AMPL problems scribe video
24 Apr   5 economic interpretation of dual LP, dual variables as shadow prices, AMPL run, Farkas' lemma, proof using LP duality scribe video
25 Apr 10 illustration of Farkas' lemma in 2D, alternative forms, application in asset pricing and arbitrage, dual variables as marginal costs scribe video
26 Apr 12 hint for AMPL, dual simplex method, primal optimality $$\equiv$$ dual feasiblity, dual simplex pivot, proof problem from Homework 7 scribe video
27 Apr 17 proof problem from Homework 7, true-false problem from Homework 8, extra problem (BT-ILO exercise 3.19) scribe video
28 Apr 19 hints for problems from Homework 10 scribe video
29 Apr 24 illustration of Bland's rule (Octave session), discussion on project, bad instances for simplex, spanning path visiting $$2^n$$ vertices scribe video
30 Apr 26 more discussion on the project scribe video