a logo for the course

Computational Methods in Optimization

David Gleich

Purdue University

Spring 2017

Course number CS-52000

Tuesday and Thursday, 1:30-2:45pm

Location Lawson B134

Homework 5

Please answer the following questions in complete sentences in submit the solution on Blackboard by the due date there.

Problem 0: List your collaborators.

Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale.

Problem 1: Steepest descent

(Nocedal and Wright, Exercise 3.6) Let's conclude with a quick problem to show that steepest descent can converge very rapidly! Consider the steepest descent method with exact line search for the function . Suppose that we know is parallel to an eigenvector of . Show that the method will converge in a single iteration.

Problem 2: LPs in Standard Form

Show that we can solve: by constructing an LP in standard form.

Problem 3: Duality

Show that the these two problems are dual by showing the equivalence of the KKT conditions:

Problem 4: Geometry of LPs

(Griva, Sofer, and Nash, Problem 3.12) Consider the system of constraints with Is a basic feasible point? Explain your answer precisely in terms of the definition.

Problem 5: Using the geometry

(Griva, Sofer, and Nash, Section 4.3, problem 3.13. Suppose that a linear program originally included a free variable where there were no upper-and-lower bounds on its values. As we described in class, this can be converted into a pair of variables and such that and is replaced with the difference . Prove that a basic feasible point can have only one of or different from zero. (Hint: this is basically a one-line proof once you see the right characterization. I would suggest trying an example.)