Computational Methods in Optimization

David Gleich

Purdue University

Spring 2025

Course number CS-52000

Tuesday, Thursday 10:30-11:45

Location Lawson 1106

Homework 5

Please answer the following questions in complete sentences in a clearly prepared manuscript and submit the solution by the due date on Gradescope.

Remember that this is a graduate class. There may be elements of the problem statements that require you to fill in appropriate assumptions. You are also responsible for determining what evidence to include. An answer alone is rarely sufficient, but neither is an overly verbose description required. Use your judgement to focus your discussion on the most interesting pieces. The answer to "should I include 'something' in my solution?" will almost always be: Yes, if you think it helps support your answer.

Problem 0: Homework checklist

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

• Make sure you have included your source-code and prepared your solution according to the most recent Edstem note on homework submissions.

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: $$\MIN{}{\sum_i \max (\va_i^T \vx - b_i, 0)}$$ 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: $$\MINone{\vx}{\vc^T \vx}{\mA \vx \ge \vb, \vx \ge 0} \qquad \text{ and } \qquad \MAXone{\vlambda}{\vb^T \vlambda}{\mA^T \vlambda \le \vc, \vlambda \ge 0}.$$

Problem 4: Geometry of LPs

(Griva, Sofer, and Nash, Problem 3.12) Consider the system of constraints $\mA \vx = \vb, \vx \ge 0$ with $$\mA = \bmat{ 1 & 2 & 3 & 1 & 0 & 0 \\ 4 & 5 & 6 & 0 & 1 & 0 \\ 7 & 8 & 9 & 0 & 0 & 1 }, \text{ and } \vb = \bmat{12 \\ 15 \\ 18}$$ 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.)