Computational Methods in Optimization

David Gleich

Purdue University

Spring 2023

Course number CS-52000

Monday, Wednesday, Friday, 1:30-2:20pm

Location Lawson 1106

Homework 6

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 Piazza note on homework submissions.

Problem 1

Using the codes from class (or your own implementations in another language) illustrate the behavior of the simplex method on the LP from problem 13.9 in Nocedal and Wright: $$\MINthree{}{-5 x_1 - x_2}{x_1 + x_2 \le 5}{2 x_1 + (1/2) x_2 \le 8 }{ \vx \ge 0}$$ starting at $[0,0]^T$ after converting the problem to standard form.

Use your judgement in reporting the behavior of the method.

Problem 2

Using the codes from class (or your own implementations in another language) illustrate the behavior of the simplex method on the LP. $$\MINthree{}{-x_1 - 3x_2}{-2x_1 + x_2 \le 2}{-x_1 + 2x_2 \le 7 }{ \vx \ge 0}$$ starting at $[0,0]^T$ after converting the problem to standard form.

Use your judgement in reporting the behavior of the method.

Problem 3

Using the codes from class (or your own implementations in another language) illustrate the behavior of the simplex method on the LP. $$\begin{array}{ll} \displaystyle\minimize & -3/4 x_1 + 150 x_2 -1/50 x_3 +6 x_4 \\ \subjectto & 1/4 x_1 - 60 x_2 -1/25 x_3 + 9x_4 \le 0 \\ & 1/2 x_1 -90 x_2 + 1/50 x_3 + 3 x_4 \le 0 \\ & x_3 \le 1 \\ & \vx \ge 0 \end{array}$$ starting at $[0,0,0,0]^T$ after converting the problem to standard form.

Use your judgement in reporting the behavior of the method.

Problem 4

Show that if we have: $$\begin{array}{ll} \displaystyle\minimize & \vc^T \vx \\ \subjectto & \mA \vx \le \vb \\ & \vx \ge 0 \\ \end{array}$$ and $\vb \ge 0$, then $\vx = 0$ is always a vertex after converting to standard form.

Problem 5

The goal here is to develop an LP-based solver for a 1-norm regression problem. Consider the problem: $$\MIN{\vx}{\normof{\mA \vx - \vb}_1 = \sum_{i} |\va_i^T \vx - b_i| },$$ where $\va_i^T$ is the $i$th row of $\mA$. This can be converted into a linear program and solved via the simplex method. Compute the solution for the sports ranking problem