Gradient Descent cho hàm 1 biến code C++ và Python

Problem: 

-Tìm x để f(x) min với f(x) = x^2 + 5*sin(x)

- Để giải bài toán này chúng ta có thể dùng phương pháp đã học ở cấp 3 đó là giải f'(x) = 0 và tìm cực tiểu tuy nhiên khá khó khăn 

- Một cách dễ hơn chính là dùng giải thuật Gradient Descent để có thể ước lượng được x.

Solution:

-Dự đoán một điểm x0

-Cập nhập x cho đến khi đạt điều kiện dừng

x = x0 - a * f'(x0)

x0 = x

-Điều kiện dừng:

+ Quá giới hạn số bước lặp

+ Giá trị tuyệt đối của Gradient nhỏ hơn một số gần bằng 0

+ Giá trị hàm của nghiệm tại 2 lần cập nhật không chênh lệch nhiều

Code C++:

#include<bits/stdc++.h>

#define X first

#define loop second

using namespace std;

double ff(double x){        //f'(x)

    return 2*x + 5*cos(x);

}

double f(double x){

    return pow(x, 2) + 5*sin(x);

}

typedef pair<double, int> ii;

ii GD(double alpha, double x0, double e=1e-3, int N= 1000){

   

    double x;

    for(int i=1; i<=N; i++){

       

        x = x0 - alpha * ff(x0);

        if (fabs(ff(x)) < e) return ii(x, i);

        x0 = x;

    }

    return ii(x0, N);

   

}

int main(){

    ii a= GD(0.1, -10);

    ii b= GD(0.1, 10);

    ii c= GD(0.5, 10);

    ii d= GD(0.01, 10);

   

    cout<<"Solution a.x = "<<a.X<<", f(a.X) = "<<f(a.X)<<", obtained after "<<a.loop<<" iterations\n";

    cout<<"Solution b.x = "<<b.X<<", f(b.X) = "<<f(b.X)<<", obtained after "<<b.loop<<" iterations\n";

    cout<<"Solution c.x = "<<c.X<<", f(c.X) = "<<f(c.X)<<", obtained after "<<c.loop<<" iterations\n";

    cout<<"Solution d.x = "<<d.X<<", f(d.X) = "<<f(d.X)<<", obtained after "<<d.loop<<" iterations\n";

}

Code Python:

from __future__ import division, print_function, unicode_literals

import math

import numpy as np

import matplotlib.pyplot as plt

def grad(x):

    return 2*x+ 5*np.cos(x)

def cost(x):

    return x**2 + 5*np.sin(x)

def myGD1(alpha, x0, gra = 1e-3, loop = 1000):

    x = [x0]

    for it in range(loop):

        x_new = x[-1] - alpha*grad(x[-1])

        if abs(grad(x_new)) < gra:

            break

        x.append(x_new)

    return (x, it)

if __name__ == '__main__':

    (x1, it1) = myGD1(.1, -10)

    (x2, it2) = myGD1(.1, 10)

    

    print('Solution x1 = %f, cost = %f, obtained after %d iterations'%(x1[-1], cost(x1[-1]), it1))

    print('Solution x2 = %f, cost = %f, obtained after %d iterations'%(x2[-1], cost(x2[-1]), it2))

    (x3, it3) = myGD1(.5, 10)

    print('Solution x3 = %f, cost = %f, obtained after %d iterations'%(x3[-1], cost(x3[-1]), it3))

    (x4, it4) = myGD1(.01, 10)

    print('Solution x4 = %f, cost = %f, obtained after %d iterations'%(x4[-1], cost(x4[-1]), it4))

    plt.plot(x1)

    plt.plot(x2)

    #plt.plot(x3)

    plt.plot(x4)

Output: 

Note: 

-Tốc độ hội tụ của Gradient Descent

+ Phụ thuộc vào điểm khởi tạo x0

+ Phụ thuộc vào chỉ số alpha