Version March 14, 2021 ESI 6417: Linear Programming & Network Optimization Midterm Due Tuesday, March 16, 2021 at 11:59pm ET • This exam consists of 4 questions worth a total of 100 points. • Please attempt to answer all questions (partial credit will be given when appropriate). Manage your time well: if you are stuck on a problem, it might be best to temporarily move on to other questions, then come back later. Explain your answers and show all your work. • Use the provided LATEX template to generate a PDF file that you will submit through Canvas. You should ensure that your submission compiles correctly, and please contact the instructor to quickly resolve any LATEX questions. • You are NOT allowed to discuss this exam, or share it, with other people. You may use your notes and anything uploaded to Canvas, including the recorded lessons, and you may refer to external references for definitions or examples, but NOT for solutions. • Any questions about the exam must be sent privately to the instructor. • Clearly define any mathematical notation you use. Exam Conditions: 1. While completing this exam: I will not communicate with any other individuals about this exam while completing it. I will not cooperate with anyone else while com- pleting this exam including sharing answers or disseminating any kind of information related to the problems. 2. After the exam: I will not discuss or disseminate information about the content of this exam or its solution before Tuesday, March 16, 2021 at 11:59pm ET. Failure to abide by these conditions will imply a violation of the Honor Code of the University of Florida and will subject violators to the consequences stated under violations in “The Orange Book” available at https://sccr.dso.ufl.edu/policies/student-honor-code-student-conduct-code/. By writing or typing my name below, I agree to abide by the above conditions. Name: 1 Question 1 (25 points) (a) (10 points) In class, we stated but did not prove the following fact: if X and Y are nonempty convex sets, then Z ..= {x+ y : x ∈ X, y ∈ Y } is convex. Prove this. Hint: Notice that if z ∈ Z, then there exists x ∈ X and y ∈ Y such that z = x+ y. (b) (15 points) A set X is convex if for any x, y ∈ X and λ ∈ [0, 1], the point λx+(1−λ)y ∈ X. Suppose X is closed and we know that, for any x, y ∈ X, the point (1/2)x+ (1/2)y belongs to X. Prove that this fact is sufficient to conclude that X is convex. Hint: Eventually you probably will use a limit. You may use the fact that for a closed set X, if zk ∈ X for all k ≥ 1, and limk→∞ zk = z, then z ∈ X. 2 Question 2 (40 points) Recall that: • A set K is a cone if and only if r ∈ K implies λr ∈ K for all λ ≥ 0. • For any finite set R = {r1, . . . , rk}, with rj ∈ Rn for all j ∈ [k], we defined cone(R) ..= {x ∈ Rn : ∃λ ∈ Rk≥0 such that x = ∑k j=1 λjr j}, where cone(∅) ..= {0}. • For a given r ∈ Rn, the ray generated by r is defined as the set {tr : t ≥ 0}, and for convenience we simply say “the ray r” when we refer to the entire set {tr : t ≥ 0}. • If K is a cone, an extreme ray of K is a ray r ∈ K that is nontrivial (r 6= 0) and for any u, v ∈ K and λ1, λ2 > 0 such that r = λ1u+ λ2v, it holds that u, v ∈ {tr : t ≥ 0}. (a) (5 points) Give an example of a nonconvex cone, and show that it is nonconvex. (b) (5 points) Let K be a cone and r ∈ K \{0}. Suppose that for any u, v ∈ K, if r = u+v, then u, v ∈ cone({r}). Show that r is extreme. 3 (c) (15 points) Show that if K ..= {x ∈ Rn : aTix ≤ 0 for all i ∈ [m]} = {x ∈ Rn : Ax ≤ 0} is a polyhedral cone, then every extreme ray of K is defined by at least n − 1 linearly independent constraints of K, i.e., for every extreme ray r ∈ K, aTi r = 0 for at least n− 1 linearly independent vectors out of {ai}mi=1. Hint: There are several possible proofs to this question. Recall from class that we proved a theorem showing the equivalence of a vertex, an extreme point, and a basic feasible solution. One idea is to adapt the proof of the theorem from class. Another is to invoke the theorem from class in a clever way, after defining a new polyhedron based onK in which a given extreme ray r corresponds to a vertex of the new polyhedron. It may be helpful to remember the rank-nullity theorem: given a matrix A ∈ Rm×n, it holds that rank(A) + dim({x ∈ Rn : Ax = 0}) = n. (d) (15 points) If K ..= {x ∈ Rn : aTix ≤ 0 for all i ∈ [n]} is a polyhedral cone defined by n linearly independent inequalities, show that it has n extreme rays. Hint: You may want to first show that the solution set to a system of n−1 linearly independent constraints of K defines an extreme ray, i.e., the converse of the previous part. 4 Question 3 (15 points) Provide a certificate for the statements in the following list, which are all correct. Show why you have given a valid certificate in each case. (a) The polyhedral set X = {x ∈ R3 : x1 ≥ 1/3, x2 ≥ 1/3, x3 ≥ 1/3, ∑3 i=1 xi ≤ 1} 6= ∅. (b) The polyhedral set X = {x ∈ R3 : x1 ≥ 1/3, x2 ≥ 1/3, x3 ≥ 1/3, ∑3 i=1 xi ≤ 0.99} = ∅. (c) The linear inequality x1 + x2 ≤ 3/4 is valid for the polyhedral set X = {x ∈ R3 : x1 ≥ 1/3, x2 ≥ 1/3, x3 ≥ 1/3, ∑3 i=1 xi ≤ 1.05}. (d) The polyhedral set X = {x ∈ R3 : x1 ≥ 1/3, x2 ≥ 1/3, x3 ≥ 1/3, ∑3 i=1 xi ≤ 1} is bounded. (e) The polyhedral set X = {x ∈ R3 : x1 ≥ 1/3, x2 ≥ 1/3, ∑3 i=1 xi ≤ 1} is unbounded. 5 Question 4 (20 points) Consider a polyhedron X ..= conv(P) + cone(R) where P ..= {p1, . . . , pk} and R ..= {r1, . . . , r`}. Define S as the set of solutions α to the following system, where β¯ is a fixed value: αTp ≥ β¯ for all p ∈ P αTr ≥ 0 for all r ∈ R, and for a fixed v ∈ Rn, let S∗ ..= {α ∈ S : αTv < β¯}. Prove that S∗ 6= ∅ for (1) β¯ = 1 if and only if 0 /∈ X and v /∈ conv(P) + cone(P +R), (2) β¯ = −1 if and only if v /∈ conv(X ∪ {0}), and (3) β¯ = 0 if and only if v /∈ cone(P ∪R). Hint: Use an appropriate version of Farkas’s lemma or consider the problem minα{αTv : α ∈ S}. 6 Question Total points Your points 1 25 2 40 3 15 4 20 Total 100 7
欢迎咨询51作业君
