Linear Optimization - Lecture Notes and Videos

Math 464 (Spring 2016)  - 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 12 syllabus, motivation from calculus, linear algebra basics scribe video
2 Jan 14 motivating LP, solution in AMPL, general form of LP, feasible and optimal solutions, standard form of LP scribe video
3 Jan 19 conversion to standard form LP, LP formulations, lighting problem - minimize excess, diet problem scribe video
4 Jan 21 diet problem in AMPL, when to insist integrality of variables, currency conversion LP, convex functions scribe video
5 Jan 26 piecewise-linear (PL) convex (PLC) functions, PLC functions in min objective or lhs of $$\leq h$$ constraints, lighting LP scribe video
6 Jan 28 inventory planning, graphical solution in 2D, Cases I,II,III: unique optimal solution, alternative optima, unbounded LP scribe video
7 Feb  2 optimal solutions as convex combinations, Case IV-infeasible LP, unbounded feasible region, affine subspace, polyhedron scribe video
8 Feb  4 convex set, half space, polyhedron is convex, bounded set, extreme point, vertex, basic solution, basic feasible solution (bfs) scribe video
9 Feb  9 extreme point $$\Leftrightarrow$$ vertex $$\Leftrightarrow$$ bfs, adjacent bfs's, polyhedron in standard form, basic solutions, basis matrix, $$\mathbf{x}_B = B^{-1} \mathbf{b}$$ scribe video
10 Feb 11 vertices and bfs's correspondences, Octave session, degenerate basic solutions, degeneracy and representations of $$P$$ scribe v1   v2
11 Feb 16 degenerate bfs in Octave, removing degeneracy, $$P$$ has a line $$\Leftrightarrow P$$ has no vertex, optimal solutions of vertex-free LPs scribe video
12 Feb 18 optimality and extreme points, change in "shape" on going to standard form, feasible direction at $$\mathbf{x} \in P$$, $$\mathbf{d}_j = B^{-1}A_j$$ scribe video
13 Feb 23 $$j$$th feasible direction at bfs $$\mathbf{x}$$, reduced cost of $$x_j$$: $$c'_j = c_j - \mathbf{c}^T_B B^{-1} A_j$$, $$c_j=0$$ for $$x_j$$ basic, Octave session scribe video
14 Feb 25 proof for "$$\mathbf{c}' \geq \mathbf{0} \Rightarrow \mathbf{x}$$ optimal bfs", simplex method, min-ratio test, leaving and entering variable, Octave session scribe video
15 Mar  1 an iteration of the simplex method, illustration in Octave, finiteness of the simplex method scribe video
16 Mar  3 $$\mathbf{y} = \mathbf{x} + \theta^* \mathbf{d}$$ is a bfs, pivot selection, naive implementation, simplex multipliers, convert $$-\mathbf{d}_B$$ to $$\mathbf{e}_{\ell}$$ via EROs to find $$B'^{-1}$$ scribe video
17 Mar  8 proof problems from Homework 7, example of $$[ B^{-1} \, | \, -\mathbf{d}_B ] ~ \overrightarrow{\rm EROs} ~ [ (B')^{-1} | \mathbf{e}_{\ell} ]$$, revised simplex method, 2D example scribe video
18 Mar 10 problem from Homework 5, revised simplex example, tableau simplex, row-$$0$$, column-$$0$$, pivot row/column/element scribe video
19 Mar 22 problem from Homework 6, full tableau implementation of simplex method in Octave, cycling in simplex method scribe video
20 Mar 24 lexicographic ordering, lexicographic pivoting rule to avoid cycling, Bland's rule, big-M method (Octave sesion) scribe video
21 Mar 29 big-M on infeasible LP, two-phase simplex, full example of big-M method, revised vs tableau simplex (Octave sesion) scribe video
22 Mar 31 Bland's rule (illustration), motivation for duality, Lagrangian, dual LP, primal-dual relationships, normal variable/constraint scribe video
23 Apr   5 dual of dual LP $$\equiv$$ primal LP, weak duality, LP unbouded $$\Rightarrow$$ dual LP infeasible, introduction to AMPL, AMPL session scribe video
24 Apr   7 further details on AMPL, AMPL session, strong duality with proof, possiblities of primal-dual pairs scribe video
25 Apr 12 complementary slackness conditions, economic interpretation, mechanical analogy for duality, certificate of infeasibility scribe video
26 Apr 14 Farkas' lemma, proof using LP duality, illustration in 2D, alternative forms, application to asset pricing and arbitrages scribe video
27 Apr 19 Recording run times in Octave and AMPL/Cplex, dual variables as shadow prices, economic interpretation of dual LP scribe video
28 Apr 21 on the project, generating AMPL commands, dual simplex, primal feasibility $$\equiv$$ dual optimality, dual simplex examples scribe video
29 Apr 26 more on the project, duality exercises from Homework 10, sensitivity analysis, adding a new variable scribe video
30 Apr 28 hints for problems from Homework 11 scribe video