В данном случае в качестве h(k) используется нормиро-
(- f Xx(k-1)))/||f'(x(k-1))
(k)
т. е. x
определя-
ванный антиградиент ется из соотношения
(k)
(k-1) -Як
x
x
fX x(k-1))
fX x(k-1))
Величина Xk выбирается так, чтобы выполнялось условие (6.1). Процесс выбора Xk осуществляется следующим образом.
Выбираются некоторые константы а> 0 и 0<в<1 (часто в = 2).
На k-й, k=1,2,..., итерации проверяется выполнение условия (6.1) при \ =а. Если оно не выполняется, то производится дробление
шага, т.е. полагается Xk =ав и вновь проверяется выполнение условия (6.1). Процесс дробления, т.е. умножение текущего значения Хк на в, продолжается до тех пор, пока условие (6.1) не окажется выполненным.
Алгоритм решения задачи безусловной минимизации методом с дроблением шага заключается в следующем.
1. Задаются а, в, ?, x(0); вычисляются f (x(0)), f'(x(0)),
f X x(0))
полагается k=1.
f X x(k-1))
Ax(k) =-Я
(k) (k-1) . x = x +
f'( x(k-1))
3. Вычисляются
+ Ax(k}, f ( x(k)).
4. Проверяется условие выбора Хк :
f (x(к)) < f (x(к-1)). Если оно выполняется, то осуществляется переход к п.5. Если условие не выполняется, то полагается Хк = Хк ( и осуществляется переход к п.3.
Вычисляются f' (x(к)), f'(x(к)) .
Проверяется условие окончания вычислений
<е.
f'( x(к))
* (к)
Если оно выполняется, то полагается x = x(
f = f (x(к)) и вычисления завершаются.
Если условие не выполняется, то полагается к=к+1 и осу-ществляется переход к п.2.
Отметим, что помимо рассмотренного применяется алгоритм, в котором в качестве начального значения Хк используется
конечное значение Хк-1. При этом в п. 1 рассмотренного алгоритма добавляется определение А0: полагается А0 =а; в п.2 алгоритма заменяется определение Хк : полагается Хк =Хк-1.
Пример. Решить методом с дроблением шага задачу безусловной минимизации
f (x) = xj2 + 2x22 - 4x1 + 2x2 ^ min при a = 1, ( = 2, ? = 0,3, x(0) = (1, 0).
Решение.
Находим первые частные производные f (x) :
df л df л - = 2 x1 - 4, = 4 x2 + 2. dx1 dx2
Используем второй (упрощенный) вариант метода с дроблением шага.
Результаты вычислений заносим в табл. 6.1 .
Таблица 6.1
Ном. итер. Я ATJ Ах2 х1 х2 f ( х) f
Эх] f
дх2 1И1
0 1 2 1 1 0,707
0,580 -0,707 0,820 1
1,71 2,29 0
-0,707 0,113 -3 -4,32 -3,67 -2 -0,586 2
-0,828 2,83 1,01
f (х(2)) > f (х(1)) ^Я = Яр = 0.5
2 3 0,5 0,5 0,290 0 0,410 -0,5 2,00 2,00 -0,297 -0,797 -4,42 -4,32 0 0,812 0,812
f (х(3)) > f (х(2)) ^Я = Яр = 0.25
3 0,25 0 -0,25 2,00 -0,547 -4,496 0 -0,188 0,188
1. Поскольку условие окончания вычислений выполнено (f'(х(3)) = 0,188 < ? = 0,з), то вычисления завершаются.
В результате решения задачи безусловной минимизации получаем х* = х(3) = (2; - 0,547), f * = f (х(3)) = -4,496. Ответ: х = (2; - 0,547), f =-4,496.
|
- ГРАДИЕНТНЫЕ МЕТОДЫ
методы относятся к группе методов спуска, являющихся численными методами решения задач безусловной минимизации f (x) ^ min, x е Rn. Исходя из заданной начальной точки x(0), методы спуска позволяют строить последовательность точек x(1), x ,..., удовлетворяющих условию f(x(k)) < f (x(к-1)), к = 1,2,... (6.1) В общей схеме методов спуска последовательность x(0) , x(1), x*-2),... приближений к
- Метод наискорейшего спуска
метода на каждой итерации требуется решать задачу одномерной минимизации, что приводит к увеличению трудоемкости итерации. Итак, метод наискорейшего спуска требует меньшего числа итераций, чем метод с дроблением шага, но каждая итерация сложнее реализуется. Алгоритм решения задачи безусловной минимизации методом наискорейшего спуска заключается в следующем. Задаются е, x(0); вычисляются f
- Задачи
методом с дроблением шага задачу безусловной минимизации f (х) = х^2 + 2х^ - 2х1 + х2 - 5 ^ min , при а = 1, в = 0,5 , ? = 0,4, х(0) = (0, 2). Решить методом наискорейшего спуска задачу безусловной минимизации f (х) = х^2 + 2х^ - 2х1 + х2 - 5 ^ min , при ? = 0,4, х(0) = (0,
- 1.5. Цели предпринимательской деятельности
методы осуществления предпринимательской деятельности, ее стиль. Все это обеспечивает эффективное поведение предпринимательских единиц в сложившихся или меняющихся условиях окружающей среды. Главной целью внутрифирменного предпринимательства является стимулирование и удовлетворение спроса общества на конкретные потребности общества в рамках существующей коммерческой организации, а главной целью
- 22.3 Развитие на основе инновационно-инвестиционных факторов
методическими подходами. Формально при оценке коммерческой эффективности инвестиционного проекта каждый инвестор имеет право самостоятельно устанавливать норму годового дохода на вложенный капитал, т.е. каждый хозяйствующий субъект использует индивидуальную норму дисконта. Однако экономически обоснованные подходы предполагают оп ределение нижней и верхней границы нормы дисконта, в интервале
- 24.6 Учет инфляции, риска и неопределенности
методы: 1) укрупненную оценку устойчивости; 2) расчет уровней безубыточности; 3) метод вариации параметров; 4) оценку ожидаемого эффекта проекта с учетом количествен ных характеристик неопределенности. Каждый последующий метод является более точным, хотя и бо лее трудоемким, и поэтому применение каждого из них делает не нужным использование предыдущих. Все методы, кроме первого,
- 16.2. ТАРИФНОЕ НОРМИРОВАНИЕ ЗАРАБОТНОЙ ПЛАТЫ
методики оценки рабочих мест, другие материалы. Единый тарифно-квалификационный справочник работ и про-фессий рабочих (ЕТКС) - нормативный общероссийский документ, предназначенный для тарификации работ, профессий рабочих и со-ставления учебных программ для подготовки и повышения квали-фикации рабочих на предприятиях и в организациях независимо от форм собственности и подчиненности. Однако для
- 13.1. Концепция маркетинга: понятие, цели
методами. Главная страте гическая цель на всех этапах развития маркетинга остается неизменной - максимизация прибыли в условиях товарного изобилия и насыщенности рынка при отстающей платежеспособности, а его главная черта - макси-мально возможно удовлетворять потребности развивающегося бизнеса во всех сферах деятельности. Но эта черта камуфлируется необходимостью учета интересов потребителя. С
- 2.1 Мера ценности.
методов производства, когда соответствие затрат и результатов нарушалось преимущественно под влиянием внешних факторов стихийного либо военно-политического характера (неурожаи, войны, политические и социальные потрясения и т.п.). В обычное же время цены товаров оставались достаточно устойчивыми. При регулярно повторяющемся производстве это позволило использовать для установления цены товаров
- 8.2. Некоторые практические предложения
методах, рассмотренных в предыдущих главах и моделях, и что модель, рассмотренная в параграфе 6.2, окажет значительную помощь. Однако практическое про граммирование должно часто осуществляться вне рамок этой модели или по крайней мере дополнять ее частичным исследованием. Это относится прежде всего к вычислениям, проводимым на стадиях 6, 7 и 8. Иногда элементы, рас сматриваемые в параграфах
|
Экономика