Глава 10. МЕТОДЫ МНОГОМЕРНОЙ МИНИМИЗАЦИИ

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

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

§ 10.1. Задача безусловной минимизации функции многих переменных

1. Постановка задачи. Определения.

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

Точка называется точкой локального минимума функции если существует такая -окрестность этой точки, что для всех

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

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

2. Поверхность уровня, градиент и матрица Гессе. Необходимые и достаточные условия локального минимума.

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

Рис. 10.1

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

Для дифференцируемой функции определен вектор из первых частных производных

Рис. 10.2

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

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

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

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

составленной из вторых частных производных функции Матрицу (10.3) принято называть матрицей Гессе.

3. Выпуклые функции.

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

Рис. 10.3

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

Функция называется сильно выпуклой с постоянной если для любых выполнено неравенство

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

где постоянная, входящая в неравенство (10.4).

4. Задача минимизации квадратичной функции.

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

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

Вычислим градиент и матрицу Гессе для функции (10.5). Дифференцирование по дает

Пользуясь симметрией матрицы А, получим формулу

Таким образом,

Дифференцируя обе части равенства (10.7) по получим Это означает, что для квадратичной функции (10.5) матрица Гессе не зависит от х и равна А.

Задача минимизации квадратичной функции представляет интерес многим причинам. Отметим две основные из них. Во-первых, в малой окрестности точки минимума гладкая целевая функция хорошо аппроксимируется суммой первых трех слагаемых ее разложения по формуле Тейлора:

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

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

Более того, решение системы (10.10) дает точку минимума функции

(10.6). Действительно, является стационарной точкой функции Так как матрица Гессе положительно определена, то в точке выполнены достаточные условия минимума и, значит,

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

Отметим, что поверхностями уровня квадратичной функции (10.6) служат -мерные эллипсоиды (при эллипсы) с центром в точке х. Отношение большей оси каждого из этих эллипсоидов (эллипсов) к меньшей оси равно числу обусловленности матрицы А. Здесь Лпвд и максимальное и минимальное собственные значения матрицы А. Чем больше отношение тем сильнее вытянуты поверхности (линии) уровня.

5. Обусловленность задачи минимизации.

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

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

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

Пусть теперь для решения задачи минимизации доступны

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

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