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
15
Feb 27
simplex method will terminatate, \(\mathbf{x'} = \mathbf{x} +
\theta\mathbf{d}\) is a bfs, options for pivot selection,
checking \(c'_j\) one at a time, naive implementation
scribe
video
16 Mar 1
*make-up
lecture*: revised simplex method, updating \(B^{-1}\)
using EROs: \(\begin{bmatrix} B^{-1} \,|\,-\mathbf{d}_B
\end{bmatrix} \rightarrow \begin{bmatrix} B'^{-1} \,|\,
\mathbf{e}_{\ell} \end{bmatrix}\), full illustration of the
method
scribe
video
17
Mar 6
hints for problems from Homework 7, full tableau
implementation of simplex method, example, use of
\(-\mathbf{c}^T_B \mathbf{x}_B\) in \((0,0)\)-element
scribe
video
18 Mar 8
tableau simplex on popular LP example in Octave,
example of cycling in simplex method shown in Octave
scribe
video
19
Mar 20
lexicographic ordering, lex-positive, lexicographics pivoting to
avoid cycling, Bland's rule, big-M method, example
in Octave
scribe
video
20 Mar 22
detect infeasibility using big-M, two-phase simplex, a full
example using big-M (Octave),
comparing revised and tableau simplex
scribe
video
21
Mar 27
project, LP
duality, Lagrangian, dual LP of a general form LP, table of
primal-dual relationships, normal variables and constraints
scribe
video
22 Mar 29
*make-up lecture*: duality in matrix form, weak duality,
(P) unbounded \(\Rightarrow\) (D) infeasible, strong duality,
(P) and (D) both infeasible
scribe
video
23
Apr 3
complementary slackness conditions, constraint inactive
\(\Rightarrow\) dual var \(=0\), mechanical analogy for LP
duality, AMPL problems
scribe
video
24 Apr 5
economic interpretation of dual LP, dual variables as shadow
prices, AMPL run,
Farkas' lemma, proof using LP duality
scribe
video
25
Apr 10
illustration of Farkas' lemma in 2D, alternative forms,
application in asset pricing and arbitrage, dual variables as
marginal costs
scribe
video
26 Apr 12
hint for AMPL, dual simplex method, primal optimality \(\equiv\)
dual feasiblity, dual simplex pivot, proof problem
from Homework
7
scribe
video
27
Apr 17
proof problem from Homework 7, true-false problem
from Homework
8, extra problem (BT-ILO exercise 3.19)
scribe
video
28 Apr 19
hints for problems from Homework 10
scribe
video
29
Apr 24
illustration of Bland's rule (Octave
session), discussion on project, bad
instances for simplex, spanning path visiting \(2^n\) vertices
scribe
video
30 Apr 26
more discussion on the project
scribe
video

Last modified: Thu Apr 26 14:33:37 PDT 2018