Linear Optimization (Math 464): Lecture Notes and Videos

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

Last modified: Wed Apr 26 14:20:17 PDT 2023