15.093 - Recitation 2 September 21, 2009 1 Linear Algebra Review Read Section 1.5 of BT. Important concepts: • linear independence of vectors • subspace, basis, dimension • the span of a collection of vectors • the rank of a matrix • nullspace, column space, row space 2 BT Exercise 2.10 Problem Consider the standard form polyhedron P = {x ∈ Rn |Ax = b, x ≥ 0}. Suppose that the matrix A has dimensions m × n and that its rows are linearly independent. For each one of the following statements, state whether it is true or false. If true, provide a proof, else, provide a counterexample. 1. If n = m + 1, then P has at most two basic feasible solutions. 2. The set of all optimal solutions is bounded. 3. At every optimal solution, no more than m variables can be positive. 4. If there is more than one optimal solution, then there are uncountably many opti mal solutions. 5. If there are several optimal solutions, then there exist at least two basic feasible solutions that are optimal. 6. Consider the problem of minimizing max{c’x, d’x } over the set P . If this problem has an optimal solution, it must have an optimal solution which is an extreme point of P . 1 Solution 1. True. The set P lies in an aﬃne subspace deﬁned by m = n−1 linearly independent constraints, that is, of dimension one. Hence, every solution of Ax = b is of the form x0 + λx1 , where x0 is an element of P and x1 is a nonzero vector. This, P is contained in a line and cannot have more than two extreme points. (If it had three, the one “in the middle” would be a convex combination of the other two, hence not an extreme point). 2. False. Consider minimizing 0, subject to x ≥ 0. The optimal solution set [0, ∞) is unbounded. 3. False. Consider a standard form problem with c = 0. Then, any feasible x is optimal, no matter how many positive components it has. 4. True. If x and y are optimal, so is any convex combination of them. 5. False. Consider the problem of minimizing x2 subject to (x1 , x2 ) ≥ (0, 0) and x2 = 0. Then the set of all optimal solutions is the set {(x1 , 0)|x1 ≥ 0}. There are several optimal solutions, but only one optimal BFS. 6. False. Consider the problem of minimizing |x1 −0.5| = max{x1 −0.5x3 , −x1 +0.5x3 } subject to x1 +x2 = 1, x3 = 1 and (x1 , x2 , x3 ) ≥ (0, 0, 0). Its unique optimal solution is (x1 , x2 , x3 ) = (0.5, 0.5, 1) which is not a BFS. 3 BFS Deﬁnition. Consider a polyhedron P deﬁned by linear equality and inequality con straints, and let x∗ ∈ Rn . Then 1. The vector x∗ is a basic solution if: • All equality constraints are active; • Out of the constraints that are active at x∗ , there are n of them that are linearly independent. 2. If x∗ is a basic solution that satisﬁes all of the constraints, we say that it is a basic feasible solution. 4 Degeneracy Deﬁnition. A basic solution x ∈ Rn of a linear optimization problem is said to be degenerate if there are more than n constraints which are active at x. Deﬁnition. Consider the standard form polyhedron P = {x ∈ Rn |Ax = b, x ≥ 0} and let x be a basic solution. Let m be the number of rows of A. The vector x is a degenerate basic solution if more than n − m of the components of x are zero. 2