- This assignment is worth 5% of your final grade.
- Due: 2017-01-25, at the start of class.

### 1 Multiple linear regression

We can modify the example of §2.4 of Matoušek and Gärtner to allow any
number of *independent variables* x₁̣…xₖ and a single *dependent
variable* *y*. A given observation *i* then consists of a vector
*(x₁,…,xₖ,y)* and the corresponding error term εⁱ is defined by the
constraint *yⁱ=β₀+∑ⱼxⱼⁱβⱼ + εⁱ*

*1a* Formulate an LP for L₁ regression, i.e. minimize ∑|εᵢ|

*1b* Formulate an LP for L∞ regression, i.e. minimize maxᵢ |εᵢ|

*1c* Implement both your models using `glpsol`

. Give example data sets
with 2 independent variables that illustrate the difference in
behaviour of the two models.

### 2 Polygon containment

This question is related to the largest disk in a polygon example example.

*2a* Construct a glpsol model file that takes an *outer* polygon `P`

as
inequalities and an *inner* polygon `Q`

as vertices (with ```
(0,0) ∈
Q
```

), and finds the largest `r`

such that some translation of `rQ`

is
inside `P`

.

*2b* Use `glpsol`

Solve your model for some example polygons.

### 3. Absolute value

Give an LP to solve the following nonlinear optimization problem. Prove your LP is correct.

```
min maxᵢ | x_i |
Ax ≤ b
```

### What to hand in

For the theoretical parts, you can hand write your answers, or use a
computer. Email me a copy of your glpsol models and date files (.mod
and .dat files). Make sure you only email me plain text files, ready
to run. Print out a copy of the the input, and output from running the
models. You may find the linux command `script`

useful to generate a
transcript of your session. Feel free to write comments on the
printouts by hand. Your printouts should also note who you worked
with, if anyone.