Optimization Methods - Midterm Review

Midterm Review Overview • Linear Programming • Simplex Method • Duality Theory • Sensitivity Analysis • Column Generation Method 2 Linear Programming I • Standard form of linear programming problems min c
x s.t. Ax = b x≥0 • Standard form reduction + − − – Free variables xi = x+ i − xi , xi , xi ≥ 0 – Slack and surpus variables – max c
x = − min −c
x 3 Linear Programming II • Piecewise linear convex objective min z min maxi=1,...,m c
ix + di
s.t. z ≥ cix + di s.t. Ax = b ⇔ Ax = b x≥0 x≥0 • Absolute values min s.t. �n i=1 ci |xi | Ax = b x≥0 – zi = |xi| ⇔ xi ≤ zi and −xi ≤ zi + − – xi = xi+ − xi− , xi, − x− i ≥ 0 ⇒ |xi | = xi + xi (assume c ≥ 0) 4 Geometry of Linear Programming I • Convexity – Convex function f : f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ∀x, y, λ ∈ [0, 1] – Convex set S: λx + (1 − λ)y ∈ S for all x, y ∈ S, λ ∈ [0, 1] – Convex hull of x1, . . . , xk : � k � λi xi |λi ≥ 0 C= i=1 ∀i = 1, k, k � � λi = 1 i=1 • Polyhedra – P = {x ∈ Rn |Ax ≥ b}, A is a m × n matrix and b ∈ Rm – Standard form representation P = {x ∈ Rn|Ax = b, x ≥ 0} 5 Geometry of Linear Programming II • Extreme points – x ∈ P is an extreme point of P if  ∃y, z ∈ P , y, z = x, λ ∈ [0, 1]: x = λy + (1 − λ)z • Vertices – x ∈ P is a vertex of P if ∃c: c
x < c
y ∀y ∈ P, y = x • Basic feasible solutions – x ∈ P is a basic feasible solution if: 1. All equality constraints are active 2. There are n active constraints that are linearly independent 3. All constraints are satisfied 6 Simplex Method I • Optimality conditions for a basis B – B −1 b ≥ 0 (feasibility) – c
= c
− c
B B −1 A ≥ 0
(optimality) • Simplex development – d: feasible direction, then
B −1 N )d z = c
d = (c
− cB N – Simplex feasible direction: dB = −B −1Aj , dj = 1, then c
B B −1 Aj = cj � � xB(i) – y = x + θd feasible: θ ≤ mini|dB(i) <0 − dB(i) z = c
− 7 Simplex Method II • Unboundedness (objective) – cj < 0 – B −1 Aj ≤ 0 • Degeneracy (BFS) – More than n tight constraints – More than one basis – xB > 0 • Multiple optimal solutions – ∃j non basic: cj = 0 � � xB(i) ∗ – θ = mini|dB(i) <0 − dB(i) > 0 (θ∗ = ∞ if dB ≥ 0) 8 Simplex Method III • Revised simplex method – Elementary row operation: [B −1|B −1 Aj ] → [B −1 |el ] • Full tableau implementation −c
B B −1 b c
− c
B B −1 A B −1 b B −1 A • Initial tableau – Solve the problem with auxiliary variables (b ≥ 0) �m Z = min i=1 yi s.t Ax + y = b x, y ≥ 0 – Infeasiblity condition: Z > 0 9 Duality Theory I • Primal and dual problem min c
x max p
b s.t. Ax = b ↔ s.t. p
A ≤ c
x≥0 max p
b min ↔ s.t. p
A = c
s.t. Ax ≥ b p≥0 c
x • Duality theorem – Weak duality: x, p are feasible solution to primal and dual problem, then p
b ≤ c
x – Strong duality: primal problem has an optimal solution ⇔ dual prob­ lem has an optimal solution and c
x∗ = b
p∗ – Complementary slackness: x, p are feasible solution to primal and dual problem, then x, p are optimal solution if and only if pi(a
ix−bi) = 0 ∀i and (cj − p
Aj )xj = 0 ∀j 10 Duality Theory II • Solution possibilities Finite Optimum Unbounded Infeasible Finite Optimum Unboundedness Infeasible ∗ − − − − ∗ − ∗ ∗ • Dual simlex method – Dual basis solution p
= c
B B −1 – Dual feasibility condition c
− p
A ≥ 0: primal optimality condition – Dual simplex: maintaining dual feasibility, working towards primal feasibility – Optimality conditions: both primal and dual feasibility – Primal infeasibility (dual unboundedness) detection • Farkas’s lemma  ∃x ≥ 0 : Ax = b ⇔ ∃p : p
A ≥ 0
, p
b < 0 11 Sensitivity Analysis I • Basic question When input data (A, b, c) change, can we still use the current plan (current optimal basis)? • Optimality conditions need to be checked: – B −1 b ≥ 0 (feasibility) – c
= c
− c
B B −1 A ≥ 0
(optimality) • Changes in b – Feasibility condition needs to be checked – Allowable range calculation • Changes in c – Optimality condition needs to be checked – Allowable range calculation (basic and non-basic cases) 12 Sensitivity Analysis II • A new variable added – Optimality condition needs to be checked – Primal simplex method • A new inequality constraint added – The current solution needs to be checked against the new constraint – Construct new tableau for new problem if new constraint is violated • Global dependence on b – The optimal cost F (b) is a convex function of b • Global dependence on c – The optimal cost G(c) is a concave function of c 13 Column Generation Method • Problem The number of variables (number of columns of A) is very large and we cannot store the matrix in memory • Fact The optimal basic solution of a linear programming problem in standard form has at most m variables with positive values, where m is the number of rows of the matrix A • Idea Starting with a small number of variables and introducing (or replacing) new variables when needed • Implementation Solving the problem Z = minj (cj −p
Aj ). If Z ≥ 0, optimal solution is obtained; otherwise, introducing (or replacing one old column by) the column j ∗ = argminj (cj − p
Aj ). 14