Math 464:   Lecture Notes and Videos on Linear Optimization

Copyright: I (Bala Krishnamoorthy) hold the copyright for all lecture scribes/notes, documents, and other materials including videos posted on these course web pages. These materials shall not be used for commercial purposes without my consent.

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

Lec #	Date	Topic(s)	Scribe	Panopto
1	Jan 10	syllabus, optimization in calculus, solving \(A\mathbf{x} = \mathbf{b}\) using EROs, linear program (LP) example: Dude's Thursday problem	Scb1	Vid1
2	Jan 12	general form of an LP, feasible and optimal solutions, standard form, conversion to standard form, excess/slack variables	Scb2	Vid2
3	Jan 17	LP formulations, diet problem, solution in AMPL, road lighting problem, exceeding illumination limits, currency exchange (CE)	Scb3	Vid3
4	Jan 19	CE LP, convex function, piecewise linear (PL) convex (PLC) functions, max of convex functions is convex, PLC functions in LP	Scb4	Vid4
5	Jan 24	intuition for min-max, absolute values in LP, \(|x_i|\)\(\to\)\(x_i^+, x_i^-\) or \(z \geq x_i^{\pm}\), lighting problem: get "close to" \(I_i^*\), inventory planning LP	Scb5	Vid5
6	Jan 26	graphical solution in 2D, feasible region, slide z-line, cases of LP: unique/alternative optimal solution(s), unbounded/infeasible LP	Scb6	Vid6
7	Jan 31	subspace, affine spaces, polyhedron, polyhedron is a convex set, bounded set, convex hull of points is convex, extreme point	Scb7	Vid7
8	Feb   2	vertex, basic & basic feasible solution (bfs), basic solution depends on presentation of \(P\), proof of vertex \(\Rightarrow\) extreme point \(\Rightarrow\) bfs	Scb8	Vid8
9	Feb   7	adjacent basic solutions and bfs's, polyhedron \(P\) in standard form, basic solutions of \(P\), finding basic solutions & bfs's in Matlab	Scb9	Vid9
10	Feb   9	correspondence of corner points and bfs's, degenerate basic (feasible) solutions, degeneracy in standard form, Matlab session	Scb10	Vid10
11	Feb 14	\(P\) has no line\(\Leftrightarrow\)\(P\) has vertex, existence of optimal vertex, change to standard form keeps "shape" of \(P\), feasible direction at \(\mathbf{x}\)	Scb11	Vid11
12	Feb 16	direction: \(\mathbf{x}+\theta\mathbf{d} \in P \mbox{ for } \theta > 0, j\)th basic direction at \(\mathbf{x}\): \(\mathbf{d}_B = B^{-1}A_{j}\), reduced cost \(\mathbf{c}'^T = \mathbf{c}^T - \mathbf{c}_B B^{-1} A \), Matlab session	Scb12	Vid12
13	Feb 21	LP optimality conditions: \(B^{-1}\mathbf{b} \geq \mathbf{0}\), \(\mathbf{c} \geq \mathbf{0}\), entering/leaving var, min-ratio test: \(\theta^*\)\(=\)\(\min_{\{i \in \scr{B}|d_{B(i)} < 0\}} \,(-x_{B(i)}/d_{B(i)}) \), Matlab	Scb13	Vid13
14	Feb 23	make-up lecture: an iteration of the simplex method, Matlab session, simplex method will terminate, \(\mathbf{x}'\)\( = \mathbf{x} + \theta\mathbf{d}\) is a bfs	Scb14	Vid14
15	Feb 28	options: checking \(c'_j\) one at a time, naive simplex, revised simplex method, update \(B^{-1}\) with EROs \(\begin{bmatrix} B^{-1} \,|\,-\mathbf{d}_B \end{bmatrix} \rightarrow \begin{bmatrix} B'^{-1} \,|\, \mathbf{e}_{\ell} \end{bmatrix}\)	Scb15	Vid15
16	Mar   2	Hints for problems 5 and 6 from Homework 6, full example of revised simplex, tableau implementation of simplex method	Scb16	Vid16
17	Mar   7	hints for Homework 7, full tableau simplex example, use of \(-\mathbf{c}^T_B \mathbf{x}_B\) in \((0,0)\)-element, tableau for popular LP instance in Matlab	Scb17	Vid17
18	Mar   9	tableau simplex on popular LP instance (continued), cycling in tableau simplex, Matlab session, lexicographic order	Scb18	Vid18
19	Mar 21	lex ordering, lexicographic pivoting to avoid cycling, Bland's rule, big-M method, artifical variables, LP example, Matlab session	Scb19	Vid19
20	Mar 23	detect infeasibility using big-M, two-phase simplex, a full example using big-M (Matlab), comparing revised and tableau simplex	Scb20	Vid20
21	Mar 28	LP duality, Lagrangian, dual LP of a general form LP, table of primal-dual relationships, normal variables and constraints	Scb21	Vid21
22	Mar 30	duality in matrix form, weak duality, (P) unbounded \(\Rightarrow\) (D) infeasible, strong duality, (P) and (D) both infeasible, hints for Hw9	Scb22	Vid22
23	Apr   4	complementary slackness, constraint inactive\(\Rightarrow\)dual var\(=0,\) mechanical analogy for duality, economic interpretation of dual LP	Scb23	Vid23
24	Apr   6	read command, displaying dual vars, and CSCs in AMPL, dual variables as shadow prices, Farkas' lemma, proof using duality	Scb24	Vid24
25	Apr 11	illustration of Farkas' lemma in 2D, alternative forms, application in asset pricing and arbitrage, dual variables as marginal costs	Scb25	Vid25
26	Apr 13	dual simplex method, primal optimality(feasibility) \(\equiv\) dual feasiblity(optimality), dual simplex pivot, Homework 7 proof problems	Scb26	Vid26
27	Apr 18	implementing Bland's rule in Matlab (session), extra problem from BT-ILO on simplex tableau, problems from Homework 10	Scb27	Vid27
28	Apr 20	details of the Project, form of functions, running time in Matlab, Jimbo LP and its \(A \mathbf{x} \leq \mathbf{b}\) form, repmat, reshape in Matlab	Scb28	Vid28
29	Apr 25	discussion on the project, interior point methods, bad instances for the simplex method, spanning path visiting \(2^n\) vertices	Scb29	Vid29