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