UNB/ CS/ David Bremner/ teaching/ cs6375/ assignments/ CS6375 Assignment 1
• 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.