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