Math 364 (Spring 2017) - Lecture Notes and Videos on Principles of Optimization
Scribes from all lectures so far (as a single big file)Lec # | Date | Topic(s) | Scribe | Panopto |
---|---|---|---|---|
1 | Jan 10 | syllabus, optimization in calculus, the system \(A\mathbf{x} = \mathbf{b}\), EROs, basic/non-basic variables, parametric vector form of solutions | scribe | video |
2 | Jan 12 | transpose, matrix multiplication, linear combination, linear independence, rank and inverse of \(A\), Gauss-Jordan method in general | scribe | video |
3 | Jan 17 | snow make-up lecture: Gauss-Jordan method \(A = [B ~ N], \mathbf{x} = [\mathbf{x}_B ~\mathbf{x}_N]^T\), parametric vector form \(\mathbf{x}_B = B^{-1}\mathbf{b} - B^{-1}N \mathbf{s},~\mathbf{s} \in \mathbb{R}^{n-m}\) | scribe | video |
4 | Jan 19 | hints on Hw1, LP formulation examples, decision variables (d.v.s), objective function, constraints, sign restrictions, assumptions of LP | scribe | oops :-( |
5 | Jan 24 | graphical solution of LP in 2D, feasible region, sliding \(z\)-line, convex set, cases of LP: alternative optima, infeasible and unbounded LPs | scribe | video |
6 | Jan 26 | currency exchage giving unbounded LP, LP fomulations: staffing problem, blending problem, average quality, inventory planning | scribe | video |
7 | Jan 31 | inventory constraints in unified form, multiperiod scheduling LP formulation, intro to AMPL, AMPL handout | scribe | video |
8 | Feb 2 | more AMPL, alternative AMPL files for Farmer Jones LP using # instead of set of crops, standard form of LP, slack/excess variables | scribe | video |
9 | Feb 7 | basic solutions, basic feasible solution (bfs), corner point \(\equiv\) bfs, LP with optimal solution has optimal bfs, adjacent bfs, # possible bfs' | scribe | video |
10 | Feb 9 | simplex method, canonical form of LP, testing optimality of bfs, entering variable, min ratio test, leaving variable, pivoting to next bfs | scribe | video |
11 | Feb 14 | tableau simplex method, simplex for min-LPs: optimal if all variable entries in Row-0 \(\leq 0\), alternative optimal solutions in tableau | scribe | Pt1 , Pt2 |
12 | Feb 16 | all optima as convex combinations of optimal vertices, unbounded LPs: no candidate for min-ratio, big-M method, artifical variable | scribe | P1, P2, P3 |
13 | Feb 21 | detecting infeasibility in big-M simplex, handling unrestricted in sign (urs) vars: \(x_i \leftarrow x_i^+ - x_i^-\), for \(x_i^+, x_i^- \geq 0\), a full example | scribe | video |
14 | Feb 23 | Problems from Homework 6, review for midterm, practice midterm problems | scribe | video |
15 | Feb 28 | midterm exam | ||
16 | Mar 2 | more AMPL, putting an LP fully in the model file vs model+data, sensitivity analysis in 2D: changing objective function coefficient \(c_j\) | scribe | video |
17 | Mar 7 | changing coefficient of wheat, changing rhs of a constraint \(b_i \rightarrow b_i + \Delta\), shadow price of a constraint, economic interpretation | scribe | video |
18 | Mar 9 | simplex method in matrix form, \(A =[B~N], \mathbf{x}^T = [\mathbf{x}_B^T~\mathbf{x}_N^T ]\), optimal \(\mathbf{x}_B = B^{-1}\mathbf{b},\, z^* = \mathbf{c}_B^T B^{-1}\mathbf{b}\), optimal tableau given optimal \(BV\) | scribe | video |
19 | Mar 21 | sensitivity analysis in matrix form: changing \(c_j\) for non-basic \(x_j\), reduced cost, quick reoptimization, changing \(c_j\) for basic \(x_j\) | scribe | video |
20 | Mar 23 | changing \(b_i \rightarrow b_i + \Delta\), shadow price, changing \(c_j\) and \(A_{ij}\) for nonbasic \(x_j\) simultaneously, LP duality, normal constraints and variables | scribe | video |
21 | Mar 28 | dual of a general normal max LP, table of primal-dual relations, motivation for the dual, economic interpretation of Farmer Jones LP | scribe | video |
22 | Mar 30 | interpretation of Gaseous min-LP (Hw2), duality in matrix form, weak and stroing duality, dual theorem: \(\mathbf{y}^T = \mathbf{c}_B^T B^{-1}\) is optimal for (D) | scribe | video |
23 | Apr 4 | optimal tableau of Farmer Jones LP in Octave, reading off optimal dual solution, shadow price\(_i = y_i\), AMPL illustration | scribe | video |
24 | Apr 6 | hints on Homework 10, complementary slackness conditions (CSCs), using CSCs to solve LPs: AMPL illustration | scribe | video |
25 | Apr 11 | discussion on Project, integer programming (IP), rounding LP solution, IP formulation: basketball starting line-up, if-then constaints | scribe | video |
26 | Apr 13 | fixed charge MIP, forcing constraint, smallest big-\(M\), general either-or constraint, OR vs XOR, modeling more than two options | scribe | video |
27 | Apr 18 | more on Project, reading in training/test sets into AMPL, modeling (as MIP) if-then constraints as either-or, warehousing example | scribe | video |
28 | Apr 20 | modeling general either-or and general if-then statements using extra binary variables | scribe | video |
29 | Apr 25 | review of problems from Homework 8 and Homework 10, problem from the practice final | scribe | video |
30 | Apr 27 | review of problems from the practice final | scribe | video |