University:
The University Of Western Ontario
Course:
MATH 3020A | Introduction to Abstract Algebra
Academic year:

2024
Views:

431

Pages:

3
Author:

Kyuwon J.

Problem 3 Consider the following LP: max cT x subject to Ax = b, x ≥ 0 (P) and its dual: min bT y subject to AT y ≥ c (D) Let c ∈ Rn be such that the dual problem (D) is feasible. Set B = {Ax : x ≥ 0}, so b ∈ B if and only if the primal problem is feasible. Note that B is a convex set. Recall from Assignment 6 that a function f : B → R is convex if and only if f (λb0 + (1 − λ)b1 ) ≤ λf (b0 ) + (1 − λ)f (b1 ) for every b0 , b1 ∈ B and 0 ≤ λ ≤ 1. A function f : B → R is concave if −f is convex. (a) Prove that a function f : B → R is concave if and only if f (λb0 + (1 − λ)b1 ) ≥ λf (b0 ) + (1 − λ)f (b1 ) for every b0 , b1 ∈ B and 0 ≤ λ ≤ 1. (a) Proof: We are asked to prove that a function f : B → R is concave if and only if f (λb0 + (1 − λ)b1 ) ≥ λf (b0 ) + (1 − λ)f (b1 ). Since f is concave, we know that −f is convex. By the definition of convexity, −f (λb0 + (1 − λ)b1 ) ≤ λ(−f (b0 )) + (1 − λ)(−f (b1 )) for every b0 , b1 ∈ B and 0 ≤ λ ≤ 1. Multiplying this inequality by −1, we obtain f (λb0 + (1 − λ)b1 ) ≥ λf (b0 ) + (1 − λ)f (b1 ), 1 which is the desired inequality. The reverse direction follows similarly. If f (λb0 + (1 − λ)b1 ) ≥ λf (b0 ) + (1 − λ)f (b1 ), multiplying through by −1 gives −f (λb0 + (1 − λ)b1 ) ≤ λ(−f (b0 )) + (1 − λ)(−f (b1 )). By definition, this means −f is convex, so f is concave. (b) Prove that the function f : B → R defined by f (b) = max{cT x : Ax = b, x ≥ 0} is concave. (b) Proof: We are tasked with proving that the function f : B → R defined by f (b) = max{cT x : Ax = b, x ≥ 0} is concave. Let b1 , b2 ∈ B and 0 ≤ λ ≤ 1. Define b3 = λb1 + (1 − λ)b2 . Let x1 and x2 be solutions to Ax = b1 and Ax = b2 , respectively, such that f (b1 ) = cT x1 and f (b2 ) = cT x2 . Now, define x3 = λx1 + (1 − λ)x2 . Then: Ax3 = A(λx1 +(1−λ)x2 ) = λ(Ax1 )+(1−λ)(Ax2 ) = λb1 +(1−λ)b2 = b3 . Thus, x3 is feasible for b3 . By the definition of f , we have: f (b3 ) = max{cT x : Ax = b3 , x ≥ 0} ≥ cT x3 . Substituting x3 , we get: f (b3 ) ≥ cT (λx1 +(1−λ)x2 ) = λcT x1 +(1−λ)cT x2 = λf (b1 )+(1−λ)f (b2 ). Therefore, f is concave. (c) Let g(b) = −f (b) for every b ∈ B. Let b ∈ B, and let ȳ ∈ Rm be an optimal solution to the dual problem (D). Show that −ȳ is a subgradient of g at b, i.e., that g(z) ≥ g(b) − ȳ T (z − b) for every z ∈ B. 2 (c) Proof: We need to show that −ȳ is a subgradient of g(b), meaning that g(z) ≥ g(b) − ȳ T (z − b) for every z ∈ B. Since ȳ is optimal for the dual problem, we know by the strong duality theorem that: bT ȳ = f (b) = −g(b). For any z ∈ B, substituting g(b) = −f (b), this becomes: −f (z) ≥ −f (b) − ȳ T z + ȳ T b. Simplifying: f (z) ≤ f (b) + ȳ T (z − b). Since f (z) = cT x for some x such that Ax = z, and ȳ T A ≥ cT , we have: f (z) ≤ ȳ T z. Thus: g(z) ≥ g(b) − ȳ T (z − b). 3