2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Метод наискорейшего спуска.
Сообщение27.04.2014, 08:39 
Поскольку сходящаяся минимизирующая последовательность позволяет найти точку минимума функции с произвольной наперед заданной точностью, то следует рассмотреть вопрос о построении такой последовательности.

Поставим следующую задачу: имея точку $x^k \in \mathbb{R}^n $ построить точку $x^{k+1} \in \mathbb{R}^n$
такую, чтобы выполнялось соотношение:
$$ f(x^{k+1}) = x^k + \mu q, q \neq  0$$,
где $q$ - заданный вектор из $\mathbb{R}^n$, называемый направлением спуска.
Параметр $\mu$ (шаг метода) определяется из условия минимума функции $f(\cdot)$.
Имеем:
$$ f(x^{k+1}) = f(x^k + \mu q) \equiv \varphi (\mu)  = \varphi(0) + \mu \dot \varphi(0) + \frac 1 2 \mu ^2 \ddot \varphi(0), \dot \varphi = \frac {d\varphi} {d\mu}  $$
где
$$ \varphi(0) = f(x^k), \dot \varphi(0) = q^T (Ax^k + b), \ddot \varphi(0) = q^TAq$$

В общем то вопрос в том, как так вывели $\dot \varphi(0), \ddot \varphi(0)$

-- 27.04.2014, 11:26 --

Это квадратичная функция, которая дана изначально $$ f(x) = \frac 1 2 x^TAx + x^Tb $$

-- 27.04.2014, 11:30 --

Можно так расписать, и попробовать взять производную по $\mu$ $$ f(x^k + \mu q) = \frac 1 2 (x^k + \mu q)^TA(x^k+\mu q) + (x^k+\mu q)^Tb = \varphi(\mu) $$

 
 
 
 Re: Метод наискорейшего спуска.
Сообщение27.04.2014, 08:57 
Ну скажем вот это: $$ \dot \varphi(0) = q^T (Ax^k + b)$$ -- просто стандартное правило дифференцирования сложной функции. В скобках стоит производная $f$ по своему непосредственному аргументу (т.е. градиент), и она умножается на производную того аргумента по параметру $\mu$ (т.е. на вектор $q$). Правда, с транспонированиями лучше бы наоборот, т.к. градиент -- это всё-таки строка. Но тут уж кому арбуз, а кому свиной хрящик.

 
 
 
 Re: Метод наискорейшего спуска.
Сообщение27.04.2014, 09:04 
Ну более менее понятно. Иногда операции транспонирования смущают :oops: :oops: :oops:

далее там написано.
Поскольку $\varphi(\mu)$ является квадратным трехчленом относительно $\mu$ с положительным старшим коэффициентом, то у этого трехчлена существует точка минимума $\bar \mu _k$, которая может быть найдена из необходимого условия экстремума $\dot \varphi(\mu) = 0$, откуда получаем:

$$ \bar \mu _k = -\frac {\dot \varphi(0)} {\ddot \varphi(0)} $$

Откуда последняя формула? С каких пор так ищем точку минимума?

 
 
 
 Re: Метод наискорейшего спуска.
Сообщение27.04.2014, 09:08 
Стандартное свойство параболы. Или, если угодно, формула метода Ньютона, который в квадратичном случае вырождается в один шаг.

 
 
 
 Re: Метод наискорейшего спуска.
Сообщение27.04.2014, 09:21 
Пусть
$$ f(x) = x^2 + x + 1 $$
Найдем точку минимума
$$ f'(x) = 2x + 1 = 0 $$
Стационарная точка $- \frac 1 2$ - ясно что это минимум.

по формуле выше
$$ \bar x = -\frac {\dot f(0)} {\ddot f(0)} = 1/2 $$

:lol: :lol: и правда получилось...
Сколько учусь, а формулы такой не припоминаю. Интересно в Фихтенгольце такая формула есть :!: :!: :!:

 
 
 
 Re: Метод наискорейшего спуска.
Сообщение27.04.2014, 09:43 
Метод Ньютона поиска экстремума -- это построение последовательности приближений $\mu_{k+1}=\mu_k-\dfrac{\dot\varphi(\mu_k)}{\ddot\varphi(\mu_k)}$. При определённых условиях эта последовательность сходится к точке экстремума. А для квадратичной функции -- сходится за один шаг, т.е. даёт точку экстремума сразу же.

Причина в том, что эта процедура основана на линеаризации производной, ну а в квадратичном случае эта производная и так линейна.

 
 
 
 Re: Метод наискорейшего спуска.
Сообщение27.04.2014, 15:15 
Трехчлен $ax^2+bx+c$ принимает экстремальное значение в точке $x=-\frac{b}{2a}$, и это написано в школьном учебнике.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group