def DescentMethod(f, x0, epsilon, **kwargs):
x = x0
while StopCriterion(x, f, **kwargs) > epsilon:
h = ComputeDescentDirection(x, f, **kwargs)
alpha = SelectStepSize(x, h, f, **kwargs)
x = x + alpha * h
return x
Рассмотрим линейную аппроксимацию дифференцируемой функции $f$ вдоль некоторого направления убывания $h, \|h\|_2 = 1$:
$$ f(x + \alpha h) = f(x) + \alpha \langle f'(x), h \rangle + o(\alpha) $$Из условия убывания
$$ f(x) + \alpha \langle f'(x), h \rangle + o(\alpha) < f(x) $$и переходя к пределу при $\alpha \rightarrow 0$:
$$ \langle f'(x), h \rangle \leq 0 $$Также из неравенства Коши-Буняковского-Шварца
$$ \langle f'(x), h \rangle \geq -\| f'(x) \|_2 \| h \|_2 = -\| f'(x) \|_2 $$Таким образом, направление антиградиента
$$ h = -\dfrac{f'(x)}{\|f'(x)\|_2} $$даёт направление наискорейшего локального убывания функции$~f$.
В итоге метод имеет вид
$$ x_{k+1} = x_k - \alpha f'(x_k) $$Рассмотрим обыкновенное диференциальное уравнение вида:
$$ \frac{dx}{dt} = -f'(x(t)) $$и дискретизуем его на равномерной сетке с шагом $\alpha$:
$$ \frac{x_{k+1} - x_k}{\alpha} = -f'(x_k), $$где $x_k \equiv x(t_k)$ и $\alpha = t_{k+1} - t_k$ - шаг сетки.
Отсюда получаем выражение для $x_{k+1}$
$$ x_{k+1} = x_k - \alpha f'(x_k), $$которое в точности совпадает с выражением для градиентного спуска.
Такая схема называется явной или прямой схемой Эйлера.
Вопрос: какая схема называется неявной или обратной?
Глобальная оценка сверху на функцию $f$ в точке $x_k$:
$$ f(y) \leq f(x_k) + \langle f'(x_k), y - x_k \rangle + \frac{L}{2} \|y - x_k \|_2^2 = g(y), $$где $\lambda_{\max}(f''(x)) \leq L$ для всех допустимых $x$.
Справа — квадратичная форма, точка минимума которой имеет аналитическое выражение:
\begin{align*} & g'(y^*) = 0 \\ & f'(x_k) + L (y^* - x_k) = 0 \\ & y^* = x_k - \frac{1}{L}f'(x_k) = x_{k+1} \end{align*}Этот способ позволяет оценить значение шага как $\frac{1}{L}$. Однако часто константа $L$ неизвестна.
Минимизация линейной аппроксимации в шаре радиуса $r$ с центром в точке $x_k$ \begin{align*} & \min \; f(x_k) + \langle f'(x_k), x - x_k \rangle\\ \text{s.t. } & \| x - x_k \|^2_2 \leq r^2 \end{align*}
Используя метод множителей Лагранжа и условия ККТ, получим
$$ x_{k+1} = x_k - \frac{1}{2\lambda} f'(x_k), $$где $\lambda$ — множитель Лагранжа, и
$$ \lambda = \frac{\| f'(x_k)\|_2}{2r} $$Вопрос: как выбрать $r$?
Вопрос: какое соотношение между константой Липшица $L$ градиента $f'(x_k)$ из способа 4 и $\lambda$?
def GradientDescentMethod(f, x0, epsilon, **kwargs):
x = x0
while StopCriterion(x, f, **kwargs) > epsilon:
h = ComputeGradient(x, f, **kwargs)
alpha = SelectStepSize(x, h, f, **kwargs)
x = x - alpha * h
return x
Список подходов:
Требование достаточного убывания, требование существенного убывания и условие кривизны: для некоторых $\beta_1, \beta_2$, таких что $0 < \beta_1 < \beta_2 < 1$ найти $x_{k+1}$ такую что
Обычно коэффициенты выбирают так: $\beta_1 \in (0, 0.3)$, а $\beta_2 \in (0.9, 1)$
Требование существенного убывания и условие кривизны обеспечивают убывание функции по выбранному направлению $h_k$. Обычно выбирают одно из них.
In [1]:
%matplotlib notebook
import matplotlib.pyplot as plt
plt.rc("text", usetex=True)
import ipywidgets as ipywidg
import numpy as np
import liboptpy.unconstr_solvers as methods
import liboptpy.step_size as ss
from tqdm import tqdm
In [2]:
f = lambda x: np.power(x, 2)
gradf = lambda x: 2 * x
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
def update(x0, step):
gd = methods.fo.GradientDescent(f, gradf, ss.ConstantStepSize(step))
_ = gd.solve(np.array([x0]), max_iter=10)
x_hist = gd.get_convergence()
x = np.linspace(-5, 5)
ax.clear()
ax.plot(x, f(x), color="r", label="$f(x) = x^2$")
y_hist = np.array([f(x) for x in x_hist])
x_hist = np.array(x_hist)
plt.quiver(x_hist[:-1], y_hist[:-1], x_hist[1:]-x_hist[:-1], y_hist[1:]-y_hist[:-1],
scale_units='xy', angles='xy', scale=1, width=0.005, color="green", label="Descent path")
ax.legend()
fig.canvas.draw()
step_slider = ipywidg.FloatSlider(value=0.8, min=0, max=1.2, step=0.1, description="Step")
x0_slider = ipywidg.FloatSlider(value=1.5, min=-4, max=4, step=0.1, description="Initial point")
_ = ipywidg.interact(update, x0=x0_slider, step=step_slider)
In [3]:
def plot_alpha(f, grad, x, h, alphas, beta1, beta2):
df = np.zeros_like(alphas)
for i, alpha in enumerate(alphas):
df[i] = f(x + alpha * h)
upper_bound = f(x) + beta1 * alphas * grad(x) * h
lower_bound = f(x) + beta2 * alphas * grad(x) * h
plt.plot(alphas, df, label=r"$f(x + \alpha h)$")
plt.plot(alphas, upper_bound, label="Upper bound")
plt.plot(alphas, lower_bound, label="Lower bound")
plt.xlabel(r"$\alpha$", fontsize=18)
plt.legend(loc="best", fontsize=18)
In [5]:
f = lambda x: x**2
grad = lambda x: 2 * x
beta1 = 0.1
beta2 = 0.5
x0 = 0.5
plot_alpha(f, grad, x0, -grad(x0), np.linspace(1e-3, 1.01, 10), beta1, beta2)
In [24]:
x_range = np.linspace(1e-10, 4)
plt.plot(x_range, x_range * np.log(x_range))
Out[24]:
In [13]:
x0 = 1
f = lambda x: x * np.log(x)
grad = lambda x: np.log(x) + 1
beta1 = 0.3
beta2 = 0.7
plot_alpha(f, grad, x0, -grad(x0), np.linspace(1e-3, 0.9, 10), beta1, beta2)
def SelectStepSize(x, f, h, rho, alpha0, beta1, beta2):
# 0 < rho < 1
# alpha0 - initial guess of step size
# beta1 and beta2 - constants from conditions
alpha = alpha0
# Check violating sufficient decrease and curvature conditions
while (f(x - alpha * h) >= f(x) + beta1 * alpha grad_f(x_k).dot(h)) and
(grad_f(x - alpha * h).dot(h) <= beta2 * grad_f(x_k).dot(h)):
alpha *= rho
return alpha
Теорема 1. Пусть
Тогда для градиентного метода выполнено:
$$ \lim\limits_{k \to \infty} f'(x_k) = 0, $$а функция монотонно убывает $f(x_{k+1}) < f(x_k)$.
Теорема 2. Пусть
Тогда
$$ f'(x_k) \to 0, \; k \to \infty \qquad x_{k_i} \to x^* $$Теорема 3. Пусть
Тогда
$$ f(x_k) - f^* \leq \dfrac{2L \| x_0 - x^*\|^2_2}{k+4} $$Теорема 4. Пусть
Тогда градиентный метод сходится к единственной точке глобального минимума $x^*$ с линейной скоростью:
$$ \| x_k - x^* \|_2 \leq cq^k, \qquad 0 \leq q < 1 $$Теорема 5. Пусть
Тогда для градиентного метода выполнено:
$$ \| x_k - x^* \|_2 \leq \left( \dfrac{M - 1}{M + 1} \right)^k \|x_0 - x^*\|_2 \qquad f(x_k) - f^* \leq \dfrac{L}{2} \left( \dfrac{M - 1}{M + 1} \right)^{2k} \| x_0 - x^*\|^2_2, $$где $M = \frac{L}{\mu}$
Теорема 6. Пусть
Тогда
$$ \| x_k - x^*\|_2 \leq \|x_0 - x^*\|_2 q^k, \qquad q = \max(|1 - \alpha l|, |1 - \alpha L|) < 1 $$и минимальное $q^* = \dfrac{L - \mu}{L + \mu}$ при $\alpha^* = \dfrac{2}{L + \mu}$
Из Теорем 5 и 6 имеем $$ q^* = \dfrac{L - \mu}{L + \mu} = \dfrac{L/\mu - 1}{L/\mu + 1} = \dfrac{M - 1}{M + 1}, $$ где $M$ - оценка числа обусловленности $f''(x)$.
Вопрос: что такое число обусловленности матрицы?
Вопрос: какая геометрия у этого требования?
Мораль: необходимо сделать оценку $M$ как можно ближе к 1!
О том, как это сделать, Вам будет предложено подумать в домашнем задании :)
Обратите внимание, что ни в одной из теорем приведённых выше не было условий на начальное приближение $x_0$!
Поиск $\alpha_k$:
In [5]:
def GradientDescent(f, gradf, x0, epsilon, num_iter, line_search,
disp=False, callback=None, **kwargs):
x = x0.copy()
iteration = 0
opt_arg = {"f": f, "grad_f": gradf}
for key in kwargs:
opt_arg[key] = kwargs[key]
while True:
gradient = gradf(x)
alpha = line_search(x, -gradient, **opt_arg)
x = x - alpha * gradient
if callback is not None:
callback(x)
iteration += 1
if disp:
print("Current function val =", f(x))
print("Current gradient norm = ", np.linalg.norm(gradf(x)))
if np.linalg.norm(gradf(x)) < epsilon:
break
if iteration >= num_iter:
break
res = {"x": x, "num_iter": iteration, "tol": np.linalg.norm(gradf(x))}
return res
Реализации различных способов выбора шага приведены тут
In [25]:
def my_f(x, A):
return 0.5 * x.dot(A.dot(x))
def my_gradf(x, A):
return A.dot(x)
In [26]:
plt.rc("text", usetex=True)
gammas = [0.1, 0.5, 1, 2, 3, 4, 5, 10, 20, 50, 100, 1000, 5000, 10000]
# gammas = [1]
num_iter_converg = []
for g in gammas:
A = np.array([[1, 0],
[0, g]], dtype=np.float64)
f = lambda x: my_f(x, A)
gradf = lambda x: my_gradf(x, A)
# x0 = np.random.rand(A.shape[0])
# x0 = np.sort(x0)
# x0 = x0[::-1]
x0 = np.array([g, 1], dtype=np.float64)
# print x0[1] / x0[0]
gd = methods.fo.GradientDescent(f, gradf, ss.ExactLineSearch4Quad(A))
x = gd.solve(x0, tol=1e-7, max_iter=100)
num_iter_converg.append(len(gd.get_convergence()))
plt.figure(figsize=(8, 6))
plt.loglog(gammas, num_iter_converg)
plt.xticks(fontsize = 20)
plt.yticks(fontsize = 20)
plt.xlabel(r"$\gamma$", fontsize=20)
plt.ylabel(r"Number of iterations with $\varepsilon = 10^{-7}$", fontsize=20)
Out[26]:
Пусть $A \in \mathbb{R}^{m \times n}$. Рассмотрим систему линейных неравенств: $Ax \leq 1$ при условии $|x_i| \leq 1$ для всех $i$.
Определение. Аналитическим центром системы неравенств $Ax \leq 1$ при условии $|x_i| \leq 1$ является решение задачи $$ f(x) = - \sum_{i=1}^m \log(1 - a_i^{\top}x) - \sum_{i = 1}^n \log (1 - x^2_i) \to \min_x $$ $$ f'(x) - ? $$
In [27]:
n = 100
m = 200
x0 = np.zeros(n)
A = np.random.rand(n, m)
In [28]:
import cvxpy as cvx
print(cvx.installed_solvers())
x = cvx.Variable(n)
obj = cvx.Minimize(cvx.sum(-cvx.log(1 - A.T * x)) -
cvx.sum(cvx.log(1 - cvx.square(x))))
prob = cvx.Problem(obj)
prob.solve(solver="SCS", verbose=True)
x = x.value
print("Optimal value =", prob.value)
In [29]:
f = lambda x: -np.sum(np.log(1 - A.T.dot(x))) - np.sum(np.log(1 - x*x))
grad_f = lambda x: np.sum(A.dot(np.diagflat(1 / (1 - A.T.dot(x)))), \
axis=1) + 2 * x / (1 - np.power(x, 2))
In [30]:
gd = methods.fo.GradientDescent(f, grad_f, ss.Backtracking("Armijo", rho=0.7, beta=0.1, init_alpha=1.))
x = gd.solve(x0, tol=1e-5, max_iter=100, disp=True)
x_conv = gd.get_convergence()
grad_conv = [np.linalg.norm(grad_f(x)) for x in x_conv]
plt.figure(figsize=(8,6))
plt.semilogy(grad_conv, label=r"$\| f'(x_k) \|_2$")
plt.semilogy([np.linalg.norm(x - np.array(x_k)) for x_k in x_conv], label=r"$\|x_k - x^*\|_2$")
plt.semilogy([np.linalg.norm(prob.value - f(np.array(x_k))) for x_k in x_conv], label=r"$\|f(x_k) - f^*\|_2$")
plt.semilogy([np.linalg.norm(np.array(x_conv[i]) - np.array(x_conv[i+1])) for i in range(len(x_conv) - 1)], label=r"$\|x_k - x_{k+1}\|_2$")
plt.semilogy([np.linalg.norm(f(np.array(x_conv[i])) - f(np.array(x_conv[i+1]))) for i in range(len(x_conv) - 1)], label=r"$\|f(x_k) - f(x_{k+1})\|_2$")
plt.xlabel(r"Number of iteration, $k$", fontsize=20)
plt.ylabel(r"Convergence rate", fontsize=20)
plt.xticks(fontsize = 20)
plt.yticks(fontsize = 20)
plt.legend(loc="best", fontsize=20)
plt.tight_layout()
In [31]:
rhos = [0.1 + i * 0.1 for i in range(9)]
conv_iter = []
hist_x = []
callback = lambda x: my_callback(x, hist_x)
for rho in rhos:
gd = methods.fo.GradientDescent(f, grad_f, ss.Backtracking(rule_type="Armijo", beta=0.1, rho=rho, init_alpha=1.))
x = gd.solve(x0, tol=1e-4, max_iter=100)
conv_iter.append(len(gd.get_convergence()))
# plt.semilogy(range(1, len(grad_norm) + 1), grad_norm, label=r"$\rho$ = " + str(rho))
hist_x = []
plt.figure(figsize=(8, 6))
plt.plot(rhos, conv_iter)
plt.xlabel(r"Decay factor, $\rho$", fontsize=18)
plt.ylabel(r"Number of iterations for convergence", fontsize=16)
plt.xticks(fontsize = 18)
_ = plt.yticks(fontsize = 20)
In [32]:
betas = [0.05 + i * 0.05 for i in range(8)]
hist_x = []
num_iter_conv = []
plt.figure(figsize=(8, 6))
for beta in betas:
gd = methods.fo.GradientDescent(f, grad_f, ss.Backtracking(rule_type="Armijo", beta=beta, rho=0.6, init_alpha=1.))
x = gd.solve(x0, tol=1e-4, max_iter=100)
num_iter_conv.append(len(gd.get_convergence()))
hist_x = []
plt.plot(betas, num_iter_conv)
plt.xlabel(r"$\beta$", fontsize=20)
plt.ylabel(r"Number of iterations for convergence", fontsize=18)
plt.xticks(fontsize = 20)
_ = plt.yticks(fontsize = 20)
In [33]:
rhos = [0.1 + i * 0.1 for i in range(9)]
conv_time = []
hist_x = []
callback = lambda x: my_callback(x, hist_x)
for rho in tqdm(rhos):
gd = methods.fo.GradientDescent(f, grad_f, ss.Backtracking(rule_type="Armijo", beta=0.1, rho=rho, init_alpha=1.))
current_time = %timeit -o -q gd.solve(x0, tol=1e-4, max_iter=100)
conv_time.append(current_time.average)
# plt.semilogy(range(1, len(grad_norm) + 1), grad_norm, label=r"$\rho$ = " + str(rho))
hist_x = []
In [34]:
plt.figure(figsize=(8, 6))
plt.plot(rhos, conv_time)
plt.xlabel(r"Decay factor, $\rho$", fontsize=18)
plt.ylabel(r"Convergence time, s.", fontsize=16)
plt.xticks(fontsize = 18)
_ = plt.yticks(fontsize = 20)
Pro
Contra
Следующий семинар: некоторые расширения и модификации градиентного спуска...