University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

468

Pages:

9
Author:

Karley Brady

Optimization Methods Introduction 1 Outline Polyhedra Standard form Algebraic and geometric de nitions of corners Equivalence of de nitions Existence of corners Optimality of corners Conceptual algorithm 2 Central Problem minimize subject to Slide 2 cx ai x = bi ai x bi ai x bi 0 i 2 M1 i 2 M2 i 2 M3 j 2 N1 j 2 N2 0 0 0 xj 0 xj >< 0 2.1 Standard Form minimize subject to cx Ax = b x0 Slide 3 c x) Slide 4 0 Characteristics Slide 1 Minimization problem Equality constraints Non-negative variables 2.2 Transformations max c x ai x bi ; min(; 0 ai x + si = bi si 0 0 ai x bi 0 xj >< 0 0 0 , ai x ; si = bi si 0 0 xj = xj+ ; xj x+j 0 xj 0 ; ; 1 2.3 Example Slide 5 maximize x1 ; x2 subject to x1 + x2 1 x1 + 2x2 1 x1 >< 0 x2 0 + ;minimize ;x1+ + x; 1 + x2 subject to x+1 ; x;1 + x2 + s1 =1 x+1 ; x;1 + 2x2 ; s2 = 1 x+1 x;1 x2 s1 s2 0 3 Preliminary Insights Slide 6 minimize ;x1 ; x2 subject to x1 + 2x2 3 2x1 + x2 3 x1 x2 0 x2 3 - x1 - x2 = - 2 1.5 - x1 - x2 = z (1,1) - x1 - x2 = 0 3 1.5 c x1 x1 + 2x2 < 3 2x1 + x2 < 3 ;x1 + x2 x1 x2 1 0 0 There exists a unique optimal solution. There exist multiple optimal solutions in this case, the set of optimal solutions can be either bounded or unbounded. 2 Slide 7 Slide 8 x2 c = (1,0) c = (- 1,- 1) 1 c = (0,1) c = (1,1) x1 The optimal cost is ;1, and no feasible solution is optimal. The feasible set is empty. 4 Polyhedra 4.1 Denitions The set fx j a x = bg is called a hyperplane. The set fx j a x bg is called a halfspace. The intersection of many halfspaces is called a polyhedron. 0 0 b3 x= a '2 = a '3x b2 a3 a2 a' x < b 1 =b a1 a 4' x = b4 a5 a a5' x = b 5 (b) (a) 3 1x =b a4 a' a' x a' x > b Slide 9 5 Corners 5.1 Extreme Points Slide 10 Polyhedron P = fx j Ax bg x 2 P is an extreme point of P if 6 9 y z 2 P (y = 6 x z= 6 x): x = y + (1 ; )z 0 < < 1 . . . w u v P . . . z x y 5.2 Vertex Slide 11 x 2 P is a vertex of P if 9 c: x is the unique optimum minimize subject to 5.3 Basic Feasible Solution cy y2P 0 P = f(x1 x2 x3) j x1 + x2 + x3 = 1 x1 x2 x3 0g Slide 12 Slide 13 Points A,B,C : 3 constraints active Point E: 2 constraints active suppose we add 2x1 + 2x2 + 2x3 = 2. 4 . w {y | c 'y =c 'w } P c . c x 'x } 'y = c {y | c x3 . A E D . . . P x2 C . B x1 Then 3 hyperplanes are tight, but constraints are not linearly independent. Intuition: a point at which n inequalities are tight and corresponding equations are linearly independent. P = fx 2 n, then there exist n linearly independent fai i 2 I g x degenerate. A D C P B E (a) (b) 6 Equivalence of denitions Slide 16 Theorem: P = fx j Ax bg. Let x 2 P . x is a vertex , x is an extreme point , x is a BFS. 7 BFS for standard form polyhedra Ax = b and x 0 m n matrix A has linearly independent rows x 2