
# 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 $f(\vx) = (1/2) \vx^T \mQ \vx - \vx^T \vb$. Suppose that we know $\vx_0 - \vx^*$ is parallel to an eigenvector of $\mQ$. 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 $\mA \vx = \vb, \vx \ge 0$ with Is $\vx = \bmat{1 & 1 & 1 & 0 & 0 & 0}^T$ 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 $x_i$ 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 $x_i^+$ and $x_i^-$ such that $x_i^+, x_i^- \ge 0$ and $x_i$ is replaced with the difference $x_i^+ - x_i^-$. Prove that a basic feasible point can have only one of $x_i^+$ or $x_i^-$ different from zero. (Hint: this is basically a one-line proof once you see the right characterization. I would suggest trying an example.)