Многомерные задачи оптимизации (стр. 3 из 6)

Как было отмечено в п. 2.1, задача одномерной оптимизации дифференцируемой функции

сводится к нахождению критических точек этой функции, определяемых уравнением: (2.7)

Когда уравнение (2.7) нельзя решить аналитически, для его решения можно применить численные методы, например метод Ньютона. В этом случае говорят о методе Ньютона решения задачи оптимизации.

Пусть

- решение уравнения (2.7), а некоторое начальное приближение к . Применим для решения (2.7) метод Ньютона решения уравнения , которое эквивалентно уравнению (2.7) при . Для этого в формулу для -го приближения метода Ньютона подставим вместо производную и получим тем самым формулу для -го приближения к решению уравнения (2.7):

(2.8)

для использования этой формулы необходимо, чтобы

. В качестве критерия окончания итерационного процесса можно применить условия близости двух последовательных приближений

или близости значений целевой функции на этих приближениях

.

Достаточное условие сходимости метода Ньютона (2.8) можно получить. А именно, справедлива следующая теорема.

Теорема. Пусть

- корень уравнения (2.7), т.е. , а и непрерывна. Тогда существуют окрестность корня такая, что если начальное приближение принадлежит этой окрестности, то для метода Ньютона (2.8) последовательность значений сходится к при .

Заметим, что точка

может являться как точкой минимума, так и точкой максимума, а может (при ) вообще не являться точкой экстремума. Если функция имеет как минимумы, так и максимум то она может сходиться и к точкам минимума, и к точкам максимума в зависимости от того, из окрестности какой критической точки взято начальное приближение. При этом, в отличие от других методов оптимизации, формула для поиска максимума функции совпадает с формулой для поиска минимума.

Формулу метода Ньютона решения задачи оптимизации можно получить и из других соображений. Разложим функцию

в ряд Тейлора в окрестности точки , ограничившись линейными и квадратичными членами относительно приращения :

(2.9)

В качестве следующего приближения

к оптимальному значению проектного параметра возьмем точку экстремума функции . Имеем

что совпадает с (2.8). Разложение (2.9) в окрестности точки

, на котором график функции заменяется параболой графиком функции .

Относительно сходимости метода Ньютона решения задачи оптимизации можно сделать замечания. Метод Ньютона обладает более быстрой сходимостью по сравнению с методами, которые не используют дифференциальные свойства функции (например, с методом золотого сечения). Однако сходимость метода Ньютона не гарантирована, при неудачном выборе начального приближения он может расходиться.

3. Многомерные задачи оптимизации

3.1 Минимум функции нескольких переменных.

В пункте 2 мы рассмотрели одномерные задачи оптимизации, в которых целевая функция зависит лишь от одного аргумента. Однако в большинстве реальных задач оптимизации, представляющих практический интерес, целевая функция зависит от многих проектных параметров.

Минимум дифференцируемой функции многих переменных

можно найти, исследуя ее значения в критических точках, которые определяются из решения системы дифференциальных уравнений

(3.1)

Рассмотренный метод можно использовать лишь для дифференцируемой целевой функции. Но и в этом случае могут возникнуть серьезные трудности при решении систем нелинейных уравнений (3.1).

Во многих случаях никакой формулы для целевой функции нет, а имеется лишь возможность определения ее значений в произвольных точках рассматриваемой области с помощью некоторого вычислительного алгоритма или физических измерений. Задача состоит в приближенном определении наименьшего значения функции во всей области при известных ее значениях в отдельных точках.

Для решения подобной задачи в области проектирования,

в которой ищется минимум целевой функции , можно дискретное множество точек (узлов) путем разбиения параметров на части с шагам .

В полученных узлах можно вычислить значения целевой функции и среди этих значений найти наименьшее.

Такой метод аналогичен методу перебора для функции одной переменной. Однако в многомерных задачах оптимизации, где число проектных параметров достигает пяти и более, этот метод потребовал бы слишком большого объема вычислений.

3.2 Метод покоординатного спуска.

Пусть требуется найти наименьшее значение целевой функции

. В качестве приближения выберем в мерном пространстве некоторую точку . Зафиксируем все координаты функции , кроме первой. Тогда фукция одной переменной . Первый шаг процесса оптимизации состоит в спуске по координате в направлении убывания функции от точки до некоторой точки . Если функция дифференцируемая, то значение может быть найдено

(3.2)

Зафиксируем теперь все координаты кроме

, и рассмотрим функцию при переменной . Снова осуществляем спуск теперь по координате , в сторону убывания функции от точки до точки . Значение можно найти