Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Оптимизация
| Харчистов Б.Ф.. Методы оптимизации, 2004 | |
Метод наискорейшего спуска |
|
|
В данном случае на каждой итерации шаг Хк выбирается из условия минимума функции f (х) в направлении движения, т. е. f (х(k-1) -XJ'(х(k-1))) = min ф(А), Я> 0 где ф(А) = f (х(k-1)-Я/(х(k-1))). Такой способ выбора Xk требует меньшего числа итера-ций, чем предыдущий, поскольку он обеспечивает достижение наименьшего значения функции вдоль заданного направления. Однако в этом варианте градиентного метода на каждой итерации требуется решать задачу одномерной минимизации, что приводит к увеличению трудоемкости итерации. Итак, метод наискорейшего спуска требует меньшего числа итераций, чем метод с дроблением шага, но каждая итерация сложнее реализуется. Алгоритм решения задачи безусловной минимизации методом наискорейшего спуска заключается в следующем. Задаются е, x(0); вычисляются f (x(0)), f' (x(0)), f'(x(0)) ; полагается к=1. Определяется Як. Вычисляются Ax(к) = - V'(x(к-1)), x(к) = x(к-1) +Ax(к), f (x(к)), f X x(к)), ||f'( x(к ))||. Проверяется условие окончания вычислений < е. f X x(к)) * (к) Если оно выполняется, то полагается x = x f* = f(x (к) ) и вычисления завершаются. Если условие не выполняется, то полагается к=к+1 и осу-ществляется переход к п.2. Пример. Решить методом наискорейшего спуска задачу безусловной минимизации f (x) = x\ + 2x2 - 4x1 + 2x2 ^ min при е = 0,3, x(0) = (1,0). Решение. Находим первые частные производные f (x) : df л df л - = 2 x1 - 4, = 4 x2 + 2. dx1 dx2 Первая итерация Определяем \ : (0)-я^/Х^ = 1 -Л(-2) = 1 + 2Я, dx1 х20)-Я^^ = 0-Я-2 = -2Я ; дх2 р(Я) = f (х(0) -Яf'(х(0))) = (1 + 2Я)2 + 2(-2Я)2 - - 4(1 + 2Я) + 2(-2Я); р '(Я) = 2(1 + 2Я)2 + 4(-2Я)(-2) - 8 + 2(-2) = 24Я - 8; р '(Я) = 0 ^ 24Я- 8 = 0 ^ Я = 1/3. Поскольку р"(Я) = 24 > 0, то Я = 1/3 есть точка минимума р(Я) . Следовательно, Я1 = 1/3 = 0,333. Вторая итерация Определяем Я2 : х1(1) -Яд(х(1)) = 1,667 + 0,667Я, 1 дх1 хл - я df (х(1)) = -0,667 + 0,667Я; дх2 р(Я) = f (х(1) - Я'(х(1))) = (1,667 + 0,667Я)2 + 2(-0,667 + + 0,667Я)2 - 4(1,667 + 0,667Я) + 2(-0,667 + 0,667Я); р '(Я) = 2(1,667 + 0,667Я)0,667 + 4(-0,667 + 0,667Я)0,667 - 4 - 0,667 + 2 - 0,667 = 2,667Я - 0,886; р '(Я) = 0 ^ 2,667Я- 0,886 = 0 ^ Я = 0,332. Поскольку р"(Я) = 2,67 > 0, то Я = 0,332 есть точка минимума р(Я) . Следовательно, Я2 = 0,332. Третья итерация Определяем Я3 : х12) - Я ^^ = 1,89 + 0,22Я, х22) - Я^^ = -0,445 - 0,22Я; 1 дх1 2 дх2 р(Я) = f (х(2) -Я'(х(2))) = (1,89 + 0,22Я)2 + 2(-0,445 - 0,22Я)2 - 4(1,89 + 0,22Я) + 2(-0,445 - 0,22Я); р '(Я) = 2(1,89 + 0,22Я)0,22 + 4(-0,445 - 0,22Я)(-0,22) - - 4 Х 0,22 + 2(-0,22) = 0,29Я - 0,0968; р '(Я) = 0 ^ 0,29Я- 0,0968 = 0 ^ Я = 0,333. Поскольку р"(Я) = 0,29 > 0 , то Я = 0,333 есть точка минимума р(Я) . Следовательно, Я3 = 0,333. Результаты вычислений заносим в табл. 6.2. Таблица 6.2 Ном. итер. Я Ах1 Ах, х1 х2 f ( х) f Эх] f Эх2 1И1 0 1 0 -3 -2 2 2,83 1 0,333 0,667 -0,667 1,67 -0,667 -4,33 -0,667 -0,667 0,943 2 0,333 0,222 0,222 1,89 -0,445 -4,48 -0,22 0,22 0,311 3 0,333 0,074 -0,074 1,96 -0,518 -4,5 -0,074 -0,074 0,105 Поскольку условие окончания вычислений выполнено (f'(х(3)) = 0.105 < ? = 0,3), то вычисления завершаются. В результате решения задачи безусловной минимизации получаем х* = х(3) = (1,96; - 0,518), f * = f (х(3)) = -4,5. Ответ: х = (1,96; - 0,518), f =-4,5. |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "Метод наискорейшего спуска" |
|
|