Premium Essay

Submitted By rumana355

Words 1247

Pages 5

Words 1247

Pages 5

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...