• University of Illinois, Urbana Champaign

• IE 411

4.4 Let A be a symmetric square matrix. Consider the linear programming problem minimize c 0x subject to Ax ≥ c x ≥ 0 Prove that if x ∗ satisfies Ax∗ = c and x ∗ ≥ 0, then x ∗ is an optimal solution. Suppose Ax∗ = c and x ∗ ≥ 0. Let’s formulate the dual: maximize p 0 c subject to p 0A ≤ c 0 p ≥ 0 p 0A ≤ c 0 ⇒ p 0Ax∗ ≤ c 0x ∗ ⇒ p 0c ≤ c 0x ∗ and since A is square and symmetric, we have c 0p ≤ c 0x ∗ . Since the dual’s objective is to maximize p 0c, set p = x ∗ . Since x ∗ ≥ 0, p ≥ 0. x ∗ and p are feasible solutions to the primal and dual and p 0b = c 0x where b = c in this problem according to standard notation. By Corollary 4.2, x ∗ and p are optimal solutions to the primal and dual, respectively. 4.7 (Duality in piecewise linear convex optimization) Consider the problem of minimizing maxi=1,...,m (a 0 ix−bi) over all x ∈ R n. Let v be the value of the optimal cost, assumed finite. Let A be the matrix with rows a1, . . . , am, and let b be the vector with components b1, . . . , bm. (a) Consider any vector p ∈ R m that satisfies p 0A = 0 0 , p ≥ 0 and Pm i=1 pi = 1. Show that −p 0b ≤ v. (b) In order to obtain the best possible lower bound of the form considered in part (a), we form the linear programming problem maximize −p 0b subject to p 0A = 0 0 subject to p 0 e = 1 p ≥ 0 Formulate the dual: minimize v subject to p 0A = 0 0 subject to p 0 e = 1 xfree