Business and Management
Submitted By rumana355
Assignment 1–Advanced Operations Research - MATH 3010 Posted 23 August 2014 Due date: 19 September 2014, by 5pm
In all the statements below, the notation, as well as references to page numbers, equations, etc, are as in the textbook Primal-dual interior-point methods, by Wright, Stephen, which is available online for UniSA staﬀ and students. All relevant chapters of the textbook are also available in the webpage of the course. For solving this assignment, you need to read the handwritten Lecture Notes posted in the web and the material in the book up to Chapter 4, page 70. Question 1 (2+2+3+3+3+3=16 points) Fix A ∈ Rm×n , b ∈ Rm , and c ∈ Rn . (a) Write down the KKT conditions for the following problem, on the variable x ∈ Rn : min cT x Ax = b ; x ≥ 0. (1)
(b) Write down the KKT conditions for the following problem, on the variable (λ, s) ∈ Rm+n AT λ max λT b + s = c; s ≥ 0, (2)
Show that both the KKT conditions associated with both problems are identical. (c) Given x, s ∈ Rn , deﬁne the matrices X = diag(x1 , . . . , xn ), S = diag(s1 , . . . , sn ), and the vector e = (1, . . . , 1)T ∈ Rn . Let F : R2n+m → R2n+m be deﬁned as T A λ+s−c . Ax − b F (x, λ, s) = XS e Show that a solution of F (x, λ, s) = 0 does not necessarily satisfy the KKT conditions of part (a) (or part (b)). Prove that, on the other hand, every vector (x, λ, s) that satisﬁes the KKT conditions must satisty F (x, λ, s) = 0. (d) Recall that the search direction (∆x, ∆λ, ∆s) generated by a Newton step for F (x, λ, s) = 0 veriﬁes the system ∆x J(x, λ, s) ∆λ = −F (x, λ, s), (3) ∆s where J(x, λ, s) is the Jacobian of F at (x, λ, s). Using the deﬁnition of F , compute J(x, λ, s) and write down the system (9) in terms of (x, λ, s) and A. (e) Show that, if F (x, λ, s) = 0, then we cannot have (x, s) > 0. (f) Modify the KKT conditions in part (a) so that the solution of the system is...