Principles of Optimization - Lecture Notes and Videos

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