Math 464 (Spring 2018) - 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 9
syllabus, optimization in
calculus, solving \(A\mathbf{x} = \mathbf{b}\) using EROs,
linear program example: Dude's Thursday problem
scribe
video
2 Jan 11
*no
class*
3
Jan 16
general form of a linear program (LP), feasible and optimal
solutions, standard form, conversion to std form, excess/slack
variables
scribe
video
4 Jan 18
LP formulations, diet problem, solution in AMPL, road lighting
problem, exceeding illumination limits, currency exchange LP
scribe
video
5
Jan 23
convex function, piecewise linear (PL) convex (PLC) functions,
max of convex functions is convex, PLC functions in LP
scribe
video
6 Jan 25
\(|x_i| \to x_i^+, x_i^-\), lighting problem: get "close to"
\(I_i^*\), inventory planning LP, graphical solution in 2D,
feasible region, slide \(\mathbf{c}^T\mathbf{x}\) line
scribe
video
7
Jan 30
cases of LP, unique and alternative optimal solutions, unbounded
LP, infeasible LP, subspace, affine spaces, polyhedron,
halfspace
scribe
video
8 Feb 1
polyhedron is convex, bounded set, convex hull, active
constraint, extreme point, vertex, basic and basic feasible
solution (bfs)
scribe
video
9
Feb 6
proof of extreme point \(\Leftrightarrow\) vertex
\(\Leftrightarrow\) bfs, adjacent basic solutions and bfs's,
polyhedron \(P\) in standard form, basic solutions of \(P\)
scribe
video
10 Feb 8
finding basic solutions in Octave,
correspondence of corner points and bfs's, degenrate basic bfs,
degeneracy and representation
scribe
video
11
Feb 13
degeneracy in standard form, \(P\) has no line \(\Leftrightarrow
P\) has vertex, existence of optimal vertex, shape of standard
form polyhedron
scribe
video
12 Feb 15
simplex method, feasible direction at \(\mathbf{x}\):
\(\mathbf{x}+\theta\mathbf{d} \in P \mbox{ for } \theta > 0,
j\)th basic direction at bfs \(\mathbf{x}\), reduced cost
\(\mathbf{c}'^T = \mathbf{c}^T - \mathbf{c}_B B^{-1} A \)
scribe
video
13
Feb 20
hints for problems from Hw6, LP optimality conditions in
standard form: basis \(B\) optimal if \(B^{-1}\mathbf{b} \geq
\mathbf{0}\) and \(\mathbf{c}^T - \mathbf{c}_B B^{-1} A \geq
\mathbf{0}^T\)
scribe
video
14 Feb 22
entering/leaving variable, min-ratio test: \(\theta^* =
\min_{\{i \in \scr{B}|d_{B(i)} < 0\}} \,(-x_{B(i)}/d_{B(i)}) \),
an iteration of the simplex method, Octave session
scribe
video

Last modified: Thu Feb 22 22:26:37 PST 2018