Методы минимизации функций нескольких переменных

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

1. Точка х^*Î U_n, называется точкой глобального минимума функции J (Х), если для всех х^*Î U_n выполняется неравенство J (x^*) £ J (Х). Значение называется минимумом функции. Множество всех точек глобального минимума функции J (Х) обозначают через U ^*.

Замечание. Если U ^* ¹ 0, то вместо минимума функции J (Х) иногда рассматривают ее точную нижнюю грань , определение которой в n –мерном случае практически не отличается от определения для одномерной функции.

2. Точка называется точкой локального минимума функции J (Х), если существует e–окрестность точки : U _n ()={Х | r(Х, ) < e} такая, что для всех х^*Î U _n () выполняется неравенство J () £ J (Х).

3. Если допустимое множество U_n в задаче минимизации (максимизации) функции n переменных совпадает со всем пространством E _n, то говорят о задаче безусловной оптимизации

, x Î E _n.

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

В общем случае рассматривается задача ,

предполагая, что функция непрерывно дифференцируема на . Согласно определению дифференцируемости функции

,

где . Если , то при достаточно малых приращение будет определяться дифференциалом функции .

Справедливо неравенство Коши-Буняковского

,

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

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

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

.

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

Все методы спуска работают по единой схеме:

1. Выбирается начальное приближение – некоторая точка и каким-то образом выясняется, что не есть точка минимума . Целесообразно использовать всю имеющуюся информацию о поведении целевой функции , чтобы выбрать поближе к точке минимума .

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

Вектор , а иногда и сам вектор называется направлением спуска.

3. Определяется величина шага спуска по направлению , то есть положительное число , для которого выполняется неравенство

.

4. За очередное приближение к точке минимума принимается

.

5. Проверяется выполнение критерия окончания итераций (об этом смотри ниже). Если критерий выполняется, то итерации прекращают и полагают . В противном случае возвращаются к п. 2.

Последовательность точек генерируемая методом спуска, называется траекторией спуска.

Критерием прекращения процесса вычислений на k -м шаге часто выбирается близость градиента к нулю: .

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

Помимо сравнения градиента с нулем используются также критерии: и , где - заданные положительные числа. Нередко используют различные сочетания этих трех критериев.

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

.

Проблемы решения данной задачи были рассмотрены в предыдущем пункте. Следовательно, для нахождения необходимо написать функцию , где с учетом и вычислялись бы последовательно и . Значения и удобно передавать в функцию через общую область (если используется язык ФОРТРАН), или сделать их глобальными переменными (в случае применения языков программирования ПАСКАЛЬ либо Си). Далее, воспользовавшись уже готовой функцией поиска минимума функции от одной переменной, определяется искомое = .

На этом этапе вычислительного процесса необходимо предварительно задаться отрезком . В случае задачи безусловного поиска глобального минимума унимодальной функции величина его может быть произвольной. Но если область определения J (Х) ограничена, либо решается задача отыскания локального минимума J (Х), следует ввести ограничения и на величину шага в направлении . Рекомендуется выбирать значения границ отрезка , которому должен принадлежать искомый , с учетом выполнения следующего условия:

Любая компонента вектора должна отличаться от соответствующей компоненты вектора не более чем в 2-3 раза.

Таким образом, перед обращением к функции необходимо для определения a и b решить соответствующую систему неравенств.

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

В том случае, когда область определения U_n функции J (Х) ограничена , в функцию необходимо ввести соответствующие корректирующие операторы:

Измененное в значение возвратится (через параметр) в вызывающую подпрограмму (функцию).

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

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

Дата добавления: 2014-12-27