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 might 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 | Video |
| 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
|