gradient_d

from sympy import *
import sympy as sym
import math

x, y, t = sym.symbols('x y t')


def interval(func):
    delta = 10 ** (-3)
    x0 = 0
    k = 0
    f1 = func.subs(t, x0)
    f2 = func.subs(t, (x0 + delta))

    if f1 >= f2:
        k += 1
        xi = x0 + delta
        h = delta
    else:
        xi = x0 - delta
        h = -delta
    k += 1
    xk = x0
    while (True):
        h *= 2
        xj = xi + h
        f3 = func.subs(t, xi)
        f4 = func.subs(t, xj)
        if f3 > f4:
            k += 1
            xk = xi
            xi += h
            continue
        else:
            if (xk < xj):
                return (xk, xj)
            else:
                return (xj, xk)
            break


def golden_ratio(func):
    inter = interval(func)
    a = inter[0]
    b = inter[1]
    eps = 10 ** (-10)
    coef1 = (3 - math.sqrt(5)) / 2
    coef2 = (math.sqrt(5) - 1) / 2
    i = 1
    x1 = a + coef1 * (b - a)
    x2 = a + coef2 * (b - a)
    f1 = func.subs(t, x1)
    f2 = func.subs(t, x2)
    while True:
        if f1 <= f2:
            b = x2
            x2 = x1
            f2 = f1
            k = 1
        else:
            a = x1
            x1 = x2
            f1 = f2
            k = 2
        if abs(a - b) < eps:
            return (a + b) / 2
        if k == 1:
            x1 = a + coef1 * (b - a)
            f1 = func.subs(t, x1)
        else:
            x2 = a + coef2 * (b - a)
            f2 = func.subs(t, x2)
        i += 1


def gradient_descent(func):
    # v-начальная точка
    v = (0, 4)
    eps1 = 10 ** (-10)
    eps2 = 10 ** (-10)
    i = 0
    # нахождение градиента и подстановка v
    gradient = ((diff(func, x)).subs({x: v[0], y: v[1]}), (diff(func, y)).subs({x: v[0], y: v[1]}))
    norma_grad = (gradient[0] ** 2 + gradient[1] ** 2) ** 0.5
    while norma_grad > eps1:
        # expand раскрывает скобки
        phi = expand(func.subs({x: v[0] - gradient[0] * t, y: v[1] - gradient[1] * t}))
        # условие безусловного экстремума, нахождение t
        t_res = golden_ratio(phi)
        # находим следующее приближение
        x_next = v[0] - gradient[0] * t_res
        y_next = v[1] - gradient[1] * t_res
        v_next = (x_next, y_next)
        n1 = ((v_next[0] - v[0]) ** 2 + (v_next[1] - v[1]) ** 2) ** 0.5
        n2 = abs(func.subs({x: v_next[0], y: v_next[1]}) - func.subs({x: v[0], y: v[1]}))
        if n1 > eps2 and n2 > eps2:
            v = v_next
            gradient = ((diff(func, x)).subs({x: v[0], y: v[1]}), (diff(func, y)).subs({x: v[0], y: v[1]}))
            norma_grad = (gradient[0] ** 2 + gradient[1] ** 2) ** 0.5
            i = i + 1

        else:
            break
    #print('min F=', "%.5f" % func.subs({x: v_next[0], y: v_next[1]}), 'в точке', v_next)
    return v_next