Project Description:

In this project, some optimization method will be studied such as Gradient, newton, quasi-newton etc. First the random data will be generated from a predefined linear regression model where $5\leq \beta_i \leq5$ and $i = 0,...,K$ with K = 120 independent variables $X = (X_1,X_2,...,X_K)$ and n = 1000 observations. In the project, it is seeked to adjust a multiple linear regression model to explain variable Y as a function of the other variables X, i.e.,($ Y = \beta 'X + \epsilon $) by using "Ridge Regression":

$$ \min_{\beta} ||y-X\beta||^2_2 + \rho ||\beta||^2_2$$

where $\rho$ is a parameter and consider it fixed to a given value $\rho = 1$

Visualizing some variables of the random data

a) Estimating the value of the regression coefficients by implementing the analytical solution

For ridge regression, there exists an analytical solution. \ The exact solution is: $\beta^*=(X^T X + \rho I)^{-1}X^T y$

b) Estimating the value of the regression coefficients by using the function minimize from the Python module Scipy.optimize

Defining ridge regression, gradient and hess of ridge regression formulas and creating functions

In order to try different solvers for the minimization problem, first ridge regression, gradient of ridge and hess of ridge functions should be defined:

As the ridge regression open formula is $$ \min_{\beta} (Y-\beta^TX)^T(Y-\beta^TX) + \rho\beta^T\beta$$ Then to find the gradient of the ridge regression, The derivation of the formula is: $$ −2X^T(Y−\beta^TX) + 2\rho\beta $$ And, the hess of the ridge regression will be: $$ 2X^TX + 2\rho$$

Trying different methods for minimizing ridge problem

In this section, six methods will be tried to minimize the ridge problem. First, all methods are written into a list called methods, and then with for loop, each method has been tried, respectively. As each method has different type of paramaters in minimize function such as jac or hess, if loop has been created to restrict this situation. \ As a result, the methods which had the minimum error and minimum objective function have been printed.

Comparison of each method performance

Values of the ridge regression coefficients with the BFGS method that had minimum error

After trying different methods, BFGS method which is one of the quasi-newton methods had the least error rate, therefore, betas that estimated with this method are displaying in this section.

c) Estimating the value of the regression coefficients by implementing:

1. Gradient Method

Gradient Method Description and Formula

In this method, from an initial iterate $x_0$ descent directions which represents $p_k=-\nabla f(x_k)$ are computed. Movement of the gradient is following: $$x_{k+1} = x_k + \alpha_k\ p_k$$ Number of k iterations take place until the algortihm converges to a local solution

Plotting Objective Function and Tolerance evaluations through iterations

As seen in the visuals, OF and tolerance values tend to decrease through iterations. For OF, the function decreases sharply at the beginning. For tolerance values, there is a sharp decrease until the algorithm reaches to 15000 iterations. Then the tolerance values are stabil.

Implementing Armijo Rule to adjust alpha for Gradient Descent
image.png

The ArmijoLineSearch function has been written according to the above formula's left hand and right hand sides. When this equation can NOT be obtained, the function reaches the optimal alpha value and the while loop stops.

Plotting Alpha evaluations through iterations

2. Newton's Method

Newton's Method Description and Formula

In this method, again, from an initial iterate $x_0$, descent direction which is $p_k=-(\nabla^2 f(x_k))^{-1} \nabla f(x_k)$ are computed whenever $\nabla^2 f(x_k)$ is nonsingular. In each iteration k, the movement of the method is following until it convergences to a local solution. $$x_{k+1} = x_k + \alpha_k\ p_k$$

Plotting Objective Function and Tolerance evaluations through iterations

As seen from graphs that OF has decreased sharply at the beginnning and the tolerance of each iteration has decreased continuesly until the end of iterations.

Implementing Armijo Rule to adjust alpha for Newton method

3. Quasi-Newton method

Quasi-Newton method Description and Formula

Quasi-Newton Formula
image.png

In this step, BFGS update rule has been examined.

d) Estimating the value of the regression coefficients by implementing:

1.Coordinate gradient method

Coordinated Descent (CD) Formula
image.png

In this step, the coordinated descent function has been created by using the above formula.

2.Mini-batch gradient method

In this step the effects of the mini-batch size in algorithm performance (number of iterations and computational time needed to reach a pre-specified tolerance limit) has been studied.

Mini-batch gradient descent formula
image.png

First, "mini_batch" function has been created in order to create batch samples in X and Y.

In this part, 5 different batch size has been tried. (30,50,300,500,1000).

3. Mini-batch gradient with momentum

In this step, the momentum(v) has been implemented to the previously obtained mini-batch algortihm. Here, apart from alpha parameter (learning rate), there is also beta parameter which is similar to acceleration in mechanics.

f) Consider the constrained problem:

$$ \min_{\beta} ||y-X\beta||^2_2$$$$ st: \sum_{i=1}^{K} \beta_{i} = 1 $$

Estimate the optimal value of the regression coefficients in (1) by implementing a penalization algorithm

Here the penalization which is $\sum_{i=1}^{K} \beta_{i} = 1 $ added to regression function. After creating the penalization function, the gradient of the function which is the derivative of the penalization function has been created in order to minimize with BFGS method.