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

Last modified: Thu Apr 28 23:14:37 PDT 2016