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