15.081J/6.251J Introduction to Mathematical Programming Lecture 10: Duality Theory IIIA2 A3 . A1 p b 1 Outline Slide 1 • Farkas lemma • Asset pricing • Cones and extreme rays • Representation of Polyhedra 2 Farkas lemma Slide 2 Theorem: Exactly one of the following two alternatives hold: 1. ∃x ≥ 0 s.t. Ax = b. 2. ∃p s.t. p ′ A ≥ 0 ′ and p ′ b < 0. 2.1 Proof Slide 3 ′′ “ ⇒ If ∃x ≥ 0 s.t. Ax = b, and if p ′ A ≥ 0 ′ , then p ′ b = p ′ Ax ≥ 0 ′′ “ ⇐ Assume there is no x ≥ 0 s.t. Ax = b (P ) max 0 ′ x (D) min p ′ b s.t. Ax = b s.t. p ′ A ≥ 0 ′ x ≥ 0 (P) infeasible ⇒ (D) either unbounded or infeasible Since p = 0 is feasible ⇒ (D) unbounded ⇒ ∃p : p ′ A ≥ 0 ′ and p ′ b < 0 1� � � � � � � 3 Asset Pricing Slide 4 • n different assets • m possible states of nature • one dollar invested in s ome asset i, a nd state of nature is s, we receive a payoff of rsi • m × n payoff matrix:   r11 . . . r1n R =  .... ..  . .. rm1 . . . rmn Slide 5 • xi: amount held of asset i. A portfolio of assets is x = x1, . . . , xn . • A negative value of xi indicates a “short” position in ass e t i: this amounts to s e lling |xi| units of asset i at the beginning of the period, with a promise to buy them back at the end. Hence, one must pay out rsi|xi| if state s occurs, which is the same as receiving a payoff of rsixi Slide 6 • Wealth in state s from a p ortfolio x n ws = rsixi. i=1 • w = w1, . . . , wm , w = Rx • pi: price of asset i, p = p1, . . . , pn ′ • Cost of ac quiring x is p x. 3.1 Arbitrage Slide 7 • Central problem: Determine pi • Absence of arbitrage: no investor can get a guaranteed nonnegative payoff out of a negative investment. In other words, any portfolio that pays off nonnegative amounts in every state of nature, must have nonnegative cost. ′if Rx ≥ 0, then p x ≥ 0. Slide 8 2� � � � � � � • Theorem: The absence of arbitrage condition holds if and only if there exists a nonnegative vector q = (q1, . . . , qm), such that the price of each asset i is given by m pi = qsrsi. s=1 • Applications to options pricing 4 Cones and extreme rays 4.1 Definitions Slide 9 • A set C ⊂ ℜn is a cone if λx ∈ C for all λ ≥ 0 and all x ∈ C • A polyhedron of the form P = {x ∈ ℜn | Ax ≥ 0} is called a poly hedral cone 4.2 Applications Slide 10 • P = x ∈ ℜn | Ax ≥ b , y ∈ P • The recession co ne at y RC = d ∈ ℜn | y + λd ∈ P, ∀ λ ≥ 0 • It turns out that RC = d ∈ ℜn | Ad ≥ 0 • RC indep e ndent of y Slide 11 4.3 Extreme rays Slide 12 A x =� 0 of a po lyhedral cone C ⊂ ℜn is called a n extreme ray if there a re n − 1 linearly independent constraints that are active at x 4.4 Unbounded LPs Slide 13 ′ Theorem: Consider the problem of minimizing c x over a polyhedral cone C = {x ∈ ℜn | A ′ ix ≥ 0, i = 1, . . . , m} that ha s zero as an extreme point. The optimal cost is equal to −∞ if and only if some extreme ray d of C satisfies ′ ′ c d < 0. Theorem: C onsider the problem of minimizing c x subject to Ax ≥ b, Slide 14 and assume that the feasible set has at least one extreme point. The optimal cost is equal to −∞ if and only if some extreme ray d of the feasible set satisfies ′ c d < 0. What happens when the simplex method detects an unbounded problem? 3'x = 0 x2 x3 - a1 x1 x1 x2.y a1a2'x= 0 . . z. - a2 (a) (b) 4� � � � � � � x1 23 w 1 y... . recession cone x1 x2 xxw 2 5 Resolution Theorem Slide 15 P = x ∈ ℜn | Ax ≥ b be a nonempty polyhedron with at least one extreme point. Let x1 , . . . , xk be the extreme points, and let w1 , . . . , wr be a complete set of extreme rays of P . k r � k Q = λix i + θj wj �� λi ≥ 0, θj ≥ 0,λi = 1 . i=1 j=1 i=1 Then, Q = P . 5.1 Example Slide 16 x1 − x2 ≥ −2 x1 + x2 ≥ 1 x1, x2 ≥ 0 Slide 17 • Extreme points: x1 = (0, 2), x2 = (0, 1), and x3 = (1, 0). • Extreme rays w1 = (1, 1) and w2 = (1, 0). • � � � � � � � � 2 0 1 1 2 1 2 y = = + + = x + w + w . 2 1 1 0 5� � � � � � � 5.2 Proof Slide 18 • Q ⊂ P . Let x ∈ Q: k r x = λix i + θj wj i=1 j=1 �k λi, θj ≥ 0 i=1 λi = 1. • y = �ki=1 λixi ∈ P and satisfies Ay ≥ b. • Awj ≥ 0 for every j: z = �rj=1 θj wj satisfies Az ≥ 0. • x = y + z satisfies Ax ≥ b and belongs to P . Slide 19 For the reverse, assume there is a z ∈ P , such that z /∈ Q. k r max 0λi + 0θj i=1 j=1 k r s.t. λix i + θj wj = z i=1 j=1 k λi = 1 i=1 λi ≥ 0, i = 1, . . . , k, θj ≥ 0, j = 1, . . . , r, Is this feasible? Slide 20 • Dual ′ min p z + q s.t. p ′ xi + q ≥ 0, i = 1, . . . , k, ′ p wj ≥ 0, j = 1, . . . , r. • This is unbounded. Why? ′ • There exists a feasible solution (p, q) whose cost p z + q < 0 • p ′ z < p …