Методы оптимизации в технико-экономических задачах

в точке х(к) выбирают направление спуска - 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) может возникнуть осложнения, связанные с быстрым накоплением ошибки округления, тогда стоит прибегнуть к упрощенному методу Ньютона. Ошибка округления должна проверяться на каждом шаге - вычисления должны дублироваться в двух типах данных.

Если ошибка округления начинает недопустимо возрастать, то:

,

а затем вернуться на шаг назад и матрицу Гессе в дальнейшем не изменять.

В этом случае сходимость метода уменьшается, но и ошибка округления также снижается.