This assignment uses a linear programming routine to predict wine quality from chemical measurements.

sea-sunset-beach-couple-2145
Cover credit to Pixaboy

Note that the files can be downloaded here.

General:

  • Dataset (winesinfo.csv): In each line, the first 11 columns contain the results from various chemical tests performed on the wine, and the last column is the evaluation of how good the wine is (a score between 0 and 10).
  • Linear Model (Linear_Progamming): This matlab file contains a linear program described below.

Setup:

Consider a model based on Linear programming. For wine sample i, let us denote y_i \in \mathbb{R} by its score and \vec{x}_i \in \mathbb{R}^{11} by its chemical properties. We will here construct a linear model to predict y_i as a function of \vec{x}_i. That is, we want to find \vec{a} \in \mathbb{R}^{11} and b \in \mathbb{R} such that

    \[ y_i \simeq \vec{a}^T\vec{x}_i+b \]

The quality of the model will be evaluated using the \ell_1 norm, i.e., we want to find a solution to this optimization problem:

    \[ \min_{\vec{a}\in \mathbb{R}^{11},b \in \mathbb{R}} \frac{1}{n} \sum_{i=1}^n |y_i-\vec{a}^T\vec{x}_i-b| \]

Formulation:

Suppose that \vec{x}_i = [x_{i1}, \dots, x_{i11}]^T and a = [a_1, \dots, a_{11}]^T. Notice that we can define a new variable \vec{z} = [z_{1}, \dots, z_{n}]^T \in \mathbb{R}^{n} to represent the values of |y_i-\vec{a}^T\vec{x}_i-b| in the objective function. Therefore, the optimization program can be rewritten as below:

The objective function is

    \[ \min_{\vec{z} \in \mathbb{R}^n} \frac{1}{n} \sum_{i=1}^n z_i \]

with respect to the constraints:

    \begin{align*} z_i &\geq y_i-\sum_{j=1}^{11} x_{ij}a_j -b \\ z_i&\geq -\left(y_i-\sum_{j=1}^{11} x_{ij}a_j -b\right) \end{align*}

for 1 \leq i \leq n. Observe that we can also rewrite the constraints as

    \begin{align*} -\sum_{j=1}^{11} x_{ij}a_j -b -z_i &\leq -y_i \\ \sum_{j=1}^{11} x_{ij}a_j+b-z_i &\leq y_i \end{align*}

We can then define

    \[ \vec{d} = [a_1, \dots, a_{11},b,z_1,\dots, z_n]^T \in \mathbb{R}^{12+n} \]

Respectively, we can write

    \[ A = \begin{bmatrix} -x_{1,1} & \cdots & -x_{1,11} & -1 & -1 & 0 & 0 & \cdots & 0 \\ -x_{2,1} & \cdots & -x_{2,11} & -1 & 0 & -1 & 0 & \cdots & 0 \\ -x_{3,1} & \cdots & -x_{3,11} & -1 & 0 & 0 & -1 & \cdots & 0 \\ \vdots & \cdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ -x_{n,1} & \cdots & -x_{n,11} & -1 & 0 & 0 & 0 & \cdots & -1 \\ \hdashline x_{1,1} & \cdots & x_{1,11} & 1 & -1 & 0 & 0 & \cdots & 0 \\ x_{2,1} & \cdots & x_{2,11} & 1 & 0 & -1 & 0 & \cdots & 0 \\ x_{3,1} & \cdots & x_{3,11} & 1 & 0 & 0 & -1 & \cdots & 0 \\ \vdots & \cdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{n,1} & \cdots & x_{n,11} & 1 & 0 & 0 & 0 & \cdots & -1 \\ \end{bmatrix} \]

and the dashed line separates the two “types” of inequality constraints. Therefore, we can write the constraints as

    \[ A\vec{d} \leq \vec{b} \]

where

    \[ \vec{b} = [-y_1, \dots, -y_n, y_1,\dots, y_n]^T \]

The objective function then can be written as

    \[ \vec{c}^T\vec{b} = \frac{1}{n}\sum_{i = 1}^n z_i = \sum_{i = 1}^n \frac{1}{n} z_i \]

where

    \[ \vec{c} = \left[\underbrace{0,\ \cdots, 0}_{\text{12 times}},\ \underbrace{\frac{1}{n},\ \cdots, \frac{1}{n}}_{\text{$n$ times}}\right]^T \]

Therefore, from the discussions above, we can rewrite the original system as

    \begin{align*} \min_{\vec{d} \in \mathbb{R}^{12+n}} \quad &\vec{c}^T \vec{d} \\ \text{subject to} \quad &A\vec{d} \leq \vec{b} \\ \end{align*}

where

    \begin{align*} \vec{c} &= \left[\underbrace{0,\ \cdots, 0}_{\text{12 times}},\ \underbrace{\frac{1}{n},\ \cdots, \frac{1}{n}}_{\text{$n$ times}}\right]^T \in \mathbb{R}^{12 + n} \\ \vec{d} &= [a_1, \dots, a_{11},b,z_1,\dots, z_n]^T \in \mathbb{R}^{12+n} \\ A &= \begin{bmatrix} -x_{1,1} & \cdots & -x_{1,11} & -1 & -1 & 0 & 0 & \cdots & 0 \\ -x_{2,1} & \cdots & -x_{2,11} & -1 & 0 & -1 & 0 & \cdots & 0 \\ -x_{3,1} & \cdots & -x_{3,11} & -1 & 0 & 0 & -1 & \cdots & 0 \\ \vdots & \cdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ -x_{n,1} & \cdots & -x_{n,11} & -1 & 0 & 0 & 0 & \cdots & -1 \\ \hdashline x_{1,1} & \cdots & x_{1,11} & 1 & -1 & 0 & 0 & \cdots & 0 \\ x_{2,1} & \cdots & x_{2,11} & 1 & 0 & -1 & 0 & \cdots & 0 \\ x_{3,1} & \cdots & x_{3,11} & 1 & 0 & 0 & -1 & \cdots & 0 \\ \vdots & \cdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{n,1} & \cdots & x_{n,11} & 1 & 0 & 0 & 0 & \cdots & -1 \\ \end{bmatrix}\in \mathbb{R}^{2n \times (12+n)} \\ \vec{b} &= [-y_1, \dots, -y_n, y_1,\dots, y_n]^T \in \mathbb{R}^{2n} \end{align*}

The formation is exactly the same as stated above in Matlab. One can check and test the files from here.
Q3
The result is displayed in the command window. It says that the optimal value is 0.4937, which is an error within an acceptable range.

Leave a Reply