1.1 Теоретическая часть
Одним из самых распространённых методов минимизации, связанных с вычислением градиента, является метод спуска по направлению антиградиента минимизируемой функции.
Суть метода градиентного спуска
В природе мы нередко наблюдаем явления, сходные с решением задачи на нахождение минимума. К ним относится, в частности, стекание воды с берега котлована на дно. Упростим ситуацию, считая, что берега котлована "унимодальны", т.е. они гладкие и не содержат локальных углублений или выступов. Тогда вода устремится вниз в направлении наибольшей крутизны берега в каждой точке.
Переходя на математический язык, заключаем, что направление наискорейшего спуска соответствует направлению наибольшего убывания функции. Из курса математики известно, что направление наибольшего возрастания функции двух переменных u=f(x,y) характеризуется ее градиентом
где i, j - единичные векторы (орты) в направлении координатных осей. Следовательно, направление, противоположное градиентному, укажет путь, ведущий вниз вдоль наиболее крутой линии. Методы, основанные на выборе пути оптимизации с помощью градиента, называются градиентными.
Идея метода градиентного спуска состоит в следующем. Выбираем некоторую начальную точку и вычисляем в ней градиент рассматриваемой функции. Делаем шаг в направлении, обратном градиентному. В результате приходим в точку, значение функции в которой обычно меньше первоначального. Если это условие не выполнено, т. е. значение функции не изменилось либо даже возросло, то нужно уменьшить шаг. В новой точке процедуру повторяем: вычисляем градиент и снова делаем шаг в обратном к нему направлении. Процесс продолжается до выполнения условия останова.
Все методы спуска решения задачи безусловной минимизации различаются либо выбором направления спуска, либо способом движения вдоль направления спуска.
Это позволяет написать общую схему методов спуска.
Решается задача минимизации функции f(x) на всём пространстве Еn.
Методы спуска состоят в следующей процедуре построения последовательности {х(к)}. В качестве начального приближения выбирается любая точка х(0) с Еn. Последовательные приближения х(1), х(2),.. строятся по следующей схеме:
в точке х(к) выбирают направление спуска - Sk;
находят (к+1)-е приближение по формуле х(k+1) = хk -?к*Sk.
Направление Sk выбирают таким образом, чтобы обеспечить неравенство f(x(k+1))<f(x(k)) по крайней мере для малых значений величины ?к.
Число ?к определяет расстояние от точки х(к) до точки х(к+1). Это число называется длиной шага или просто шагом.
Основная задача при выборе величины ?к - это обеспечить выполнение неравенства f(x(k+1))<f(x(k)). Одним из элементарных способов выбора шага является способ удвоения шага.
Выбирают ак=ак-1. Если при этом f(x(k+l))<f(x(k)), то либо переходят к следующей (к+2)-й итерации, либо выбирают ак--2ак-1. Если значение f(x) меньше его предыдущего значения, то процесс удвоения можно продолжать до тех пор, пока убывание не прекратится.
Если f(x(k+1))>f(x(k)), то выбирают ?k=0.5* ?k. Если f(x(k)- 0.5* ?k *S(k))<f(x(k)), то полагают х( k+1)=хk -0.5* ?k *S(k) и переходят к следующей (к+2)-й итерации. Если же f(x(k)- 0.5* ?k *S(k))>f(x(k)), то выбирают ?к =0.25 ?к-1 и т.д.
Метод градиентного спуска сходиться достаточно медленно, поэтому чаще для решения задачи безусловной минимизации функции нескольких переменных используют метод Ньютона, сходимость которого на порядок выше.
Рассмотрим метод Ньютона.
Сначала необходимо найти стационарную точку как:
(1.1)
Систему (1.1) решаем приближенно методом Ньютона для решения системы нелинейных уравнений, который основан на разложении в ряд Тейлора, т.е. с использованием первого дифференциала :
где ,
,
,
- остаточный член.
Затем приравниваем левую часть уравнения к 0 и отбрасываем . В результате получим:
.
Новые приближения и :
(1.2)
Выразим остальные члены:
,
,
,
.
Тогда получим следующую систему уравнений:
,
где и - неизвестные.
Матрица этой системы является матрицей Гессе:
, (1.3)
где .
Из (1.2) находим точку минимума функции.
К достоинствам метода Ньютона стоит отнести быструю сходимость, недостатком же является необходимость нахождения первой и второй производных минимизируемой функции.
При решении системы (1.3) может возникнуть осложнения, связанные с быстрым накоплением ошибки округления, тогда стоит прибегнуть к упрощенному методу Ньютона. Ошибка округления должна проверяться на каждом шаге - вычисления должны дублироваться в двух типах данных.
Если ошибка округления начинает недопустимо возрастать, то:
,
а затем вернуться на шаг назад и матрицу Гессе в дальнейшем не изменять.
В этом случае сходимость метода уменьшается, но и ошибка округления также снижается.
1.2 Задание
Зависимость расходов предприятия, прогнозируемых на будущий квартал от факторов x1, x2 задаётся в некоторых денежных единицах функцией
Найти значение x1 и x2, при которых прогнозируемые расходы минимальны. Использовать комбинацию одного их градиентных методов с методом Ньютона.
Фиксировать x3=0,31
1.3 Построение математической модели задачи
Задача минимизации функции от двух переменных сводится к нахождению таких значений х1* и х2*, при которых
При kv=0.739,
Найдём производную функции по переменной х1:
Найдём производную функции по переменной х2:
Найдём вторую производную функции по переменной х1:
Найдём вторую производную функции по переменной х2:
Найдём вторую производную функции по переменным х1 и х2:
Таким образом, градиент функции будет равен:
Далее необходимо определить величину шага ?k, для которого бы выполнялось неравенство: f(x(k+1))<f(x(k)).
Задача нахождения минимума функции сводится к построению последовательностей
x1(k+1) = х(к) -?к * grad(f(x1(k)))
x2(k+1) = х(к) -?к * grad(f(x2(k)))
до тех пор, пока не выполнятся условия останова:
u1:
, где
u2:
u3:
, где
u4: Если условия u2 u3 выполняются, а условие u1 нет, на протяжении 10 итераций, вычисления прекратить и вывести результат.
1.4 Решение задачи
Необходимо найти величину шага. За начальную точку берём х1(0)=0 и х2(0)=0. f(х1(0); х2(0))=16,43.
1) ?0(1)=1
х1(1)=-1,3388
х2(1)=0,9076
f(х1(1); х2(1))=33,59
Получили f(x(k+l)) > f(x(k)), таким образом, следует уменьшить шаг.
2) ?0(2)=0,5
х1(2)=8,8788
х2(2)=-4,2155
f(х1(2); х2(2))=765,129
Получили f(x(k+l)) > f(x(k)), таким образом, следует уменьшить шаг.
3) ?0(3)=0,25
х1(3)=-25,6164
х2(3)=11,1324
f(х1(3); х2(3))=5923,182
Получили f(x(k+l)) > f(x(k)), таким образом, следует уменьшить шаг.
4) ?0(4)=0,125
х1(4)=23,2581
х2(4)=-9,4773
f(х1(4); х2(4))=4857,293
Получили f(x(k+l)) < f(x(k)), величина шага выбрана ?0=0,125
Метод градиентного спуска:
1 итерация:
х1(1)=-1,3388
х2(1)=0,9076
u1: =17.1637
Ef=8.399*10-6
Условие останова не выполняется, т.к.
u2: =1.62621
Ex=0.000808
Условие останова не выполняется, т.к.
u3: =10.818
E=0.211653
Условие останова не выполняется, т.к.
2 итерация:
х1(2)=8.8788
х2(2)=-4.2156
u1: =731.5315
Ef=0.000191
Условие останова не выполняется, т.к.
u2: =11.43007
Ex=0.004914
Условие останова не выполняется, т.к.
u3: =76.5888
E=4.820012
Условие останова не выполняется, т.к.
Последняя итерация:
х1(k+1)=-0.05001334
х2(k+1)=0.1100748
u1: =1.2805*10-9
Ef=4.08599*10-6
Условие останова выполняется, т.к.
u2: =5.8072*10-5
Ex=6.045204*10-5
Условие останова выполняется, т.к.
u3: =0.0002276
E=0.10296
Условие останова выполняется, т.к.
Все три условия останова выполняются, следовательно в точках
x*=(-0.05001334;0.1100748) функция достигает своего минимума равного
f(-0.5001334;0.1100748)=8,2853964
На этом останавливаемся и проводим последнюю итерацию методом Ньютона:
Принимаем за начальные точки, точки получившиеся в результате метода градиентного спуска, т.е.
х1(0)=-0.05001334
х2(0)=0.1100748
Подставив вычисленные вторые производные в этих точках в систему уравнений (1,3), решаем её.
14*? х1(1)-3* ? х2(1)=0,27918
-3* ? х1(1)+8* ? х2(1)=-0,58
Получаем
? х1(1)=0,04764
? х2(1)=-0,0707
Проверяем условия останова:
u1: =0,16797
Ef=4.14861*10-6
Условие останова выполняется, т.к.
u2: =0,08525
Ex=4,2626*10-5
Условие останова выполняется, т.к.
u3: =0,17054
E=0,10453
Условие останова выполняется, т.к.
Решение найдено. Функция
принимает свое минимальное значение 8,2853964 в точках x*=(0,04764; -0,0707)
1.5 Тестирование задачи на ЭВМ
2. Задача линейного планирования производства
- Задание на курсовую работу по математической экономике (общая часть)
- Задание (вариант 18)
- ВВЕДЕНИЕ
- 1. Неклассические методы оптимизации
- 1.1 Теоретическая часть
- 2.1 Теоретическая часть
- 1.2 Задание
- 1.3 Построение математической модели задачи
- 2.3 Построение математической модели задачи
- 1.4 Решение задачи
- 1.5 Тестирование задачи на ЭВМ
- 2.4 Решение задачи
- 3.3 Построение математической модели задачи
- 3.4 Решение транспортной задачи
- Заключение
- 3.3. Методы оптимизации технологических объектов
- 14. Оптимизационные методы экономического анализа.
- 2.9 Технико-экономический анализ инженерных решений
- Классификация задач оптимизации.
- Математические методы оптимизации технологических систем
- 9.3. Методы оптимизации решений
- 1.1 Предмет, метод и задачи курса «Технико-экономическое проектирование пищевых предприятий».
- 4.3. Методы оптимизации технологических объектов управления
- Лекция №4 Критерии технико-экономической оптимизации