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 staff 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 , define 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 defined 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 satisfies 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 verifies 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 definition 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