Теорема 3.1. Необходимые условия

Глава 3

Функции нескольких переменных

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

Сначала рассмотрим вопрос анализа «в статике» с использованием положений линейной алгебры и дифференциального исчисления (приложение А), а также условия, которые (в достаточно общих возможных ситуациях) позволяют идентифицировать точки оптимума. Такие условия используются для проверки выбранных точек и дают возможность выяснить, являются ли эти точки точками минимума, максимума или седловыми точками. При этом задача выбора указанных точек остаётся вне рамок проводимого анализа; основное внимание уделяется решению вопроса о том, соответствуют ли исследуемые точки решениям многомерной задачи безусловной оптимизации, в которой требуется

минимизировать f(х), xÎR^N, (3.1)

при отсутствии ограничений на х, где х — вектор управляемых переменных размерности N, f — скалярная целевая функция. Обычно предполагается, что x_i (для всех значений i = 1, 2, 3,…, N)могут принимать любые значения, хотя в ряде практических приложений область значений х выбирается в виде дискретного множества. Кроме того, часто оказывается удобным предполагать, что функция f и ее производные существуют и непрерывны всюду, хотя известно, что оптимумы могут достигаться в точках разрыва f или ее градиента

(3.2)

Следует помнить, что функция f может принимать минимальное значение в точке , в которой f или f претерпевают разрыв. Кроме того, в этой точке f может не существовать. Для того чтобы построить систему конструктивных критериев оптимальности, необходимо (по крайней мере на первой стадии исследования) исключить из рассмотрения подобные ситуации, которые весьма усложняют анализ. Наконец, в ряде случаев приходится ограничиваться лишь идентификацией локальных оптимумов, поскольку нелинейная целевая функция f не всегда обладает свойством выпуклости (см. приложение Б) и, следовательно, может оказаться мультимодальной. На рис. 3.1 изображены линии уровня функции Химмельблау

f (x)= [ + – 11] + [ + – 7] . (3.3)

Нетрудно видеть, что эта функция имеет четыре различных минимума.

Далее перейдем к вопросу анализа «в динамике», который формулируется следующим образом: если точка х⁽⁰⁾ не удовлетворяет

функции Химмельблау

f(x)=[ + - 11] +[ + - 7]

Рис. 3.1. Линии уровня мультимодальной функции.

условиям, налагаемым упомянутыми выше критериями оптимальности, то как получить «хорошее» новое приближение x⁽¹⁾к решению х*? Попытка дать ответ на этот вопрос приводит к необходимости рассмотрения ряда методов, описание которых составляет значительную часть данной главы. Рассматриваемые методы классифицируются в соответствии с тем, используется ли информация о производных исследуемых функций. Глава завершается обсуждением относительных преимуществ методов и обзором результатов вычислительных экспериментов.

Критерии оптимальности

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

f(x)=f( )+ f( ) ∆x+½∆x f( )∆x+O (∆x), (3.4)

где — точка разложения из пространства R^N; ∆х = х - — величина изменения х; f(x) — N-мерный вектор-столбец первых производных f(х), вычисленных в точке ; f( ) = H ( ) — симметрическая матрица порядка N×N вторых частных производных f(x), вычисленных в точке . (Эту матрицу часто называют матрицей Гессе. Ее элемент, расположенный на пересечении i-й строки и j-го столбца, равен f / dx x .) O (∆x) — сумма всех членов разложения, имеющих порядок по ∆x выше второго. Пренебрегая членами высших порядков (т. е. исключая O (∆x)), определим величину изменения целевой функции f(х), соответствующего произвольному изменению х:

∆ f(x)= f(x) - f( ) = f( ) ∆x+½∆x f( )∆x (3.5)

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

∆f = f(x) - f( ) ≥0. (3.6)

Точка является точкой глобального минимума, если неравенство (3.6) выполняется для всех хÎ R^N; такие точки будем обозначать через х**. Когда формула (3.6) справедлива лишь в некоторой δ-окрестности точки , т. е. для всех х, таких, что ||х – || < δ при заданном δ > 0, то есть точка локального минимума, или х*. Если же

∆ f = f(x) – f( ) ≤0. (3.7)

то есть точка максимума (локального или глобального в соответствии с данными выше определениями). Исключение знака равенства из формул (3.6) и (3.7) позволяет определить точку строгого минимума или максимума. В случае когда ∆f принимает как положительные и отрицательные, так и нулевые значения в зависимости от выбора точек из δ-окрестности, точка представляет собой седловую точку.

Вернемся к равенству (3.5) и вспомним о выдвинутом ранее предположении о том, что f(х), f(x) и f(x) существуют и непрерывны для всех х Î R^N. Как следует из формулы (3.5), для того чтобы знак ∆f не менялся при произвольном варьировании ∆х, градиент f( ) должен быть равен нулю, т. е. должна быть стационарной точкой. В противном случае разность ∆f может принимать положительные или отрицательные значения в зависимости от знаков f( ) и ∆х Таким образом, точка должна удовлетворять условию стационарности

f( ) = 0, (3.8)

и формула (3.5) принимает следующий вид:

∆f(x) = +½∆x f( )∆x. (3.9)

Очевидно, что знак ∆f(x) определяется квадратичной формой

Q(х) = ∆x f( )∆x (3.10)

или Q(z)=z^TAz.

Из линейной алгебры известно (см. приложение А), что

А — положительно определенная матрица, если Q(z)>0 для любых z;

А — положительно полуопределенная матрица, если Q (z)≥0 для любых z;

А — отрицательно определенная матрица, если Q(z)<0 для любых z;

(3.11)

А — отрицательно полуопределенная матрица, если Q(z)≤0 для любых z;

А — неопределенная матрица, если Q (z)>0 для некоторых z и Q(z)<0 для остальных z.

Из (3.11) следует, что стационарная точка есть

точка минимума, если ²f( ) — положительно полуопределенная матрица;

точка максимума, если ²f( ) — отрицательно полуопределенная матрица;

(3.12)

cедловая точка, если ²f(x) 0 — неопределенная матрица.

Кроме того, может оказаться полезным провести анализ стационарной точки в несколько ином аспекте. Рассмотрим стационарную точку вместе с окружающей ее δ-окрестностью и векторами, исходящими из точки (рис. 3.2). При этом

= + s( ). (3.13)

Путем соответствующего выбора и s можно построить все точки из окрестности точки . Подстановка (3.13) в (3.9) дает формулу

∆f(x) = ( /2) s f( )s. (3.14)

Теперь с помощью (3.11) и (3.12) можно классифицировать s(x) как направление спуска, направление подъема или направление общего вида. Если направление спуска найти не удается, то

Рис.3.2. Окрестность стационарной точки.

является точкой локального минимума х*, что соответствует случаю,

когда ²f( ) — положительно полуопределенная матрица.

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

Теорема 3.1. Необходимые условия

Для наличия в точке х* локального минимума необходимо, чтобы выполнялось равенство

f(x*)=0 (3.15а)

и матрица ²f(x*) была положительно полуопределенной. (3.15б)

Дата добавления: 2018-06-01; просмотров: 437; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 5 6 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!